Reducción de Barrett: ¿es posible sin desbordamiento ni aritmética de coma flotante?

Question

Tengo dos variables, $x$ y $y$ . Busco calcular el producto de $x$ y $y$ modulo $p$ , donde $p$ es primo.

Para valores pequeños de $x$ y $y$ (menos de 43 bits cada uno), pude realizar el cálculo utilizando Reducción de Barrett .

Sin embargo, para grandes valores de $x$ y $y$ Si se produce un desbordamiento que supera los 128 bits, el valor calculado es incorrecto. Esto se debe a que $x$ y $y$ deben multiplicarse entre sí, lo que debe almacenarse en un tipo de datos de 128 bits. A continuación, ese producto debe multiplicarse por una constante precalculada, $r$ , dando como resultado un valor que puede ser almacenado en 192 bits.

¿Es posible calcular xy mod p utilizando la Reducción de Barrett donde el desbordamiento de más de 128 bits no ¿también sin depender de la aritmética de punto flotante?

Si ayuda, tengo la capacidad de realizar la multiplicación de $x$ y $y$ y almacenar el producto en dos variables: $a$ y $b$ , donde $a$ contiene los 64 bits altos del producto, y $b$ contiene los 64 bits inferiores del producto.

Answer 1

Sí, pero además de $r = \left\lfloor \dfrac{2^{64}}p\right\rfloor$ También necesitará $$s =\left\lfloor \dfrac{2^{128}}p\right\rfloor - 2^{64}r$$ y $$t = 2^{64} - rp$$ Tenga en cuenta que $s,t < 2^{64}$ .

Así que tienes $xy = a2^{64} + b$ . Entonces $$\begin{align}xy \bmod p &= (a2^{64} + b) \bmod p\\&= \big[(a2^{64}\bmod p) + (b\bmod p)\big]\bmod p\end{align}$$

Según el algoritmo de Barrett, para calcular $a2^{64}\bmod p$ , primero se calcula $$q = \left\lfloor\dfrac {a2^{64}(2^{24}r + s)}{2^{128}}\right\rfloor = ar + \left\lfloor\frac{as}{2^{64}}\right\rfloor$$

El módulo aproximado es entonces $$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$$

En pseudocódigo, para encontrar $x \bmod p$ para una versión de 128 bits $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

Variación asumiendo dos funciones hi64(x,y) y lo64(x,y) que devuelven los 64 bits altos y bajos del producto de enteros de 64 bits x y y . Si $p <2^{63}$ esta versión está garantizada para no desbordarse nunca usando aritmética de 64 bits sin signo, ya que qb * p puede ser como máximo 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