Algoritmo de Schönhage-Strassen

Algoritmo de multiplicación

El algoritmo de Schönhage-Strassen se basa en el método de multiplicación de enteros por transformada rápida de Fourier (FFT) . Esta figura demuestra cómo multiplicar 1234 × 5678 = 7006652 usando el método FFT simple. Se utiliza la base 10 en lugar de la base 2 ^w con fines ilustrativos.

Schönhage (a la derecha) y Strassen (a la izquierda) jugando al ajedrez en Oberwolfach , 1979

El algoritmo de Schönhage-Strassen es un algoritmo de multiplicación asintóticamente rápido para números enteros grandes , publicado por Arnold Schönhage y Volker Strassen en 1971. ^[1] Funciona aplicando recursivamente la transformada rápida de Fourier (FFT) sobre los enteros módulo 2 ⁿ +1. La complejidad de bits en tiempo de ejecución para multiplicar dos números de n dígitos usando el algoritmo está en notación O grande . ${\displaystyle O(n\cdot \log n\cdot \log \log n)}$

El algoritmo de Schönhage-Strassen fue el método de multiplicación asintóticamente más rápido conocido desde 1971 hasta 2007. Es asintóticamente más rápido que los métodos más antiguos, como la multiplicación de Karatsuba y Toom-Cook , y comienza a superarlos en la práctica para números de más de 10.000 a 100.000 dígitos decimales. ^[2] En 2007, Martin Fürer publicó un algoritmo con una complejidad asintótica más rápida. ^[3] En 2019, David Harvey y Joris van der Hoeven demostraron que la multiplicación de varios dígitos tiene complejidad teórica; sin embargo, su algoritmo tiene factores constantes que lo hacen increíblemente lento para cualquier problema práctico imaginable (ver algoritmo galáctico ). ^[4] ${\displaystyle O(n\log n)}$

Las aplicaciones del algoritmo de Schönhage-Strassen incluyen grandes cálculos realizados por sí mismos, como la Gran Búsqueda de Mersenne Prime en Internet y aproximaciones de π , así como aplicaciones prácticas como la factorización de la curva elíptica de Lenstra mediante la sustitución de Kronecker , que reduce la multiplicación de polinomios a multiplicación de enteros. . ^{[5] [6]}

Descripción

Esta sección tiene una versión simplificada del algoritmo, que muestra cómo calcular el producto de dos números naturales , módulo de un número de la forma , donde es un número fijo. Los números enteros deben dividirse en bloques de bits, por lo que en implementaciones prácticas es importante lograr el equilibrio adecuado entre los parámetros . En cualquier caso, este algoritmo proporcionará una manera de multiplicar dos números enteros positivos, siempre que se elija de modo que . ${\displaystyle ab}$ ${\displaystyle a,b}$ ${\displaystyle 2^{n}+1}$ ${\displaystyle n=2^{k}M}$ ${\displaystyle a,b}$ ${\displaystyle D=2^{k}}$ ${\displaystyle M}$ ${\displaystyle M,k}$ ${\displaystyle n}$ ${\displaystyle ab<2^{n}+1}$

Sea el número de bits en las señales y , donde es una potencia de dos. Divida las señales y en bloques de bits cada uno, almacenando los bloques resultantes como matrices (cuyas entradas consideraremos por simplicidad como números enteros de precisión arbitraria). ${\displaystyle n=DM}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle D=2^{k}}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle D}$ ${\displaystyle M}$ ${\displaystyle A,B}$

