Reducción de Barrett

En aritmética modular , la reducción de Barrett es un algoritmo diseñado para optimizar el cálculo de ^{[ 1 ]} sin necesidad de un algoritmo de división rápido . Reemplaza las divisiones con multiplicaciones y puede utilizarse cuando es constante y . Fue introducido en 1986 por P. D. Barrett. ^{[ 2 ]}${\displaystyle a\,{\bmod {\,}}n\,}$${\displaystyle n}$${\displaystyle a<n^{2}}$

Históricamente, para valores , se calculaba aplicando la reducción de Barrett al producto completo . En 2021, Becker et al. demostraron que el producto completo es innecesario si podemos realizar un preprocesamiento en uno de los operandos. ^{[ 3 ]}${\displaystyle a,b<n}$${\displaystyle ab\,{\bmod {\,}}n\,}$${\displaystyle ab}$

Llamamos a una función aproximación entera si . Para un módulo y una aproximación entera , definimos como ${\displaystyle \left[\,\right]:\mathbb {R} \to \mathbb {Z} }$${\displaystyle |\left[z\right]-z|\leq 1}$${\displaystyle n}$${\displaystyle \left[\,\right]}$${\displaystyle {\text{mod}}^{\left[\,\right]}\,n:\mathbb {Z} \to (\mathbb {Z} /n\mathbb {Z} )}$

${\displaystyle a\,{\text{mod}}^{\left[\,\right]}\,n=a-\left[a/n\right]n}$.

Las opciones más comunes son las funciones de piso , techo y redondeo . ${\displaystyle \left[\,\right]}$

Generalmente, la multiplicación de Barrett comienza especificando dos aproximaciones enteras y calcula una aproximación razonablemente cercana de como ${\displaystyle \left[\,\right]_{0},\left[\,\right]_{1}}$${\displaystyle ab\,{\bmod {\,}}n}$

${\displaystyle ab-\left[{\frac {a\,\left[{\frac {bR}{n}}\right]_{0}}{R}}\right]_{1}n}$,

donde es una constante fija, normalmente una potencia de 2, elegida de manera que la multiplicación y la división por se puedan realizar de forma eficiente. ${\displaystyle R}$${\displaystyle R}$

El caso fue introducido por PD Barrett ^{[ 2 ]} para el caso de la función piso . El caso general para se puede encontrar en NTL . ^{[ 4 ]} La vista de aproximación entera y la correspondencia entre la multiplicación de Montgomery y la multiplicación de Barrett fueron descubiertas por Hanno Becker, Vincent Hwang, Matthias J. Kannwischer, Bo-Yin Yang y Shang-Yi Yang. ^{[ 3 ]}${\displaystyle b=1}$${\displaystyle \left[\,\right]_{0}=\left[\,\right]_{1}=\lfloor \,\rfloor }$${\displaystyle b}$

Barrett consideró inicialmente una versión entera del algoritmo anterior cuando los valores cabían en palabras de máquina. Ilustramos la idea para el caso de la función piso con y . ${\displaystyle b=1}$${\displaystyle R=2^{k}}$

Al realizar cálculos con enteros sin signo, el análogo obvio sería usar la división por : ${\displaystyle a\,{\bmod {\,}}n}$${\displaystyle n}$

