La multiplicación de Kochanski [1] es un algoritmo que permite que la aritmética modular (multiplicación u operaciones basadas en ella, como exponenciación ) se realice de manera eficiente cuando el módulo es grande (típicamente varios cientos de bits). Esto tiene una aplicación particular en la teoría de números y en criptografía : por ejemplo, en el criptosistema RSA y el intercambio de claves Diffie-Hellman .
La forma más común de implementar la multiplicación de enteros grandes en hardware es expresar el multiplicador en binario y enumerar sus bits, un bit a la vez, comenzando con el bit más significativo, realizar las siguientes operaciones en un acumulador :
- Duplique el contenido del acumulador (si el acumulador almacena números en binario, como suele ser el caso, se trata de un simple "desplazamiento a la izquierda" que no requiere ningún cálculo real).
- Si el bit actual del multiplicador es 1, agregue el multiplicando al acumulador; si es 0, no haga nada.
Para un multiplicador de n bits, esto tomará n ciclos de reloj (donde cada ciclo hace un cambio o un cambio y suma).
Para convertir esto en un algoritmo de multiplicación modular, con un módulo r , es necesario restar r condicionalmente en cada etapa:
- Duplica el contenido del acumulador.
- Si el resultado es mayor o igual que r , reste r . (De manera equivalente, reste r del acumulador y almacene el resultado nuevamente en el acumulador si y solo si no es negativo).
- Si el bit actual del multiplicador es 1, agregue el multiplicando al acumulador; si es 0, no haga nada.
- Si el resultado de la suma es mayor o igual que r , reste r . Si no se realizó ninguna adición, no haga nada.
Este algoritmo funciona. Sin embargo, depende críticamente de la velocidad de la suma.
La suma de enteros largos adolece del problema de que los acarreos tienen que propagarse de derecha a izquierda y el resultado final no se conoce hasta que no se ha completado este proceso. La propagación de acarreo se puede acelerar con la lógica de anticipación de acarreo , pero esto aún hace que la adición sea mucho más lenta de lo necesario (para la adición de 512 bits, la adición con anticipación de acarreo es 32 veces más lenta que la adición sin acarreos) .
La multiplicación no modular puede hacer uso de sumadores de acarreo , que ahorran tiempo al almacenar los acarreos de cada posición de dígito y usarlos más tarde: por ejemplo, calculando 111111111111 + 000000000010 como 111111111121 en lugar de esperar a que el acarreo se propague por todo número para obtener el valor binario verdadero 1000000000001. Esa propagación final aún debe realizarse para obtener un resultado binario, pero esto solo debe hacerse una vez al final de la multiplicación.
Desafortunadamente, el método de multiplicación modular descrito anteriormente necesita conocer la magnitud del valor acumulado en cada paso, para decidir si restar r : por ejemplo, si necesita saber si el valor en el acumulador es mayor que 1000000000000, el acarreo La representación -save 111111111121 es inútil y debe convertirse a su valor binario verdadero para que se realice la comparación.
Por lo tanto, parece que uno puede tener o bien la velocidad de arrastre de ahorro o de multiplicación modular, pero no ambos.
Esquema del algoritmo
El principio del algoritmo de Kochanski consiste en hacer conjeturas sobre si se debe restar r o no , basándose en los pocos bits más significativos del valor de acarreo-ahorro en el acumulador. Tal suposición será incorrecta en algunas ocasiones, ya que no hay forma de saber si los portadores latentes en los dígitos menos significativos (que no han sido examinados) podrían no invalidar el resultado de la comparación. Por lo tanto:
- Es posible que no se haya hecho una resta cuando se requirió. En ese caso, el resultado en el acumulador es mayor que r (aunque el algoritmo aún no lo sabe), por lo que después del siguiente desplazamiento a la izquierda, será necesario restar 2 r del acumulador.
- Es posible que se haya hecho una resta cuando no era necesaria. En ese caso, el resultado en el acumulador es menor que 0 (aunque el algoritmo aún no lo sabe), por lo que después del siguiente cambio a la izquierda, será necesario volver a agregar r o incluso 2 r al acumulador para que sea positivo. de nuevo.
Lo que está sucediendo es esencialmente una carrera entre los errores que resultan de las suposiciones incorrectas, que se duplican con cada cambio que queda, y las correcciones que se realizan al sumar o restar múltiplos de r basándose en una suposición de cuáles pueden ser los errores.
Resulta [2] que examinar los 4 bits más significativos del acumulador es suficiente para mantener los errores dentro de los límites y que los únicos valores que deben agregarse al acumulador son −2 r , - r , 0, + r , y +2 r , todos los cuales pueden generarse instantáneamente mediante simples cambios y negaciones.
Al final de una multiplicación modular completa, se debe evaluar el verdadero resultado binario de la operación y es posible que se necesite una suma o resta adicional de r como resultado de los acarreos que luego se descubren; pero el costo de ese paso adicional es pequeño cuando se amortiza en los cientos de pasos de cambio y suma que dominan el costo general de la multiplicación.
Alternativas
Brickell [3] ha publicado un algoritmo similar que requiere una mayor complejidad en la electrónica para cada dígito del acumulador.
La multiplicación de Montgomery es un algoritmo alternativo que procesa el multiplicador "hacia atrás" (primero el dígito menos significativo) y utiliza el dígito menos significativo del acumulador para controlar si se debe agregar o no el módulo. Esto evita la necesidad de que se propaguen los acarreos. Sin embargo, el algoritmo no es práctico para multiplicaciones modulares simples, ya que se deben realizar dos o tres pasos adicionales de Montgomery para convertir los operandos en una forma especial antes del procesamiento y convertir el resultado de nuevo en binario convencional al final.
Referencias
- ^ Kochanski, Martin J. (1985). "Desarrollando un Chip RSA". Avances en criptología: Actas de CRYPTO 85 . Berlín: Springer-Verlag. págs. 350–357. doi : 10.1007 / 3-540-39799-X_25 . ISBN 3-540-16463-4.
- ^ Kochanski, Martin J. (19 de agosto de 2003). "Un nuevo método de multiplicación modular en serie" (PDF) . Archivado desde el original (PDF) el 16 de julio de 2018. Describe el algoritmo con todo detalle.
- ^ Brickell, Ernest F. (1983). "Un algoritmo de multiplicación modular rápido con aplicaciones a la criptografía de dos claves". Avances en criptología: Actas de CRYPTO '82 . Nueva York: Pleno. págs. 51–60. doi : 10.1007 / 978-1-4757-0602-4_5 . ISBN 0-306-41366-3.
- Kochanski, Martin. "Creando el Chip FAP4" . Archivado desde el original el 9 de mayo de 2018. Explicación informal y motivación del algoritmo, con detalles de una implementación de hardware real.