search

quarkslab / NFLlib

NTT-based Fast Lattice library
MIT License
162 stars 52 forks source link

Am I doing something completely wrong ? #31

Open Kirija opened 6 years ago

Kirija commented 6 years ago

2 options : either I am completely wrong or there are enormous bugs (I tried a commit from last year but got the same behaviour) .... I'd prefer the first option.

x={1,2,3,4,5,6,7,8}; y={0}; (x==y) returns TRUE !

x={1,2,3,4,5,6,7,8}; y={1}; z=x*y; // after that z={1} !

See the following commit for the full example : https://github.com/Kirija/NFLlib/commit/8b24259e58f085a35d1b759ffea28ea18a0152ac

Kirija commented 6 years ago

Regarding the second issue, i may have overlooked the hypothesis that polynomials are under ntt form. But still, the first issue remains.

fionser commented 6 years ago
  1. Multiplication on poly is done coeffient-wisely.
  2. To perform meaningful polynomial multiplication, you should use the "poly::ntt" first, then coefficient-wise multiplication (i.e., "a*b"), then "poly:ntt_inv" to convert back the NTT-format to coefficient format.
Kirija commented 6 years ago

Thanks Riku, but as i said the main issue is #1.

urianr commented 2 days ago

I also run into the equality bug. if equality isn't working than the tests will probably not have spotted wrong calculation. So, maybe the wrong NTT calculation was not detected. At the current status, this lib is not usable.