4
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ How large is $p$? Is it greater than $43$ bits? $\endgroup$ Commented Nov 29, 2019 at 2:33
  • $\begingroup$ @DavidK $p$ won't exceed 64 bits. $\endgroup$ Commented Nov 29, 2019 at 2:34
  • $\begingroup$ The obvious first step is to take x mod p and y mod p before doing the multiplication--but if $p$ is larger than both $x$ and $y$, that won't help. $\endgroup$ Commented Nov 29, 2019 at 2:49
  • $\begingroup$ @DavidK Yes, $p$ is already larger than both $x$ and $y$. $\endgroup$ Commented Nov 29, 2019 at 2:50
  • $\begingroup$ So the overflow you mention occurs only when you multiply by $r$? $\endgroup$ Commented Nov 29, 2019 at 3:30

1 Answer 1

Reset to default
4
$\begingroup$

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$

function Mod128(x, p) a = x >> 64 b = x - (a << 64) qa = a * s >> 64 qb = b * r >> 64 a1 = a * t - qa * p if a1 >= p then a1 = a1 - p b1 = b - qb * p if b1 >= p then b1 = b1 - p x1 = a1 + b1 if x1 >= p then x1 = x1 - p return x1

Variation assuming two functions hi64(x,y) and lo64(x,y) that return the high and low 64 bits of the product of 64 bit integers x and y. If $p <2^{63}$, this version is guaranteed to never overflow using unsigned 64 bit arithmetic, since qb * p can be at most b:

function ModProd(x,y,p) a = hi64(x,y) b = lo64(x,y) qa = hi64(a,s) qb = hi64(b,r) at = lo64(a,t) qap = lo64(qa,p) if at < qap then a1 = (2^63 - qap) + 2^63 + at else a1 = at - qap if a1 >= p then a1 = a1 - p b1 = b - qb * p if b1 >= p then b1 = b1 - p prod = a1 + b1 if prod >= p then prod = prod - p return prod
$\endgroup$
7
  • 1
    $\begingroup$ Thanks for the answer. How would the pseudocode change if x was stored in two 64-bit variables instead? One variable would be the high 64 bits of the product, and the other would be the low 64 bits. $\endgroup$ Commented Nov 29, 2019 at 16:49
  • 1
    $\begingroup$ The first two lines divide $x$ up into the high 64 bits $a$ and low 64 bits $b$. Everything after that is in 64 bits (except the products before the >> 64 shift is applied - but that is just taking the high 64 bits of that product) $\endgroup$ Commented Nov 29, 2019 at 16:52
  • 1
    $\begingroup$ I added a version that uses only 64 bit arithmetic, except for two functions for returning the high and low 64 bits of products. $\endgroup$ Commented Nov 29, 2019 at 16:58
  • 1
    $\begingroup$ Much appreciated. I’ll be able to verify that everything works in a couple hours, and then I’ll be happy to accept this answer. Thanks again! $\endgroup$ Commented Nov 29, 2019 at 17:02
  • 1
    $\begingroup$ Actually, it needed a little more cleaning before I can claim it is 64-bit arithmetic only, as a * t and qa * p are not guaranteed to be below 2^64. However, since their difference is guaranteed to be so(assuming $2p <2^{64}$), the high 64 bits must be the same, and can be discarded. $\endgroup$ Commented Nov 29, 2019 at 17:16

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.