func reduce ( a uint ) uint { q := a / n // La división devuelve implícitamente el redondeo hacia abajo del resultado. return a - q * n }

Sin embargo, la división puede ser costosa y, en entornos criptográficos, podría no ser una instrucción de tiempo constante en algunas CPU, lo que expone la operación a un ataque de temporización . Por lo tanto, la reducción de Barrett se aproxima con un valor porque la división por es simplemente un desplazamiento a la derecha, y por lo tanto es barata. ${\displaystyle 1/n}$${\displaystyle m/2^{k}}$${\displaystyle 2^{k}}$

Para calcular el mejor valor para un valor dado , considere lo siguiente: ${\displaystyle m}$${\displaystyle 2^{k}}$

${\displaystyle {\frac {m}{2^{k}}}={\frac {1}{n}}\;\Longleftrightarrow \;m={\frac {2^{k}}{n}}}$

Para que sea un número entero, necesitamos redondearlo de alguna manera. Redondear al entero más cercano dará la mejor aproximación, pero puede resultar en un valor mayor que , lo que puede causar desbordamientos negativos. Por lo tanto, se utiliza para aritmética sin signo. ${\displaystyle m}$${\displaystyle {2^{k}}/{n}}$${\displaystyle m/2^{k}}$${\displaystyle 1/n}$${\displaystyle m=\lfloor {2^{k}}/{n}\rfloor }$

Por lo tanto, podemos aproximar la función anterior con lo siguiente:

func reduce ( a uint ) uint { q := ( a * m ) >> k // ">> k" denota desplazamiento de bits en k. return a - q * n }

Sin embargo, dado que , el valor de en esa función puede terminar siendo uno demasiado pequeño, y por lo tanto solo se garantiza que esté dentro de en lugar de como generalmente se requiere. Una resta condicional corregirá esto: ${\displaystyle m/2^{k}\leq 1/n}$qa${\displaystyle [0,2n)}$${\displaystyle [0,n)}$

func reduce ( a uint ) uint { q := ( a * m ) >> k a := a - q * n if a >= n { a := a - n } return a }

Supongamos que se conoce. Esto nos permite precalcular antes de recibir . La multiplicación de Barrett calcula , aproxima la parte superior de con , y resta la aproximación. Como es un múltiplo de , el valor resultante es un representante de . ${\displaystyle b}$${\displaystyle \left\lfloor {\frac {bR}{n}}\right\rfloor }$${\displaystyle a}$${\displaystyle ab}$${\displaystyle ab}$${\displaystyle \left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n}$${\displaystyle \left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n}$${\displaystyle n}$${\displaystyle ab-\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n}$${\displaystyle ab\,{\bmod {\,}}n}$

Recordemos que la multiplicación de Montgomery sin signo calcula un representante de como ${\displaystyle ab\,{\bmod {\,}}n}$

${\displaystyle {\frac {a\left(bR\,{\bmod {\,}}n\right)+\left(a\left(-bR\,{\bmod {\,}}n\right)n^{-1}\,{\bmod {\,}}R\right)n}{R}}}$.

De hecho, este valor es igual a . ${\displaystyle ab-\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n}$

Demostramos la afirmación de la siguiente manera.

${\displaystyle {\begin{aligned}&&&ab-\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n\\&=&&ab-{\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor -\left(a\left\lfloor {\frac {bR}{n}}\right\rfloor \,{\bmod {\,}}R\right)}{R}}\,n\\&=&&\left({\frac {abR}{n}}-a\left\lfloor {\frac {bR}{n}}\right\rfloor +\left(a\left\lfloor {\frac {bR}{n}}\right\rfloor \,{\bmod {\,}}R\right)\right){\frac {n}{R}}\\&=&&\left({\frac {abR}{n}}-a{\frac {bR-\left(bR\,{\bmod {\,}}n\right)}{n}}+\left(a\left\lfloor {\frac {bR}{n}}\right\rfloor \,{\bmod {\,}}R\right)\right){\frac {n}{R}}\\&=&&\left({\frac {a\left(bR\,{\bmod {\,}}n\right)}{n}}+\left(a\left\lfloor {\frac {bR}{n}}\right\rfloor \,{\bmod {\,}}R\right)\right){\frac {n}{R}}\\&=&&\left({\frac {a\left(bR\,{\bmod {\,}}n\right)}{n}}+\left(a\left(-bR\,{\bmod {\,}}n\right)n^{-1}\,{\bmod {\,}}R\right)\right){\frac {n}{R}}\\&=&&{\frac {a\left(bR\,{\bmod {\,}}n\right)+\left(a\left(-bR\,{\bmod {\,}}n\right)n^{-1}\,{\bmod {\,}}R\right)n}{R}}.\end{aligned}}}$

Generalmente, para aproximaciones enteras , tenemos ${\displaystyle \left[\,\right]_{0},\left[\,\right]_{1}}$

${\displaystyle ab-\left[{\frac {a\,\left[{\frac {bR}{n}}\right]_{0}}{R}}\right]_{1}\,n={\frac {a\left(bR\,{\text{mod}}^{\left[\,\right]_{0}}\,n\right)+\left(a\left(-bR\,{\text{mod}}^{\left[\,\right]_{0}}\,q\right)n^{-1}\,{\text{mod}}^{\left[\,\right]_{1}}\,R\right)n}{R}}}$. ^{[ 3 ]}

Limitamos la salida con

${\displaystyle ab-\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rfloor }{R}}\right\rfloor \,n={\frac {a\left(bR\,{\bmod {\,}}n\right)+\left(a\left(-bR\,{\bmod {\,}}n\right)n^{-1}\,{\bmod {\,}}R\right)n}{R}}\leq {\frac {an+Rn}{R}}=n\left(1+{\frac {a}{R}}\right)}$.

