Imagine I have 64-bit machine and the widest integer available is 64-bit signed long. I cannot use BigInteger or similar libraries for performance reasons, and all calculations I get would me modulo $2^{64}$. I need to choose prime $p$ close to $2^{63}$ but less than $2^{63}$ (which one would it be, I think choosing $2^{61}$ would make my computations faster?) and need to implement multiplication modulo $p$. Is there any known algorithm to do so?
Modular multiplication with machine word limitations
4
$\begingroup$
elementary-number-theory
prime-numbers
modular-arithmetic
-
0If you're working on a 64-bit architecture, chances are that an exact 64 bit multiplication with a 128 bit result is supported natively. For example the imulq and mulq instructions on x86-64 do just that and place the result in two separate 64 bit registers. Check if such a multiplication is available in a (standard) library. Once you have that you're all set (see for example the answer by Richard). – 2012-11-04