Reducción de Barrett

En aritmética modular , la reducción de Barrett es un algoritmo de reducción introducido en 1986 por PD Barrett. ^[1]

Una forma ingenua de calcular

${\displaystyle c=a\,{\bmod {\,}}n\,}$

Sería utilizar un algoritmo de división rápida . La reducción de Barrett es un algoritmo diseñado para optimizar esta operación suponiendo que es constante, y , reemplazando divisiones por multiplicaciones. ${\displaystyle n}$ ${\displaystyle a<n^{2}}$

Históricamente, para los valores , se calculaba aplicando la reducción de Barrett al producto completo . Recientemente, se demostró que el producto completo es innecesario si podemos realizar un cálculo previo en uno de los operandos. ^{[2] [3]} ${\displaystyle a,b<n}$ ${\displaystyle ab\,{\bmod {\,}}n\,}$ ${\displaystyle ab}$

Idea general

Llamamos a una función una 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 suelo , 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, típicamente una potencia de 2, elegida para que la multiplicación y la división por se puedan realizar de manera eficiente. ${\displaystyle R}$ ${\displaystyle R}$

El caso fue introducido por PD Barrett ^[1] para el caso de función de piso . El caso general para se puede encontrar en NTL . ^[2] La visión de aproximación de enteros y la correspondencia entre la multiplicación de Montgomery y la multiplicación de Barrett fue descubierta 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}$

Reducción de Barrett de una sola palabra

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

Al calcular números enteros sin signo, el análogo obvio sería utilizar 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 valor mínimo del resultado. return a - q * n }               

Sin embargo, la división puede ser costosa y, en entornos criptográficos, puede no ser una instrucción de tiempo constante en algunas CPU, lo que somete la operación a un ataque de tiempo . Por lo tanto, la reducción de Barrett se aproxima a un valor porque la división por es solo 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 determinado parámetro 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 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. 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 }$

Así podemos aproximar la función anterior con lo siguiente:

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

Sin embargo, dado que , el valor de en esa función puede terminar siendo uno más pequeño de lo que debería y, por lo tanto, solo se garantiza que esté dentro de los límites establecidos en lugar de como se requiere generalmente. 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 -= q * n si a >= n { a -= n } devuelve a }                           

Multiplicación de Barrett de una sola palabra

Supongamos que se conoce. Esto nos permite realizar un cálculo previo antes de recibir . La multiplicación de Barrett calcula , aproxima la parte alta 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}$

Correspondencia entre las multiplicaciones de Barrett y Montgomery

Recuerde 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}$

Probamos 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 de números enteros , 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]

Rango de multiplicación de Barrett

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)}$

Se aplican límites similares a otros tipos de funciones de aproximación de números enteros. Por ejemplo, si elegimos , la función de redondeo hacia arriba , 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 \left|{\frac {a{\frac {n}{2}}+{\frac {R}{2}}n}{R}}\right|={\frac {n}{2}}\left(1+{\frac {|a|}{R}}\right).}$

Reducción de Barrett de varias palabras

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 anterior pero para valores de múltiples palabras. Para obtener más detalles, consulte la sección 14.3.3 del Manual de criptografía aplicada . ^[4]

Algoritmo de Barrett para polinomios

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

Véase también

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

Referencias

1. Barrett, P. (1986). "Implementación del algoritmo de cifrado de clave pública Rivest Shamir y Adleman en un procesador de señal digital estándar". Avances en criptología – CRYPTO' 86. Apuntes de clase en informática. Vol. 263. págs. 311–323. doi :10.1007/3-540-47721-7_24. ISBN 978-3-540-18047-0.
2. Shoup, Victor. "Biblioteca de teoría de números".
3. Becker, Hanno; Hwang, Vincent; Kannwischer, Matthias J.; Yang, Bo-Yin; Yang, Shang-Yi (2021), "Neon NTT: dilitio, Kyber y Saber más rápidos en Cortex-A72 y Apple M1", Transactions on Cryptographic Hardware and Embedded Systems , 2022 (1): 221–244, doi : 10.46586/tches.v2022.i1.221-244
4. Menezes, Alfred; Oorschot, Paul; Vanstone, Scott (1997). Manual de criptografía aplicada (quinta edición). CRC Press. doi :10.1201/9780429466335. ISBN 0-8493-8523-7.
5. "Reducción de Barrett para polinomios". www.corsix.org . Consultado el 7 de septiembre de 2022 .

Fuentes

• Bosselaers, A.; Govaerts, R.; Vandewalle, J. (1993). "Comparación de tres funciones de reducción modular". En Stinson, Douglas R. (ed.). Avances en criptología – Crypto'93 . Apuntes de clase en informática. Vol. 773. Springer. págs. 175–186. CiteSeerX  10.1.1.40.3779 . ISBN. 3540483292.
• Hasenplaugh, W.; Gaubatz, G.; Gopal, V. (2007). "Reducción modular rápida" (PDF) . 18.º Simposio IEEE sobre aritmética informática (ARITH'07) . pp. 225–229. doi :10.1109/ARITH.2007.18. ISBN 978-0-7695-2854-0.S2CID14801112  .​