search

unzvfu / cuda-fixnum

Extended-precision modular arithmetic library that targets CUDA.
MIT License
32 stars 7 forks source link

Implement support for even moduli #9

Open unzvfu opened 4 years ago

unzvfu commented 4 years ago

From https://github.com/data61/cuda-fixnum/issues/22:

Montgomery reduction requires an odd modulus, and that's the only one that's implemented at present. Even moduli could be handled by having special code for moduli that are powers of 2 (in which case reduction is very fast), together with CRT.

This is lowish priority, since the main case is that of prime moduli, which are all odd.

Another possibility is to use Barrett reduction for even moduli.