search

quarkslab / NFLlib

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

Why this Specified Format of Primes ? #43

Closed fionser closed 6 years ago

fionser commented 6 years ago

NFL uses 2^62 - i * 2 * kMaxPolyDegree + 1 primes. Does any reason for this specific form ? Could we use any other 62-bit long prime ?

carlosaguilarmelchor commented 6 years ago

No this is needed to ensure that there are primitive roots of unity of large-enough degree, which in turn is required by the NTT algorithm. Carlos