Algoritmo del Führer

El algoritmo de Führer es un método rápido para multiplicar números enteros grandes. El algoritmo fue construido en 2007 por el matemático suizo Martin Führer [1] de la Universidad de Pensilvania como un algoritmo asintóticamente más rápido que su predecesor, el algoritmo Schönhage-Strassen , publicado en 1971 [2] . El problema de multiplicar rápidamente grandes números es de gran interés en el campo de la criptografía de clave pública .

El predecesor del algoritmo del Führer, el algoritmo de Schönhage-Strassen, utilizó la transformada rápida de Fourier para multiplicar grandes números en el tiempo , pero sus autores, Arnold Schönhage ( alemán: Arnold Schönhage ) y Volker Strassen , asumieron que existe un algoritmo que puede resolver el problema de multiplicar números grandes en . El algoritmo de Führer [1] llenó el espacio entre estos límites: se puede usar para multiplicar números en el tiempo , donde es el logaritmo iterado de n . Sin embargo, la diferencia de tiempo entre los algoritmos se vuelve notable en números multiplicados muy grandes (más de 10,000,000,000,000 $O\izquierda(n\registro n\registro\registro n\derecha)$ $O\izquierda(n\log n\derecha)$ $O(n\log n\cdot 2^{O(\log ^{*}n)})$ $\log ^{*}n$ [3] dígitos significativos).

En 2008, Anindaya De, Shenden Saha, Pyush Kurur y Ramprasad Saptharishi construyeron un algoritmo similar basado en aritmética modular en lugar de compleja, mientras lograban el mismo tiempo de ejecución [4] .

Teoría

Convolución

Digamos que multiplicamos los números 123 y 456 "en una columna", pero sin realizar la transferencia. El resultado se verá así:

		una	2	3
	×	cuatro	5	6

		6	12	Dieciocho
	5	diez	quince
cuatro	ocho	12

cuatro	13	28	27	Dieciocho

Esta secuencia (4, 13, 28, 27, 18) se denomina convolución acíclica o lineal de las secuencias (1,2,3) y (4,5,6). Conociendo la convolución acíclica de dos sucesiones, no es difícil calcular el producto: basta con realizar la transferencia (por ejemplo, en la columna de la derecha, dejamos 8 y sumamos 1 a la columna que contiene 27). En nuestro ejemplo, esto da como resultado 56088.

Hay otros tipos de pliegues que pueden ser útiles. Digamos que las secuencias de entrada contienen n elementos (en el ejemplo, 3). Entonces la convolución lineal resultante contiene n + n − 1 elementos; si tomamos la columna más a la derecha de n elementos y agregamos la columna más a la izquierda de n − 1 ', terminamos con una convolución circular:

	28	27	Dieciocho
+		cuatro	13

	28	31	31

Si realizamos la envoltura, el resultado será el mismo que al multiplicar números módulo B n − 1 (en este ejemplo es 10 3 − 1 = 999). Realizamos la transferencia (aún no cíclica): (31+3=34, 28+3=31) y obtenemos 3141. Si sumamos los tres de la izquierda al de la derecha, obtenemos 144 ≡ 56088 (mod 999) (El la transferencia debe realizarse de forma cíclica, es decir, se sumarán 3 de los 31 inferiores a los 31 superiores, 3 de los 34 recibidos se sumarán a 28 y el triple de los 31 recibidos se sumará al orden inferior, es decir, a 1).

Por el contrario, si tomamos la columna más a la derecha de n elementos y restamos la columna más a la izquierda de n − 1 elementos, terminamos con un desdoblamiento:

	28	27	Dieciocho
−		cuatro	13

	28	23	5

Si realizamos el rollback, el resultado será el mismo que cuando multiplicamos los números módulo B n + 1. En este ejemplo, 10 3 + 1 = 1001, realizamos el arrastre (28, 23, 5) y obtenga 3035 , mientras que 3035 ≡ 56088 (mod 1001). El pliegue inverso puede contener números negativos, que se pueden eliminar durante el envoltorio utilizando la misma técnica que para las restas largas.

Teorema de convolución

Al igual que otros métodos basados en la transformada rápida de Fourier, el algoritmo del Führer depende fundamentalmente del teorema de convolución, que proporciona una manera eficiente de calcular la convolución cíclica de dos secuencias. Su idea es:

La convolución cíclica de dos vectores se puede encontrar a través de la Transformada Discreta de Fourier (DFT) de cada uno, al multiplicar los vectores resultantes elemento por elemento, seguido de la Transformada Inversa de Fourier (IDFT).

O a través de fórmulas:

CyclicConvolution(X, Y) = IDFT(DFT(X) DFT(Y)), donde: CyclicConvolution - convolución cíclica , DFT - Transformada de Fourier discreta , IDFT - Transformada de Fourier Discreta Inversa .

Si calculamos la DFT y la ODFT usando la transformada rápida de Fourier y llamamos recursivamente a nuestro algoritmo de multiplicación para multiplicar las entradas (?) de los vectores transformados DFT(X) y DFT(Y), terminamos con un algoritmo eficiente para calcular el ciclo circunvolución.

En este algoritmo, es mucho más eficiente calcular la convolución circular inversa ; resulta que una versión ligeramente modificada del teorema de convolución puede hacer precisamente eso. Supongamos que los vectores X e Y son de longitud ny a es una raíz primitiva de orden 2 n (lo que significa que a 2 n = 1 y todas las potencias menores de a no son iguales a 1). Así podemos definir un tercer vector A , llamado vector de peso , que tiene las siguientes propiedades:

UN = ( un j ), 0 ≤ j < norte UN −1 = ( un − j), 0 ≤ j < norte

Ahora podemos escribir:

Convoluciónnegacíclica( X , Y ) = A −1 IDFT(DFT( A X ) DFT ( A Y )), donde NegacyclicConvolution — Convolución cíclica inversa , DFT - Transformada de Fourier discreta , IDFT - Transformada de Fourier Discreta Inversa .

En otras palabras, es lo mismo excepto que los vectores de entrada se multiplican por A y el resultado se multiplica por A −1 .

Selección de anillo

La transformada discreta de Fourier es una operación abstracta que se puede realizar en cualquier anillo algebraico ; generalmente se toma del campo de los números complejos, pero en realidad usar aritmética compleja con suficiente precisión para proporcionar resultados precisos es lento e ineficiente. En su lugar, podemos usar una transformación teórica de números que transforma el campo de los números enteros módulo N para algún número entero N.

Así como existen raíces unitarias primitivas de cualquier orden en el plano complejo, para cualquier n dado podemos elegir un N adecuado tal que b sea una raíz unitaria primitiva de orden n en el campo de los enteros módulo N (en otras palabras, b n ≡ 1 (mod N ), y todas las potencias menores de b no son iguales a 1 mod N).

El algoritmo pasa la mayor parte de su tiempo ejecutando recursivamente el producto de números más pequeños; en una versión simple del algoritmo, esto sucede en varios lugares:

Dentro del algoritmo Fast Fourier Transform, la raíz unitaria primitiva b se eleva repetidamente a una potencia y se multiplica por otros números.
Al elevar una raíz primitiva de la unidad a a una potencia para obtener un vector de peso A, y luego multiplicar los vectores A o A −1 por otros vectores.
Al realizar la multiplicación secuencial de los vectores transformados.

El punto clave es elegir N, módulo 2 n + 1 para algún número entero n . Este método tiene una serie de ventajas en varios sistemas estándar en los que los números enteros grandes se representan en binario:

Cualquier número se puede reducir rápidamente módulo 2 n + 1 usando solo el desplazamiento y la suma.
Cualquier raíz unitaria primitiva en este anillo se puede escribir en la forma 2 k ; en consecuencia, podemos multiplicar o dividir cualquier número por la raíz de la unidad usando un cambio.
La multiplicación recursiva elemento por elemento de los vectores transformados se puede realizar mediante deconvolución, que es más rápida que la convolución acíclica y ya tiene una reducción módulo 2 n + 1 del resultado.

Diferencia con el predecesor

La principal diferencia con su predecesor es la ejecución múltiple de la compresión de números, lo que le da complejidad computacional, en contraste con un solo uso en el algoritmo de Schönhage-Strassen, que le da complejidad. $n \log n\,2^{O(\log^* n)}$ $n\log n\log \log n$

Estructura del algoritmo

Producto de números enteros

Módulo producto de números enteros Descomposición FFT Producto Explosionado FFT inversa Composición del resultado

Notas

↑ 1 2 Furer, M. (2007). « Multiplicación de enteros más rápida Archivado desde el original el 25 de abril de 2013. » en Actas del trigésimo noveno simposio anual de ACM sobre Teoría de la computación, 11-13 de junio de 2007, San Diego, California, EE. UU.
↑ A. Schönhage y V. Strassen, "Schnelle Multiplikation großer Zahlen", Computing 7 (1971), págs. 281-292.
↑ Alexander J. Yee. Algoritmos en y-cruncher: el programa más rápido para calcular varias constantes con alta precisión. (21 de junio de 2014). Consultado el 24 de junio de 2014. Archivado desde el original el 30 de marzo de 2014. (indefinido)
↑ Anindya De, Piyush P Kurur, Chandan Saha, Ramprasad Saptharishi. Multiplicación rápida de enteros usando aritmética modular. Simposio sobre Teoría de la Computación (STOC) 2008. arXiv : 0801.1416

Algoritmos de teoría de números
Pruebas de simplicidad	Molinero Miller - Rabín Luca-Lemaire pepina Agrawala - Kayala - Sajonia Ruiseñor - Strassen
Encontrar números primos	Iterando sobre divisores Tamiz de Eratóstenes tamiz de atkin Tamiz Sundarama
Factorización	Iterando sobre divisores método Fermat p −1 Método de Pollard Algoritmo ρ de Pollard método Lehmann Método de la curva elíptica (algoritmo de Lenstra) algoritmo de dixon tamiz cuadrado
logaritmo discreto	Algoritmo de Gelfond-Shanks Algoritmo de Polig-Hellman Método ρ de Pollard Algoritmo del canguro de Pollard algoritmo de Adleman algoritmo COS
Encontrar MCD	Algoritmo de Euclides Algoritmo avanzado Algoritmo binario
Módulo aritmético	algoritmo de Montgomery Teorema del resto chino
Multiplicación y división de números.	Algoritmo Karatsuba Algoritmo de Toom-Cook Algoritmo de Schönhage-Strassen Algoritmo del Führer Algoritmo de Harvey-van der Hoeven Algoritmo de Burnickel-Ziegler
Calcular la raíz cuadrada	Algoritmo de Tonelli-Shanks Algoritmo de Berlekamp-Rabin