Límites similares se aplican a otros tipos de funciones de aproximación entera. Por ejemplo, si elegimos , la función de redondeo al alza , entonces tenemos ${\displaystyle \left[\,\right]_{0}=\left[\,\right]_{1}=\left\lfloor \,\right\rceil }$

${\displaystyle \left|ab-\left\lfloor {\frac {a\left\lfloor {\frac {bR}{n}}\right\rceil }{R}}\right\rceil \,n\right|=\left|{\frac {a\left(bR\,{\text{mod}}^{\pm }\,n\right)+\left(a\left(-bR\,{\text{mod}}^{\pm }\,n\right)n^{-1}\,{\text{mod}}^{\pm }\,R\right)n}{R}}\right|\leq {\frac {|a|{\frac {n}{2}}+{\frac {R}{2}}n}{R}}={\frac {n}{2}}\left(1+{\frac {|a|}{R}}\right).}$

Es común seleccionar R de tal manera que (o en el   caso de) para que la salida permanezca dentro de y ( y respectivamente), y por lo tanto solo se realiza una verificación para obtener el resultado final entre y . Además, se puede omitir la verificación y realizarla una sola vez al final de un algoritmo a costa de mayores entradas a las operaciones aritméticas de campo. ${\displaystyle {\frac {a}{R}}<1}$${\displaystyle {\frac {\left|a\right|}{R}}<1}$${\displaystyle \left[\,\right]_{0}=\left[\,\right]_{1}=\left\lfloor \,\right\rceil }$${\displaystyle 0}$${\displaystyle 2n}$${\displaystyle -n}$${\displaystyle n}$${\displaystyle 0}$${\displaystyle n}$

La multiplicación de Barrett descrita anteriormente requiere un operando constante b que debe precalcularse . De lo contrario, la operación no es eficiente. Es común usar la multiplicación de Montgomery cuando ambos operandos no son constantes, ya que ofrece un mejor rendimiento. Sin embargo, la multiplicación de Montgomery requiere una conversión hacia y desde el dominio de Montgomery, lo que implica un alto costo computacional cuando se necesitan pocas multiplicaciones modulares. ${\displaystyle \left[{\frac {bR}{n}}\right]_{0}}$

Para realizar la multiplicación de Barrett con operandos no constantes, se puede establecer como el producto de los operandos y establecer en . Esto conduce a ${\displaystyle a}$${\displaystyle b}$${\displaystyle 1}$

