I have two variables, $x$ and $y$. I'm looking to compute the product of $x$ and $y$ modulo $p$, where $p$ is prime.
For small values of $x$ and $y$ (less than 43 bits each), I was able to perform the computation using Barrett Reduction.
However, for large values of $x$ and $y$, overflow exceeding 128 bits occurs, and the computed value is incorrect. This is because $x$ and $y$ must be multiplied together, which must be stored in a 128-bit datatype. That product must then be multiplied by a precomputed constant, $r$, resulting in a value that can be stored in 192 bits.
Is it possible to compute xy mod p
using Barrett Reduction where overflow over 128 bits does not occur, also while not relying on floating point arithmetic?
If it helps, I have the ability to perform the multiplication of $x$ and $y$ and store the product in two variables: $a$ and $b$, where $a$ holds the high 64 bits of the product, and $b$ holds the low 64 bits of the product.
Best Answer
Yes, but in addition to $r = \left\lfloor \dfrac{2^{64}}p\right\rfloor$, you will also need $$s =\left\lfloor \dfrac{2^{128}}p\right\rfloor - 2^{64}r$$ and $$t = 2^{64} - rp$$ Note that $s,t < 2^{64}$.
So you have $xy = a2^{64} + b$. Then $$\begin{align}xy \bmod p &= (a2^{64} + b) \bmod p\\&= \big[(a2^{64}\bmod p) + (b\bmod p)\big]\bmod p\end{align}$$
Per Barrett's algorithm, to calculate $a2^{64}\bmod p$, you first calculate $$q = \left\lfloor\dfrac {a2^{64}(2^{24}r + s)}{2^{128}}\right\rfloor = ar + \left\lfloor\frac{as}{2^{64}}\right\rfloor$$
The approximate modulus is then $$2^{64}a - qp = a(2^{64} - rp) - \left\lfloor\frac{as}{2^{64}}\right\rfloor p= at - \left\lfloor\frac{as}{2^{64}}\right\rfloor p$$
In pseudocode, to find $x \bmod p$ for a 128-bit $x$
Variation assuming two functions
hi64(x,y)
andlo64(x,y)
that return the high and low 64 bits of the product of 64 bit integersx
andy
. If $p <2^{63}$, this version is guaranteed to never overflow using unsigned 64 bit arithmetic, sinceqb * p
can be at mostb
: