Algoritmo de Schönhage - Estrassen

El algoritmo de Schönhage–Strassen es un algoritmo de multiplicación asintoticamente rápida para grandes enteros, publicado por Arnold Schönhage y Volker Strassen en 1971. Funciona aplicando recursivamente la transformación rápida Fourier (FFT) sobre los enteros modulo 2ⁿ+1. La complejidad del tiempo de ejecución para multiplicar dos n- números de dígitos usando el algoritmo es ${\displaystyle O(n\cdot \log n\cdot \log n)}$ en la gran notación O.

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

Las aplicaciones del algoritmo Schönhage -Strassen incluyen grandes cálculos realizados por su propio bien, como la gran búsqueda de Internet Mersenne Prime y las aproximaciones de π, así como aplicaciones prácticas como la factorización de la curva elíptica de Lenstra a través de la sustitución de Kronecker, que reduce a la multiplicación entera.

Descripción

Esta sección tiene una versión simplificada del algoritmo, mostrando cómo calcular el producto ${\displaystyle ab}$ de dos números naturales ${\displaystyle a,b}$, modulo un número de la forma ${\displaystyle 2^{n}+1}$, donde ${\displaystyle No.$ es un número fijo. Los enteros ${\displaystyle a,b}$ se dividirán en ${\displaystyle D=2^{k}$ bloques de ${\displaystyle M}$ bits, así que en implementaciones prácticas, es importante lograr el equilibrio adecuado entre los parámetros ${\displaystyle M,k}$. En cualquier caso, este algoritmo proporcionará una manera de multiplicar dos enteros positivos, proporcionados ${\displaystyle n}$ es elegido para que ${\displaystyle ab won2^{n}+1}$.

Vamos. ${\displaystyle n=DM}$ ser el número de bits en las señales ${\displaystyle a}$ y ${\displaystyle b}$, donde ${\displaystyle D=2^{k}$ es un poder de dos. Divide las señales ${\displaystyle a}$ y ${\displaystyle b}$ en ${\displaystyle D}$ bloques de ${\displaystyle M}$ pica cada uno, almacenando los bloques resultantes como arrays ${\displaystyle A,B}$ (cuyas entradas consideraremos para la simplicidad como enteros de precisión arbitrarios).

Ahora seleccionamos un módulo para la transformación Fourier, como sigue. Vamos. ${\displaystyle M'}$ ser tal ${\displaystyle DM'\geq 2M+k}$. También se puso ${\displaystyle n'=DM'}$, y considerar los elementos de los arrays ${\displaystyle A,B}$ como (precisión arbitraria) modulo de enteros ${\displaystyle 2^{n}+1}$. Observa que desde entonces ${\displaystyle 2^{n'}+1\geq 2^{2M+k}+1=D2^{2M}+1}$, el módulo es lo suficientemente grande para acomodar cualquier carga que puede resultar de multiplicación ${\displaystyle a}$ y ${\displaystyle b}$. Así, el producto ${\displaystyle ab}$ (modulo) ${\displaystyle 2^{n}+1}$) se puede calcular evaluando la convolución de ${\displaystyle A,B}$. También, con ${\displaystyle g=2^{2M}$, tenemos ${\displaystyle G^{D/2}\equiv -1{\pmod {2^{n'}+1}$, y así ${\displaystyle g}$ es un primitivo ${\displaystyle D}$la raíz del modulo de unidad ${\displaystyle 2^{n}+1}$.

Ahora tomamos la discreta transformación Fourier de los arrays ${\displaystyle A,B}$ en el anillo ${\displaystyle \mathbb {Z}/(2^{n'}+1)\mathbb {Z}$, utilizando la raíz de la unidad ${\displaystyle g}$ para la base Fourier, dando los arrays transformados ${\displaystyle {\widehat {A}},{\widehat {B}}$. Porque... ${\displaystyle D=2^{k}$ es un poder de dos, esto se puede lograr en el tiempo logarítmico usando una rápida transformación Fourier.

Vamos. ${\displaystyle {\widehat {C} {\fn} {\fnMicrosoft} {\fnK}} {\f}}} {\f}} {\f}} {\fnMicrosoft}} {\f}}} {\f}} {\fn}}}} {\\f}}}} {\f}}}}} {\\\\\\\fn\\\fnH}}}}}}}}}}}}}}}}}}}}\\\\\\\\\\\\\\f}}\\\\\\\\\\\\\\\\\\\\\\\\fnH\\\\\\\\\\\\\\\\\\\fnH}}}}}}}}}}}}}}}}}}}}\\\\\\\f}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} {\fnK} {\f} {\fnMicrosoft}} {\fnK}} {\f}} {\f}} {\f}}} {\f}}} {\f}}} {\f}}}}}} {\f}}} {\f}}} {\f}}}}} {\f}}}}}}} {\\f}}}} {\f}}}}}}}}}}}} {\\m}}}}}}}}}}}}}}} {\m}}} {\m} {\m}}}}}}}} {\m}}}}}}}}}}}}}}}}}} {\m} {\m}}}} {\m}}}} {\m}} {\m} {\m} {\m}}}}} {\f}}}} {\m} {\m}}}}{\m}}}}}} {\m}}} {\m}}}} {B}_{i}$ (producto puntero), y computar la transformación inversa ${\displaystyle C}$ de la matriz ${\displaystyle {\widehat {C}}$, nuevamente utilizando la raíz de la unidad ${\displaystyle g}$. El array ${\displaystyle C}$ es ahora la convolución de los arrays ${\displaystyle A,B}$. Finalmente, el producto ${\displaystyle ab{\pmod {2}+1}}$ se da por evaluación

$${\displaystyle ab\equiv \sum ¿Qué? {2}+1}$$

Este algoritmo básico se puede mejorar de varias maneras. En primer lugar, no es necesario almacenar los dígitos de ${\displaystyle a,b}$ a la precisión arbitraria, pero sólo hasta ${\displaystyle n'+1}$ bits, que da una representación de máquina más eficiente de los arrays ${\displaystyle A,B}$. En segundo lugar, está claro que las multiplicaciones en las transformaciones de avance son simples cambios de bits. Con cierto cuidado, también es posible calcular la transformación inversa utilizando sólo turnos. Cuidar, por lo tanto es posible eliminar cualquier verdadera multiplicación del algoritmo excepto para donde el producto puntero ${\displaystyle {\widehat {C} {\fn} {\fnMicrosoft} {\fnK}} {\f}}} {\f}} {\f}} {\fnMicrosoft}} {\f}}} {\f}} {\fn}}}} {\\f}}}} {\f}}}}} {\\\\\\\fn\\\fnH}}}}}}}}}}}}}}}}}}}}\\\\\\\\\\\\\\f}}\\\\\\\\\\\\\\\\\\\\\\\\fnH\\\\\\\\\\\\\\\\\\\fnH}}}}}}}}}}}}}}}}}}}}\\\\\\\f}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} {\fnK} {\f} {\fnMicrosoft}} {\fnK}} {\f}} {\f}} {\f}}} {\f}}} {\f}}} {\f}}}}}} {\f}}} {\f}}} {\f}}}}} {\f}}}}}}} {\\f}}}} {\f}}}}}}}}}}}} {\\m}}}}}}}}}}}}}}} {\m}}} {\m} {\m}}}}}}}} {\m}}}}}}}}}}}}}}}}}} {\m} {\m}}}} {\m}}}} {\m}} {\m} {\m} {\m}}}}} {\f}}}} {\m} {\m}}}}{\m}}}}}} {\m}}} {\m}}}} {B}_{i}$ se evalúa. Por lo tanto, es ventajoso seleccionar los parámetros ${\displaystyle D,M}$ para que este producto puntero pueda ser realizado eficientemente, ya sea porque es una sola palabra de máquina o usando algún algoritmo optimizado para multiplicar enteros de un número de palabras (idealmente pequeño). Seleccionar los parámetros ${\displaystyle D,M}$ es por lo tanto un área importante para mayor optimización del método.

Detalles

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

${\displaystyle X=\sum ¿Qué?$

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

${\displaystyle XY=\left(\sum) ¿Por qué? ¿Por qué?$

Porque, por ${\displaystyle B^{k}$: ${\displaystyle ¿Qué? ¿Qué?$, Tenemos una convolución.

Mediante el uso de FFT (fast Fourier transform), utilizado en versión original en lugar de NTT, con la regla de la convolución; obtenemos

${\displaystyle {\hat {\f}(a*b)={\hat {f}\left(\sum) ¿Por qué?$

Eso es; ${\displaystyle ¿Qué? B_{k}$, donde ${\displaystyle C_{k}$es el coeficiente correspondiente en el espacio cuatro. Esto también se puede escribir como: fft(a * b) = fft(a) ● fft(b).

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

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

${\fnMicrosoft Sans Serif}(a\,X(\xi)+b\,Y(\xi))=a\,{\hat {X}(\xi)+b\,{\hat {Y}(\xi)}$

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

Hemos reducido nuestro problema de convolución al problema del producto, a través de FFT.

Al encontrar ifft (interpolación polinomial), para cada ${\displaystyle C_{k}$, uno consigue los coeficientes deseados.

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

Convolución bajo mod N

${\displaystyle ¿Qué?$, donde ${\displaystyle N(n)=2^{n}+1}$ y ${\displaystyle N(N)=2^{N}+1}$ en el algoritmo de Schönhage-Strassen.

Al permitir:

${\displaystyle A_{i}=\theta ^{i}a_{i}$ y ${\displaystyle ¿Qué?$

Donde ${\displaystyle \theta ^{N}=-1}$ es la raíz n-th

Se ve que:

${\displaystyle {\begin{aligned}C_{k}\sum _{(i,j):i+j=k\equiv {\pmod {N(n)}a_{i}b_{j}=\theta ¿Qué? ^{k}+\sum _{(i,j):i+j=k+n}a_{i}b_{j}\theta ^{n+k}\right)\[6pt] ventaja=\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 uno puede usar peso ${\displaystyle \theta ^{i}$, y luego se multiplica con ${\displaystyle \theta ^{-k}$ después.

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

${\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+k+n}a_{i}b_{j}$

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

$${\displaystyle \exp \left({\frac {2k\pi {\fn}}\correcto)=\cos {\fnMicroc {2k\pi} ################################################################################################################################################################################################################################################################ {2k\pi} } {n},\qquad k=0,1,\dotsn-1.}$$

${\displaystyle {\begin{aligned}C_{k} ^{-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] k/n}+\sum _{(i,j):i+j=k+n}a_{i}b_{j}e^{i2\pi (n+k)/n}\right)\end{aligned}}}$

Sin embargo, FFT también se puede utilizar como un NTT (general transformación teorética) en Schönhage–Strassen. Esto significa que tenemos que usar Silencio que generan números en un campo finito (por ejemplo ${\displaystyle \mathrm {GF} (2^{n}+1)}$).

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

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

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 {}(k)={\hat {\hat {\f}\left(\theta ^{-k}\left _{(i,j):i+j=k}a_{i}b_{j}\theta ^{k}+\sum _{(i,j):i+j=k+n}a_{i}b_{j}\theta ¿Por qué? ^{k}+\sum _{(i,j):i+j=n+2k}a_{i}b_{j}\theta ^{n+k}\right)\[6pt] ^{k}+\sum _{(i,j):i+j=2k+n}a_{i}b_{j}\theta ################################################################################################################################################################################################################################################################$

Primer producto da contribución a ${\displaystyle C_{k}$, para cada k. Segunda contribución ${\displaystyle C_{k}$debido a ${\displaystyle (i+j)}$ mod ${\displaystyle N(n)}$.

Para hacer el inverso:

${\displaystyle ¿Qué? }$ o ${\displaystyle ¿Qué?$

dependiendo de si fft usa datos normalizados o no.

Uno se multiplica por ${\displaystyle 2^{-m}$, para normailizar datos fft a un rango específico, donde ${\fnMicrosoft {\fn}}\equiv 2}{-m}{\bmod {N} {\n} {\fn}} {\fn}}$, donde m se encuentra utilizando inverso multiplicativo modular.

Detalles de implementación

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

En el algoritmo Schönhage–Strassen, ${\displaystyle N=2^{M}+1}$. Uno debe pensar en esto como un árbol binario, donde uno tiene valores en ${\displaystyle 0\leq {\text{index}\leq 2^{M}=2^{i+j}$. Dejando ${\displaystyle K\in [0,M]}$, una lata para cada K encontrar todos ${\displaystyle i+j=K}$: Uno puede agrupar todos ${\displaystyle (i,j)}$ pares en grupos M diferentes. Uso ${\displaystyle i+j=k}$ grupo ${\displaystyle (i,j)}$ pares a través de la convolución, es un problema clásico en algoritmos. Por ejemplo: Let k be total income and i ser hombres ingresos y j ingresos de las mujeres; mediante el uso de la convolución, se puede agrupar ${\displaystyle (i,j)}$ en K grupos basados en el ingreso total deseado.

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

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

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ía haber sido utilizado, por supuesto, con las mismas ventajas de número primo. Dejando ${\displaystyle N=2^{k}-1}$, uno tiene el número máximo en un número binario con ${\displaystyle k+1}$ bits. ${\displaystyle N=2^{k}-1}$ es un número de Mersenne, que en algunos casos es un Mersenne primo. Es un candidato natural contra el número de Fermat ${\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 productos enteros. 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

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:

${\displaystyle G_{q,p,n}=\sum ¿Por qué? {\fn} {\fn}} {\fn}} {\fn}}} {\fn}}}} {\fn}}} {\fn}}}} {\fn}}}}}}} {\fn}}}}}}}}}}}}}}}}}}} {\fn}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} {}}}}}}}}}}}} {}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} {}}}}}}}}}}}}}}}}}}}}}}}}}}}}}}} {}}}}}}}}}}}}}}}}}}} {\}}}}}}}}}}}}}}}}}}}}$

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

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

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

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

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

