Algoritmo de Schönhage-Strassen

El método de multiplicación de Schönhage-Strassen ( ing.  Algoritmo de Schönhage-Strassen ) es un algoritmo para multiplicar números enteros grandes basado en la transformada rápida de Fourier , requiere ) operaciones de bits, donde es el número de dígitos binarios en el producto [1] .

Inventado por Arnold Schönhage y Volker Strassen en 1971 [2] .

De hecho, es un método para multiplicar polinomios de una variable, se convierte en un algoritmo para multiplicar números, si estos números se representan como polinomios desde la base del sistema numérico y, después de recibir el resultado, se transfieren a través de los dígitos. Por ejemplo, para multiplicar 157 y 171 (en notación decimal), se realizan las siguientes operaciones:

• se representa como , y  como , donde ;
• los polinomios se multiplican y usando la transformada rápida de Fourier , el resultado es ;
• se aplican guiones a dígitos:, es decir, .

También en el algoritmo, puedes multiplicar números de módulo Fermat , si usas el sistema numérico binario .

El método fue considerado el método asintóticamente más rápido desde 1971 hasta 2007, cuando se inventó el algoritmo Führer con una mejor estimación de la complejidad [3] . En la práctica, el método de Schönhage-Strassen comienza a superar a los métodos clásicos anteriores, como la multiplicación de Karatsuba y el algoritmo de Toom-Cook (una generalización del método de Karatsuba), comenzando con números enteros de orden ( de 10 000 a 40 000 lugares decimales) [4 ] [5] [6] .

Notas

1. ↑ Bürgisser P., Clausen M., Shokrollahi A. Teoría de la complejidad algebraica. - Berlín: Springer-Verlag, 1997. - 618 p. — ISBN 3-540-60582-7 . .
2. ↑ Schönhage A., Strassen V. Schnelle Multiplikation großer Zahlen // Informática. - 1971. - Nº 7 . - Pág. 281-292.
3. ↑ Furer M. Multiplicación de enteros más rápida  // Actas de STOC 2007. - 2007. - Págs. 57-66. Archivado desde el original el 25 de abril de 2013.
4. ↑ Meter van R., Itoh KM Exponenciación modular cuántica rápida  // Physical Review A. - 2005. - Vol. 71 .
5. ↑ Descripción general de las características de Magma V2.9, sección aritmética Archivado el 20 de agosto de 2006 . : analiza los puntos de cruce prácticos entre varios algoritmos.
6. ↑ Coronado García LC ¿Puede la multiplicación de Schönhage acelerar el cifrado o descifrado RSA?  // Universidad de Tecnologia. —Darmstadt, 2005.