${\displaystyle a-\left[{\frac {a\,\left[{\frac {R}{n}}\right]_{0}}{R}}\right]_{1}\,n={\frac {a\left(R\,{\text{mod}}^{\left[\,\right]_{0}}\,n\right)+\left(a\left(-R\,{\text{mod}}^{\left[\,\right]_{0}}\,q\right)n^{-1}\,{\text{mod}}^{\left[\,\right]_{1}}\,R\right)n}{R}}}$

Una comprobación rápida de los límites arroja lo siguiente en caso ${\displaystyle \left[\,\right]_{0}=\left[\,\right]_{1}=\left\lfloor \,\right\rfloor }$

${\displaystyle {\begin{aligned}a-\left\lfloor {\frac {a\,\left\lfloor {\frac {R}{n}}\right\rfloor }{R}}\right\rfloor \,n&={\frac {a\left(R\,{\bmod {\,}}n\right)+\left(a\left(-R\,{\bmod {\,}}n\right)n^{-1}\,{\bmod {\,}}R\right)n}{R}}\\&\leq {\frac {a(R\,{\bmod {\,}}n)+Rn}{R}}=n\left(1+{\frac {a(R\,{\bmod {\,}}n)}{Rn}}\right)\end{aligned}}}$

y lo siguiente en caso ${\displaystyle \left[\,\right]_{0}=\left[\,\right]_{1}=\left\lfloor \,\right\rceil }$

${\displaystyle {\begin{aligned}\left|a-\left\lfloor {\frac {a\left\lfloor {\frac {R}{n}}\right\rceil }{R}}\right\rceil \,n\right|&=\left|{\frac {a\left(R\,{\text{mod}}^{\pm }\,n\right)+\left(a\left(-R\,{\text{mod}}^{\pm }\,n\right)n^{-1}\,{\text{mod}}^{\pm }\,R\right)n}{R}}\right|\\&\leq {\frac {|a(R\,{\text{mod}}^{\pm }\,n)|+{\frac {R}{2}}n}{R}}={\frac {n}{2}}\left(1+{\frac {|a(R\,{\text{mod}}^{\pm }\,n)|}{Rn}}\right)\end{aligned}}}$

La configuración siempre producirá una comprobación en la salida. Sin embargo, podría ser posible una restricción más estricta en ya que es una constante que a veces es significativamente menor que . ${\displaystyle R>|a|}$${\displaystyle R}$${\displaystyle R\,{\text{mod}}^{\left[\,\right]_{0}}\,n}$${\displaystyle n}$

Surge un pequeño problema al realizar el siguiente producto, ya que es un producto de dos operandos. Suponiendo que cabe en bits, entonces cabría en bits y cabría en bits. Su producto requeriría una multiplicación, lo que podría requerir fragmentación en sistemas que no pueden realizar el producto en una sola operación. ${\displaystyle a\,\left[{\frac {R}{n}}\right]_{0}}$${\displaystyle a}$${\displaystyle n}$${\displaystyle w}$${\displaystyle a}$${\displaystyle 2w}$${\displaystyle \left[{\frac {R}{n}}\right]_{0}}$${\displaystyle w}$${\displaystyle 2w\times w}$

Un enfoque alternativo consiste en realizar la siguiente reducción de Barrett:

${\displaystyle a-\left[{\frac {\left[{\frac {a}{R_{0}}}\right]_{2}\,\left[{\frac {R}{n}}\right]_{0}}{R_{1}}}\right]_{1}\,n={\frac {a\left(R\,{\text{mod}}^{\left[\,\right]_{0}}\,n\right)+\left(a\,{\text{mod}}^{\left[\,\right]_{2}}\,R_{0}\right)\left(R-R\,{\text{mod}}^{\left[\,\right]_{0}}\,n\right)+\left(\left[{\frac {a}{R_{0}}}\right]_{2}\,\left[{\frac {R}{n}}\right]_{0}\,{\text{mod}}^{\left[\,\right]_{1}}\,R_{1}\right)R_{0}n}{R}}}$

