Add support for certain larger moduli #2
Description
Is your feature request related to a problem? Please describe.
Some lattice-based constructions, such as streaming verifiable computation, use a sum of hash values and require a modulus larger than 257 currently supported by LibSWIFFT.
Describe the solution you'd like
Add support for certain larger moduli such that many more short vectors can be aggregated while maintaining high performance. The suggested moduli are the Fermat prime q=2^{16}+1 and the Mersenne prime q=2^{31}-1. The modular arithmetic operations for these moduli likely fit within 32-bit and 64-bit respectively. These moduli should also allow for high performance because they are one-off from a power of 2.
Describe alternatives you've considered
Other moduli besides the suggested ones were considered. For performance reasons, Fermat and Mersenne primes, being one-off from a power-of-2, are good candidates. There is only one known Fermat prime 2^{16}+1 that is larger than 257. It should be a good fit for a 32-bit register the same way 257 is a good fit for a 16-bit register. There is no Mersenne prime that is a better fit for a 32-bit register. For a 64-bit register, the best fitting Mersenne prime is 2^{31}-1.
Additional context
N/A.