Si ${\displaystyle N=2^{t}$, donde ${\displaystyle 1\leq t\leq n}$Entonces ${\displaystyle g_{t}=a^{(2^{n}-1)2^{n-t}}$.

Cómo elegir K para un N específico

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

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

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

Si uno asume eficiencia por encima del 50%, ${\displaystyle {\frac {\fn}\leq {\fnK}}K\leq n}$ y k es muy pequeño en comparación con el resto de la fórmula;

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

Esto significa: Cuando algo es muy efectivo; K está obligado por encima ${\displaystyle 2{\sqrt {N}}$ o asintotípicamente ligados arriba por ${\displaystyle {\sqrt {N}}$

Pseudocódigo

A continuación del algoritmo, el algoritmo de multiplicación modular estándar de Schönhage-Strassen (con algunas optimizaciones) se encuentra en una descripción general a través de

• T3MUL = Toom–Cook multiplication
• SMUL = multiplicación de Schönhage–Strassen
• Evaluación = FFT/IFFT

Estudio adicional

Para obtener detalles sobre la implementación, se puede leer el libro Números primos: una perspectiva computacional. 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 El arte de la programación informática de Knuth.

Optimizaciones

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

Uso de otro algoritmo de multiplicaciones, algoritmo interno

Por debajo de un determinado punto de corte, es más eficiente utilizar otros algoritmos de multiplicación, como la multiplicación de Toom-Cook.

Raíz cuadrada de 2 truco

La idea es usar ${\displaystyle {\sqrt {2}}$ como raíz de la unidad del orden ${\displaystyle 2^{n+2}$ en campo finito ${\displaystyle \mathrm {GF} (2^{n+2}+1)}$ (es una solución a la ecuación ${\displaystyle \theta ^{2^{n+2}\equiv 1{\pmod {2^{n+2}+1}}}}$), cuando los valores de ponderación en NTT (número de transformación teorética) enfoque. Se ha demostrado que ahorra un 10% en tiempo de multiplicación entero.

El truco de Granlund

Dejando ${\displaystyle m=N+h}$; uno puede calcular ${\displaystyle uv{\bmod {2}+1}}$ y ${\displaystyle (u{h}})(v{\bmod {2}}}} {h}}}}}$. En combinación con CRT (Teorema de Restante chino), a encontrar valores exactos de la multiplicación uv