donde , , , y es la longitud en bits de . ${\displaystyle R_{0}=2^{k-\beta }}$${\displaystyle R_{1}=2^{\alpha +\beta }}$${\displaystyle R=R_{0}\cdot R_{1}=2^{k+\alpha }}$${\displaystyle k}$${\displaystyle n}$

La comprobación de límites en este caso produce lo siguiente: ${\displaystyle \left[\,\right]_{0}=\left[\,\right]_{1}=\left[\,\right]_{2}=\left\lfloor \,\right\rfloor }$

${\displaystyle {\begin{aligned}a-\left\lfloor {\frac {\left\lfloor {\frac {a}{R_{0}}}\right\rfloor \,\left\lfloor {\frac {R}{n}}\right\rfloor }{R_{1}}}\right\rfloor \,n&\leq {\frac {a\left(R\,{\bmod {\,}}n\right)+R_{0}R-R_{0}\left(R\,{\bmod {\,}}n\right)+Rn}{R}}\\&=n\left(1+{\frac {a(R\,{\bmod {\,}}n)}{Rn}}+{\frac {R_{0}}{n}}-{\frac {R\,{\bmod {\,}}n}{R_{1}n}}\right)\end{aligned}}}$

y para este caso se obtiene lo siguiente ${\displaystyle \left[\,\right]_{0}=\left[\,\right]_{1}=\left[\,\right]_{2}=\left\lfloor \,\right\rceil }$

${\displaystyle {\begin{aligned}\left|a-\left\lfloor {\frac {\left\lfloor {\frac {a}{R_{0}}}\right\rceil \left\lfloor {\frac {R}{n}}\right\rceil }{R_{1}}}\right\rceil \,n\right|&\leq {\frac {|a\left(R\,{\text{mod}}^{\pm }\,n\right)|+R_{0}R/2+R_{0}|(R\,{\text{mod}}^{\pm }\,n)|/2+Rn/2}{R}}\\&={\frac {n}{2}}\left(1+{\frac {2|a(R\,{\text{mod}}^{\pm }\,n)|}{Rn}}+{\frac {R_{0}}{n}}+{\frac {|R\,{\text{mod}}^{\pm }\,n|}{R_{1}n}}\right)\end{aligned}}}$

Para cualquier módulo y suponiendo , el límite dentro del paréntesis en ambos casos es menor o igual que: ${\displaystyle |a|<2^{k+\gamma }}$

${\displaystyle 1+{\frac {(2^{k+\gamma })(n)}{(2^{k+\alpha })(n)}}+{\frac {2^{k-\beta }}{n}}+\epsilon \leq 1+{\frac {2^{k+\gamma }}{2^{k+\alpha }}}+{\frac {2^{k-\beta }}{2^{k-1}}}+\epsilon =1+2^{\gamma -\alpha }+2^{1-\beta }+\epsilon }$

donde en el caso y en el caso. ${\displaystyle \epsilon =-{\frac {1}{R_{1}}}}$${\displaystyle \left\lfloor \,\right\rfloor }$${\displaystyle \epsilon ={\frac {1}{2R_{1}}}}$${\displaystyle \left\lfloor \,\right\rceil }$

Establecer y (o en el caso) siempre producirá una comprobación. En algunos casos, probar los límites podría producir valores más bajos de y/o . ${\displaystyle \beta =2}$${\displaystyle \alpha =\gamma +1}$${\displaystyle \alpha =\gamma +2}$${\displaystyle \left\lfloor \,\right\rceil }$${\displaystyle \alpha }$${\displaystyle \beta }$

Es posible realizar una reducción de Barrett con una multiplicación menos de la siguiente manera:

${\displaystyle a-\left[{\frac {a}{R}}\right]_{1}\,n}$ donde y es la longitud en bits de${\displaystyle R=2^{k}}$${\displaystyle k}$${\displaystyle n}$