Ahora seleccionamos un módulo para la transformada de Fourier, como sigue. Sea tal que . También ponga y considere los elementos de las matrices como módulos enteros (precisión arbitraria) . Observe que desde , el módulo es lo suficientemente grande como para acomodar cualquier acarreo que pueda resultar de la multiplicación y . Por lo tanto, el producto (módulo ) se puede calcular evaluando la convolución de . Además, con , tenemos , y también lo es una raíz primitiva de módulo unitario . ${\displaystyle M'}$ ${\displaystyle DM'\geq 2M+k}$ ${\displaystyle n'=DM'}$ ${\displaystyle A,B}$ ${\displaystyle 2^{n'}+1}$ ${\displaystyle 2^{n'}+1\geq 2^{2M+k}+1=D2^{2M}+1}$ ${\displaystyle a}$ ${\displaystyle b}$ ${\displaystyle ab}$ ${\displaystyle 2^{n}+1}$ ${\displaystyle A,B}$ ${\displaystyle g=2^{2M'}}$ ${\displaystyle g^{D/2}\equiv -1{\pmod {2^{n'}+1}}}$ ${\displaystyle g}$ ${\displaystyle D}$ ${\displaystyle 2^{n'}+1}$

Ahora tomamos la transformada discreta de Fourier de las matrices en el anillo , usando la raíz de la unidad para la base de Fourier, dando las matrices transformadas . Como es una potencia de dos, esto se puede lograr en tiempo logarítmico usando una transformada rápida de Fourier . ${\displaystyle A,B}$ ${\displaystyle \mathbb {Z} /(2^{n'}+1)\mathbb {Z} }$ ${\displaystyle g}$ ${\displaystyle {\widehat {A}},{\widehat {B}}}$ ${\displaystyle D=2^{k}}$

Sea (producto puntual) y calcule la transformada inversa de la matriz , nuevamente usando la raíz de la unidad . La matriz ahora es la convolución de las matrices . Finalmente, el producto se obtiene evaluando ${\displaystyle {\widehat {C}}_{i}={\widehat {A}}_{i}{\widehat {B}}_{i}}$ ${\displaystyle C}$ ${\displaystyle {\widehat {C}}}$ ${\displaystyle g}$ ${\displaystyle C}$ ${\displaystyle A,B}$ ${\displaystyle ab{\pmod {2^{n}+1}}}$

$${\displaystyle ab\equiv \sum _{j}C_{j}2^{Mj}\mod {2^{n}+1}.}$$

Este algoritmo básico se puede mejorar de varias maneras. En primer lugar, no es necesario almacenar los dígitos con precisión arbitraria, sino solo hasta bits, lo que proporciona una representación mecánica más eficiente de las matrices . En segundo lugar, está claro que las multiplicaciones en las transformadas directas son simples desplazamientos de bits. Con cierto cuidado, también es posible calcular la transformada inversa utilizando únicamente desplazamientos. Teniendo cuidado, por lo tanto es posible eliminar cualquier multiplicación verdadera del algoritmo, excepto cuando se evalúa el producto puntual. Por lo tanto, es ventajoso seleccionar los parámetros para que este producto puntual se pueda realizar de manera eficiente, ya sea porque es una sola palabra de máquina o usando algún algoritmo optimizado para multiplicar números enteros de un número (idealmente pequeño) de palabras. Por tanto, la selección de los parámetros es un área importante para una mayor optimización del método. ${\displaystyle a,b}$ ${\displaystyle n'+1}$ ${\displaystyle A,B}$ ${\displaystyle {\widehat {C}}_{i}={\widehat {A}}_{i}{\widehat {B}}_{i}}$ ${\displaystyle D,M}$ ${\displaystyle D,M}$

Detalles

Todo número en base B se puede escribir como un polinomio:

${\displaystyle X=\sum _{i=0}^{N}{x_{i}B^{i}}}$

Además, la multiplicación de dos números podría considerarse como el producto de dos polinomios:

${\displaystyle XY=\left(\sum _{i=0}^{N}{x_{i}B^{i}}\right)\left(\sum _{j=0}^{N}{y_{i}B^{j}}\right)}$

Porque, para : , tenemos una convolución. ${\displaystyle B^{k}}$ ${\displaystyle c_{k}=\sum _{(i,j):i+j=k}{a_{i}b_{j}}=\sum _{i=0}^{k}{a_{i}b_{k-i}}}$

Mediante el uso de FFT ( transformada rápida de Fourier ), utilizada en la versión original en lugar de NTT, ^[7] con regla de convolución; obtenemos

${\displaystyle {\hat {f}}(a*b)={\hat {f}}\left(\sum _{i=0}^{k}a_{i}b_{k-i}\right)={\hat {f}}(a)\bullet {\hat {f}}(b).}$

Eso es; , donde es el coeficiente correspondiente en el espacio de Fourier. Esto también se puede escribir como: fft(a * b) = fft(a) ● fft(b). ${\displaystyle C_{k}=a_{k}\bullet b_{k}}$ ${\displaystyle C_{k}}$

Tenemos los mismos coeficientes debido a la linealidad bajo la transformada de Fourier y porque estos polinomios solo constan de un término único por coeficiente:

${\displaystyle {\hat {f}}(x^{n})=\left({\frac {i}{2\pi }}\right)^{n}\delta ^{(n)}}$ y

${\displaystyle {\hat {f}}(a\,X(\xi )+b\,Y(\xi ))=a\,{\hat {X}}(\xi )+b\,{\hat {Y}}(\xi )}$

Regla de convolución: ${\displaystyle {\hat {f}}(X*Y)=\ {\hat {f}}(X)\bullet {\hat {f}}(Y)}$

Hemos reducido nuestro problema de convolución a un problema de producto, mediante FFT.

Al encontrar ifft (interpolación polinómica), para cada uno , se obtienen los coeficientes deseados. ${\displaystyle c_{k}}$

El algoritmo utiliza la estrategia de dividir y conquistar para dividir el problema en subproblemas.

Convolución bajo mod N

${\displaystyle c_{k}=\sum _{(i,j):i+j\equiv k{\pmod {N(n)}}}a_{i}b_{j}}$, donde y en el algoritmo de Schönhage-Strassen. ${\displaystyle N(n)=2^{n}+1}$ ${\displaystyle N(N)=2^{N}+1}$

Dejando:

${\displaystyle a_{i}'=\theta ^{i}a_{i}}$y ${\displaystyle b_{j}'=\theta ^{j}b_{j},}$

¿Dónde está la raíz enésima? ${\displaystyle \theta ^{N}=-1}$

Se ve que: ^[8]

${\displaystyle {\begin{aligned}C_{k}&=\sum _{(i,j):i+j=k\equiv {\pmod {N(n)}}}a_{i}b_{j}=\theta ^{-k}\sum _{(i,j):i+j\equiv k{\pmod {N(n)}}}a_{i}'b_{j}'\\[6pt]&=\theta ^{-k}\left(\sum _{(i,j):i+j=k}a_{i}'b_{j}'+\sum _{(i,j):i+j=k+n}a_{i}'b_{j}'\right)\\[6pt]&=\theta ^{-k}\left(\sum _{(i,j):i+j=k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=k+n}a_{i}b_{j}\theta ^{n+k}\right)\\[6pt]&=\sum _{(i,j):i+j=k}a_{i}b_{j}+\theta ^{n}\sum _{(i,j):i+j=k+n}a_{i}b_{j}.\end{aligned}}}$

Esto significa que se puede usar peso y luego multiplicar por después. ${\displaystyle \theta ^{i}}$ ${\displaystyle \theta ^{-k}}$

En lugar de utilizar peso; uno puede debido a , en el primer paso de la recursividad (cuando ), calcular: ${\displaystyle \theta ^{N}=-1}$ ${\displaystyle n=N}$

${\displaystyle C_{k}=\sum _{(i,j):i+j\equiv k{\pmod {N(N)}}}=\sum _{(i,j):i+j=k}a_{i}b_{j}-\sum _{(i,j):i+j=k+n}a_{i}b_{j}}$

En FFT normal, que opera con números complejos, se usaría:

$${\displaystyle \exp \left({\frac {2k\pi i}{n}}\right)=\cos {\frac {2k\pi }{n}}+i\sin {\frac {2k\pi }{n}},\qquad k=0,1,\dots ,n-1.}$$

${\displaystyle {\begin{aligned}C_{k}&=\theta ^{-k}\left(\sum _{(i,j):i+j=k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=k+n}a_{i}b_{j}\theta ^{n+k}\right)\\[6pt]&=e^{-i2\pi k/n}\left(\sum _{(i,j):i+j=k}a_{i}b_{j}e^{i2\pi k/n}+\sum _{(i,j):i+j=k+n}a_{i}b_{j}e^{i2\pi (n+k)/n}\right)\end{aligned}}}$

Sin embargo, la FFT también se puede utilizar como NTT (transformación teórica de números) en Schönhage-Strassen. Esto significa que tenemos que usar θ que genere números en un campo finito (por ejemplo ). ${\displaystyle \mathrm {GF} (2^{n}+1)}$

Una raíz de unidad bajo un campo finito GF( r ) , es un elemento tal que o . Por ejemplo, GF( p ) , donde p es un número primo, da . ${\displaystyle \theta ^{r-1}\equiv 1}$ ${\displaystyle \theta ^{r}\equiv \theta }$ ${\displaystyle \{1,2,\ldots ,p-1\}}$

Observe que en y en . Para estos candidatos, bajo su campo finito, y por lo tanto actúan de la manera que queremos. ${\displaystyle 2^{n}\equiv -1}$ ${\displaystyle \operatorname {GF} (2^{n}+1)}$ ${\displaystyle {\sqrt {2}}\equiv -1}$ ${\displaystyle \operatorname {GF} (2^{n+2}+1)}$ ${\displaystyle \theta ^{N}\equiv -1}$

Sin embargo, aún se pueden usar los mismos algoritmos FFT, siempre que θ sea la raíz de la unidad de un campo finito.

Para encontrar la transformación FFT/NTT, hacemos lo siguiente:

${\displaystyle {\begin{aligned}C_{k}'&={\hat {f}}(k)={\hat {f}}\left(\theta ^{-k}\left(\sum _{(i,j):i+j=k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=k+n}a_{i}b_{j}\theta ^{n+k}\right)\right)\\[6pt]C_{k+k}'&={\hat {f}}(k+k)={\hat {f}}\left(\sum _{(i,j):i+j=2k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=n+2k}a_{i}b_{j}\theta ^{n+k}\right)\\[6pt]&={\hat {f}}\left(\sum _{(i,j):i+j=2k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=2k+n}a_{i}b_{j}\theta ^{n+k}\right)\\[6pt]&={\hat {f}}\left(A_{k\leftarrow k}\right)\bullet {\hat {f}}(B_{k\leftarrow k})+{\hat {f}}(A_{k\leftarrow k+n})\bullet {\hat {f}}(B_{k\leftarrow k+n})\end{aligned}}}$

El primer producto da contribución a , para cada k . El segundo contribuye a , debido al mod . ${\displaystyle c_{k}}$ ${\displaystyle c_{k}}$ ${\displaystyle (i+j)}$ ${\displaystyle N(n)}$

Para hacer lo inverso:

${\displaystyle C_{k}=2^{-m}{\hat {f^{-1}}}(\theta ^{-k}C_{k+k}')}$o ${\displaystyle C_{k}={\hat {f^{-1}}}(\theta ^{-k}C_{k+k}')}$

dependiendo de si fft uno usa datos normalizados o no.

Uno multiplica por , para normalizar los datos de fft a un rango específico, donde , donde m se encuentra usando el inverso multiplicativo modular. ${\displaystyle 2^{-m}}$ ${\displaystyle {\frac {1}{n}}\equiv 2^{-m}{\bmod {N}}(n)}$

Detalles de implementacion

Por qué N = 2 M + 1 en mod N

En el algoritmo de Schönhage-Strassen ,. Uno debería pensar en esto como un árbol binario, donde uno tiene valores en . Al dejar , se pueden encontrar todos para cada K : Se pueden agrupar todos los pares en M grupos diferentes. Usar para agrupar pares mediante convolución es un problema clásico en algoritmos. ^[9] Por ejemplo: Sea k el ingreso total, i el ingreso del hombre y j el ingreso de la mujer; Al utilizar la convolución, se pueden agrupar en K grupos según el ingreso total deseado. ${\displaystyle N=2^{M}+1}$ ${\displaystyle 0\leq {\text{index}}\leq 2^{M}=2^{i+j}}$ ${\displaystyle K\in [0,M]}$ ${\displaystyle i+j=K}$ ${\displaystyle (i,j)}$ ${\displaystyle i+j=k}$ ${\displaystyle (i,j)}$ ${\displaystyle (i,j)}$

Teniendo esto en cuenta, ayúdanos a agrupar en grupos, para cada grupo de subtareas en profundidad k ; en árbol con ${\displaystyle N=2^{M}+1}$ ${\displaystyle (i,j)}$ ${\displaystyle {\frac {M}{2^{k}}}}$ ${\displaystyle N=2^{\frac {M}{2^{k}}}+1}$

Observe que , para algunos L. Este es el número de Fermat. Al hacer mod , tenemos algo llamado anillo Fermat. ${\displaystyle N=2^{M}+1=2^{2^{L}}+1}$ ${\displaystyle N=2^{M}+1=2^{2^{L}}+1}$

Debido a que algunos números de Fermat son primos de Fermat, en algunos casos se pueden evitar los cálculos.

Hay otros N que podrían haberse utilizado, por supuesto, con las mismas ventajas de los números primos. Al dejar , uno tiene el número máximo en un número binario con bits. es un número de Mersenne, que en algunos casos es un número primo de Mersenne. Es un candidato natural contra el número de Fermat ${\displaystyle N=2^{k}-1}$ ${\displaystyle k+1}$ ${\displaystyle N=2^{k}-1}$ ${\displaystyle N=2^{2^{L}}+1}$

En busca de otro N

Hacer varios cálculos mod contra diferentes N puede ser útil cuando se trata de resolver un producto entero. Utilizando el teorema del resto chino , después de dividir M en tipos diferentes más pequeños de N , se puede encontrar la respuesta de la multiplicación xy ^[10]

Los números de Fermat y los números de Mersenne son solo dos tipos de números, en algo llamado número de Fermat Mersenne generalizado (GSM); con fórmula: ^[11]

${\displaystyle G_{q,p,n}=\sum _{i=1}^{p}q^{(p-i)n}={\frac {q^{pn}-1}{q^{n}-1}}}$

${\displaystyle M_{p,n}=G_{2,p,n}}$

En esta fórmula; es un número de Fermat y es un número de Mersenne. ${\displaystyle M_{2,2^{k}}}$ ${\displaystyle M_{p,1}}$

Esta fórmula se puede utilizar para generar conjuntos de ecuaciones, que se pueden utilizar en CRT (teorema del resto chino): ^[12]

${\displaystyle g^{\frac {(M_{p,n}-1)}{2}}\equiv -1{\pmod {M_{p,n}}}}$, donde g es un número tal que existe una x donde , suponiendo ${\displaystyle x^{2}\equiv g{\pmod {M_{p,n}}}}$ ${\displaystyle N=2^{n}}$

Además; , donde a es un elemento que genera elementos de forma cíclica. ${\displaystyle g^{2^{(p-1)n}-1}\equiv a^{2^{n}-1}{\pmod {M_{p,n}}}}$ ${\displaystyle \{1,2,4,...2^{n-1},2^{n}\}}$

Si , dónde , entonces . ${\displaystyle N=2^{t}}$ ${\displaystyle 1\leq t\leq n}$ ${\displaystyle g_{t}=a^{(2^{n}-1)2^{n-t}}}$

Cómo elegir K para una N específica

La siguiente fórmula ayuda a encontrar un K adecuado (número de grupos para dividir N bits) dado el tamaño de bit N calculando la eficiencia: ^[13]

${\displaystyle E={\frac {{\frac {2N}{K}}+k}{n}}}$ N es el tamaño de bits (el que se usa en ) en el nivel más externo. K da grupos de bits, donde . ${\displaystyle 2^{N}+1}$ ${\displaystyle {\frac {N}{K}}}$ ${\displaystyle K=2^{k}}$

n se encuentra a través de N, K y k encontrando el x más pequeño , tal que ${\displaystyle 2N/K+k\leq n=K2^{x}}$

Si se supone una eficiencia superior al 50% y k es muy pequeño en comparación con el resto de la fórmula; uno consigue ${\displaystyle {\frac {n}{2}}\leq {\frac {2N}{K}},K\leq n}$

${\displaystyle K\leq 2{\sqrt {N}}}$

Esto significa: Cuando algo es muy efectivo; K está ligado arriba por o asintóticamente ligado arriba por ${\displaystyle 2{\sqrt {N}}}$ ${\displaystyle {\sqrt {N}}}$

Pseudocódigo

Siguiendo el algoritmo, el algoritmo de multiplicación modular estándar de Schönhage-Strassen (con algunas optimizaciones) se encuentra en una descripción general en ^[14]

1. Divida ambos números de entrada a y b en n coeficientes de s bits cada uno.

   Utilice al menos bits para almacenarlos, ${\displaystyle K+1}$

   para permitir la codificación del valor ${\displaystyle 2^{K}.}$
2. Pondere ambos vectores de coeficientes según (2.24) con potencias de θ realizando desplazamientos cíclicos sobre ellos.
3. Mezcla los coeficientes y . ${\displaystyle a_{i}}$ ${\displaystyle b_{j}}$
4. Evaluar y . Las multiplicaciones por potencias de ω son cambios cíclicos. ${\displaystyle a_{i}}$ ${\displaystyle b_{j}}$
5. No hagas multiplicaciones puntuales en . Si SMUL se usa de forma recursiva, proporcione K como parámetro. De lo contrario, utilice alguna otra función de multiplicación como T3MUL y luego reduzca el módulo. ${\displaystyle c_{k}:=a_{k}b_{k}}$ ${\displaystyle Z/(2^{K}+1)Z}$ ${\displaystyle 2^{K}+1}$
6. Mezcla los coeficientes del producto . ${\displaystyle c_{k}}$
7. Evaluar los coeficientes del producto . ${\displaystyle c_{k}}$
8. Aplicar los contrapesos según (2.25). Ya que se deduce que ${\displaystyle c_{k}}$ ${\displaystyle \theta ^{2n}\equiv 1}$ ${\displaystyle \theta ^{-k}\equiv \theta ^{n-k}}$
9. Normalice el con (nuevamente un cambio cíclico). ${\displaystyle c_{k}}$ ${\displaystyle 1/n\equiv 2^{-m}}$
10. Sume y propague los acarreos. Asegúrese de manejar adecuadamente los coeficientes negativos. ${\displaystyle c_{k}}$
11. Haz un módulo de reducción . ${\displaystyle 2^{N}+1}$

• T3MUL = multiplicación de Toom-Cook
• SMUL = multiplicación de Schönhage-Strassen
• Evaluar = FFT/IFFT

Estudio adicional

Para obtener detalles sobre la implementación, se puede leer el libro Números primos: una perspectiva computacional . ^[15] Esta variante difiere algo del método original de Schönhage en que explota la transformada ponderada discreta para realizar convoluciones negacíclicas de manera más eficiente. Otra fuente de información detallada es The Art of Computer Programming de Knuth . ^[dieciséis]

Optimizaciones

Esta sección explica una serie de optimizaciones prácticas importantes al implementar Schönhage-Strassen.

Uso de otro algoritmo de multiplicación, algoritmo interno.

Por debajo de cierto punto de corte, es más eficiente utilizar otros algoritmos de multiplicación, como la multiplicación de Toom-Cook . ^[17]

Raíz cuadrada de 2 truco

La idea es utilizar como raíz de la unidad de orden en un campo finito (es una solución de la ecuación ), al ponderar valores en el enfoque NTT (transformación teórica de números). Se ha demostrado que ahorra un 10% en el tiempo de multiplicación de números enteros. ^[18] ${\displaystyle {\sqrt {2}}}$ ${\displaystyle 2^{n+2}}$ ${\displaystyle \mathrm {GF} (2^{n+2}+1)}$ ${\displaystyle \theta ^{2^{n+2}}\equiv 1{\pmod {2^{n+2}+1}}}$

El truco de Granlund

Dejando ; se puede calcular y . En combinación con CRT (Teorema del resto chino), para encontrar valores exactos de multiplicación uv ^[19] ${\displaystyle m=N+h}$ ${\displaystyle uv{\bmod {2^{N}+1}}}$ ${\displaystyle (u{\bmod {2^{h}}})(v{\bmod {2}}^{h})}$

Referencias

1. Schönhage, Arnold ; Strassen, Volker (1971). "Schnelle Multiplikation großer Zahlen" [Multiplicación rápida de números grandes]. Computación (en alemán). 7 (3–4): 281–292. doi :10.1007/BF02242355. S2CID  9738629.
2. La multiplicación de Karatsuba tiene una complejidad asintótica de aproximadamente y la multiplicación de Toom-Cook tiene una complejidad asintótica de aproximadamente ${\displaystyle O(n^{1.58})}$ ${\displaystyle O(n^{1.46}).}$

   Van Meter, Rodney; Itoh, Kohei M. (2005). "Exponenciación modular cuántica rápida". Revisión física . 71 (5): 052320. arXiv : quant-ph/0408006 . Código Bib : 2005PhRvA..71e2320V. doi : 10.1103/PhysRevA.71.052320. S2CID  14983569.

   Se puede encontrar una discusión sobre puntos de cruce prácticos entre varios algoritmos en: Descripción general de las características de Magma V2.9, sección aritmética Archivado el 20 de agosto de 2006 en Wayback Machine.

   Luis Carlos Coronado García, "¿Puede la multiplicación de Schönhage acelerar el cifrado o descifrado RSA? Archivado", Universidad Tecnológica de Darmstadt (2005)

   La biblioteca GNU Multi-Precision lo utiliza para valores de al menos 1728 a 7808 palabras de 64 bits (33 000 a 150 000 dígitos decimales), según la arquitectura. Ver:

   "Multiplicación FFT (GNU MP 6.2.1)". gmplib.org . Consultado el 20 de julio de 2021 .

   "MUL_FFT_THRESHOLD". Rincón de los desarrolladores de GMP . Archivado desde el original el 24 de noviembre de 2010 . Consultado el 3 de noviembre de 2011 .

   "MUL_FFT_THRESHOLD". gmplib.org . Consultado el 20 de julio de 2021 .

3. El algoritmo de Fürer tiene complejidad asintótica ${\textstyle O{\bigl (}n\cdot \log n\cdot 2^{\Theta (\log ^{*}n)}{\bigr )}.}$
   Fürer, Martín (2007). "Multiplicación de enteros más rápida" (PDF) . Proc. ESTOC '07 . Simposio sobre teoría de la computación, San Diego, junio de 2007, págs. 57–66. Archivado desde el original (PDF) el 5 de marzo de 2007.
   Fürer, Martín (2009). "Multiplicación de enteros más rápida". Revista SIAM de Computación . 39 (3): 979–1005. doi :10.1137/070711761. ISSN  0097-5397.

   El algoritmo de Fürer se utiliza en la biblioteca de código abierto de subprogramas de álgebra polinomial básica (BPAS). Ver: Covanov, Svyatoslav; Mohajerani, Davood; Moreno Maza, Marc; Wang, Linxiao (8 de julio de 2019). "Big Prime Field FFT en procesadores multinúcleo". Actas del Simposio internacional sobre computación simbólica y algebraica de 2019 (PDF) . Pekín China: ACM. págs. 106-113. doi :10.1145/3326229.3326273. ISBN 978-1-4503-6084-5. S2CID  195848601.

4. Harvey, David; van der Hoeven, Joris (2021). "Multiplicación de enteros en el tiempo O ( n log ⁡ n ) {\displaystyle O(n\log n)} " (PDF) . Anales de Matemáticas . Segunda Serie. 193 (2): 563–617. doi : 10.4007/anales.2021.193.2.4. SEÑOR  4224716. S2CID  109934776.
5. Este método se utiliza en la biblioteca ECM de INRIA.
6. "ECMNET". miembros.loria.fr . Consultado el 9 de abril de 2023 .
7. Becker, Hanón; Hwang, Vicente; J. Kannwischer, Matías; Panny, Lorenz (2022). "Multiplicación eficiente de números enteros algo pequeños mediante transformaciones de teoría de números" (PDF) .
8. Lüders, Christoph (2014). "Multiplicación rápida de números enteros grandes: implementación y análisis del algoritmo DKSS". pag. 26.
9. Kleinberg, Jon; Tardós, Eva (2005). Diseño de algoritmos (1 ed.). Pearson. pag. 237.ISBN​ 0-321-29535-8.
10. Gaudry, Pierrick; Alejandro, Kruppa; Pablo, Zimmermann (2007). "Una implementación basada en GMP del algoritmo de multiplicación de enteros grandes de Schönhage-Strassen" (PDF) . pag. 6.
11. S. Dimitrov, Vassil; V. Cooklev, Todor; D. Donevsky, Borislav (1994). "Transformada teórica de números de Fermat-Mersenne generalizada". pag. 2.
12. S. Dimitrov, Vassil; V. Cooklev, Todor; D. Donevsky, Borislav (1994). "Transformada teórica de números de Fermat-Mersenne generalizada". pag. 3.
13. Gaudry, Pierrick; Kruppa, Alejandro; Zimmermann, Paul (2007). "Una implementación basada en GMP del algoritmo de multiplicación de enteros grandes de Schönhage-Strassen" (PDF) . pag. 2.
14. Lüders, Christoph (2014). "Multiplicación rápida de números enteros grandes: implementación y análisis del algoritmo DKSS". pag. 28.
15. R. Crandall y C. Pomerance. Números primos: una perspectiva computacional . Segunda edición, Springer, 2005. Sección 9.5.6: Método de Schönhage, p. 502. ISBN 0-387-94777-9 
16. Knuth, Donald E. (1997). "§ 4.3.3.C: Transformadas discretas de Fourier". El arte de la programación informática . vol. 2: Algoritmos seminuméricos (3ª ed.). Addison-Wesley. págs. 305–311. ISBN 0-201-89684-2.
17. Gaudry, Pierrick; Kruppa, Alejandro; Zimmermann, Paul (2007). "Una implementación basada en GMP del algoritmo de multiplicación de enteros grandes de Schönhage-Strassen" (PDF) . pag. 7.
18. Gaudry, Pierrick; Kruppa, Alejandro; Zimmermann, Paul (2007). "Una implementación basada en GMP del algoritmo de multiplicación de enteros grandes de Schönhage-Strassen" (PDF) . pag. 6.
19. Gaudry, Pierrick; Kruppa, Alejandro; Zimmermann, Paul (2007). "Una implementación basada en GMP del algoritmo de multiplicación de enteros grandes de Schönhage-Strassen" (PDF) . pag. 6.