search

data61 / cuda-fixnum

Extended-precision modular arithmetic library that targets CUDA.
Other
41 stars 28 forks source link

Implement support for even moduli #22

Open unzvfu opened 6 years ago

unzvfu commented 6 years ago

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.

unzvfu commented 6 years ago

Another possibility is to use Barrett reduction for even moduli.

unzvfu commented 4 years ago

Follow up at https://github.com/unzvfu/cuda-fixnum/issues/9.