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 computació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 asumiendo es constante, y , reemplazando divisiones por multiplicaciones.
Idea general
Dejar ser el inverso de como un número de coma flotante . Luego
dónde denota la función de piso . El resultado es exacto, siempre que se calcula con suficiente precisión.
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.
Al calcular usando el método anterior, pero con números enteros, el análogo obvio sería usar la división por :
func reduce ( a uint ) uint { q : = a / n // La división devuelve implícitamente el piso del resultado. devuelve a - q * n }
Sin embargo, la división puede ser costosa y, en configuraciones criptográficas, puede no ser una instrucción de tiempo constante en algunas CPU. Por tanto, la reducción de Barrett se aproxima con un valor porque la división por es solo un cambio a la derecha y, por lo tanto, es barato.
Para calcular el mejor valor para dado considerar:
Para poder para ser un número entero, necesitamos redondear de algun modo. Redondear al entero más cercano dará la mejor aproximación, pero puede resultar en siendo más grande que , que puede provocar subdesbordamientos. Por lo tanto se utiliza generalmente.
Por lo tanto, podemos aproximar la función anterior con:
func reduce ( a uint ) uint { q : = ( a * m ) >> k // ">> k" denota desplazamiento de bits por k. devuelve a - q * n }
Sin embargo, desde , el valor de q
en esa función puede terminar siendo demasiado pequeño y, por lo tanto, a
solo se garantiza que esté dentro de en vez de como se requiere generalmente. Una resta condicional corregirá esto:
func reduce ( a uint ) uint { q : = ( a * m ) >> k a - = q * n if n <= a { a - = n } return a }
Desde es sólo una aproximación, el rango válido de necesita ser considerado. El error de la aproximación de es:
Por tanto, el error en el valor de q
es. Mientras entonces la reducción es válida así . Es posible que la función de reducción no dé inmediatamente una respuesta incorrecta cuando pero los límites en debe ser respetado para asegurar la respuesta correcta en el caso general.
Al elegir valores mayores de , el rango de valores de para los que la reducción es válida se puede incrementar, pero valores mayores de puede causar problemas de desbordamiento en otros lugares.
Ejemplo
Considere el caso de cuando se opera con enteros de 16 bits.
El valor más pequeño de eso tiene sentido es porque si ¡entonces la reducción solo será válida para valores que ya son mínimos! Por un valor de siete,. Por un valor de ocho. Por lo tanto no proporciona ninguna ventaja porque la aproximación de en ese caso () es exactamente igual que . Para, obtenemos , que es una mejor aproximación.
Ahora consideramos los rangos de entrada válidos para y . En el primer caso, entonces implica . Desde es un número entero, efectivamente el valor máximo es 478. (En la práctica, la función funciona para valores hasta 504.)
Si tomamos luego y así el valor máximo de es 7387. (En la práctica, la función funciona hasta 7473.)
El siguiente valor de que da como resultado una mejor aproximación es 13, dando . Sin embargo, tenga en cuenta que el valor intermedio en el cálculo desbordará un valor de 16 bits sin firmar cuando , por lo tanto funciona mejor en esta situación.
Prueba de rango para un k específico
Dejar ser el número entero más pequeño tal que . Llevar como un valor razonable para en las ecuaciones anteriores. Como en los fragmentos de código anteriores, deje
- y
- .
Debido a la función de piso , es un número entero y . También si luego . En ese caso, escriba los fragmentos de arriba como una expresión:
La prueba de que sigue:
Si , luego
Desde a pesar de , resulta que
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 excederán casi con certeza 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 varias palabras. Para obtener más información, consulte la sección 14.3.3 del Manual de criptografía aplicada . [2]
Ver también
- La reducción de Montgomery es otro algoritmo similar.
Referencias
- ^ 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 conferencias en Ciencias de la Computación. 263 . págs. 311–323. doi : 10.1007 / 3-540-47721-7_24 . ISBN 978-3-540-18047-0.
- ^ Menezes, Alfred; Oorschot, Paul; Vanstone, Scott (1997). Manual de criptografía aplicada . ISBN 0-8493-8523-7.
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 conferencias en Ciencias de la Computación. 773 . Saltador. 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) . págs. 225–9. doi : 10.1109 / ARITH.2007.18 . ISBN 978-0-7695-2854-0. S2CID 14801112 .