Todo módulo puede escribirse en la forma para algún entero . ${\displaystyle n=2^{k}-c=R-c}$${\displaystyle c}$

${\displaystyle {\begin{aligned}a-\left[{\frac {a}{R}}\right]_{1}\,n&=a-{\frac {a-(a\,{\text{mod}}^{\left[\,\right]_{1}}\,R)}{R}}n\\&={\frac {aR-an+(a\,{\text{mod}}^{\left[\,\right]_{1}}\,R)n}{R}}\\&={\frac {ac+(a\,{\text{mod}}^{\left[\,\right]_{1}}\,R)n}{R}}\\&=n\left({\frac {a\,{\text{mod}}^{\left[\,\right]_{1}}\,R}{R}}+{\frac {ac}{Rn}}\right)\\&=n\left({\frac {a\,{\text{mod}}^{\left[\,\right]_{1}}\,R}{R}}+{\frac {a}{{\frac {R^{2}}{c}}-R}}\right)\end{aligned}}}$

Por lo tanto, reducir cualquier for o cualquier for produce un cheque. ${\displaystyle a<{\frac {R^{2}}{c}}-R}$${\displaystyle \left[\,\right]_{1}=\left\lfloor \,\right\rfloor }$${\displaystyle |a|<\left({\frac {R^{2}}{c}}-R\right)/\,2}$${\displaystyle \left[\,\right]_{1}=\left\lfloor \,\right\rceil }$

Del análisis de la restricción, se puede observar que el límite de es mayor cuando es menor. En otras palabras, el límite es mayor cuando está más cerca de . ${\displaystyle a}$${\displaystyle c}$${\displaystyle n}$${\displaystyle R}$

La reducción de Barrett se puede utilizar para calcular la división por piso, redondo o techo sin realizar costosas divisiones largas. Además, se puede utilizar para calcular . Después de precalcular las constantes, los pasos son los siguientes: ${\displaystyle \left[{\frac {a}{n}}\right]}$${\displaystyle \left[{\frac {ab}{n}}\right]}$

1. Calcula el cociente aproximado .${\displaystyle {\tilde {q}}=\left[{\frac {a\,\left[{\frac {bR}{n}}\right]_{0}}{R}}\right]_{1}}$
2. Calcula el resto de Barrett .${\displaystyle {\tilde {r}}=ab-{\tilde {q}}n}$
3. Calcula el error del cociente donde . Esto se hace restando un múltiplo de a hasta que se obtenga.${\displaystyle e=({\tilde {r}}-r)/n}$${\displaystyle r=a\,{\text{mod}}^{\left[\,\right]}\,n}$${\displaystyle n}$${\displaystyle {\tilde {r}}}$${\displaystyle r}$
4. Calcula el cociente .${\displaystyle q={\tilde {q}}+e}$

Si las restricciones para la reducción de Barrett se eligen de manera que haya una sola verificación, entonces el valor absoluto de en el paso 3 no puede ser mayor que 1. Usando y restricciones apropiadas, el error se puede obtener a partir del signo de . ${\displaystyle e}$${\displaystyle \left[\,\right]_{0}=\left[\,\right]_{1}=\left\lfloor \,\right\rceil }$${\displaystyle e}$${\displaystyle {\tilde {r}}}$

La principal motivación de Barrett para considerar la reducción fue la implementación de RSA , donde los valores en cuestión casi con certeza excederán el tamaño de una palabra de máquina. En esta situación, Barrett proporcionó un algoritmo que se aproxima a la versión de una sola palabra mencionada anteriormente, pero para valores de varias palabras. Para más detalles, consulte la sección 14.3.3 del Manual de Criptografía Aplicada . ^{[ 5 ]}

También es posible utilizar el algoritmo de Barrett para la división de polinomios, invirtiendo los polinomios y utilizando aritmética X-ádica. ^{[ 6 ]}

• La reducción de Montgomery es otro algoritmo similar.