Tamiz cuadrático

Algoritmo de factorización de números enteros

El algoritmo de la criba cuadrática ( QS ) es un algoritmo de factorización de números enteros y, en la práctica, el segundo método más rápido conocido (después de la criba de cuerpos numéricos generales ). Sigue siendo el más rápido para números enteros de menos de 100 dígitos decimales o más, y es considerablemente más simple que la criba de cuerpos numéricos. Es un algoritmo de factorización de propósito general, lo que significa que su tiempo de ejecución depende únicamente del tamaño del número entero a factorizar, y no de una estructura o propiedades especiales. Fue inventado por Carl Pomerance en 1981 como una mejora de la criba lineal de Schröppel . ^[1]

Objetivo básico

El algoritmo intenta establecer una congruencia de cuadrados módulo n (el entero que se va a factorizar), lo que a menudo conduce a una factorización de n . El algoritmo funciona en dos fases: la fase de recopilación de datos , donde recopila información que puede conducir a una congruencia de cuadrados; y la fase de procesamiento de datos , donde coloca todos los datos que ha recopilado en una matriz y la resuelve para obtener una congruencia de cuadrados. La fase de recopilación de datos se puede paralelizar fácilmente en muchos procesadores, pero la fase de procesamiento de datos requiere grandes cantidades de memoria y es difícil de paralelizar de manera eficiente en muchos nodos o si los nodos de procesamiento no tienen cada uno suficiente memoria para almacenar la matriz completa. El algoritmo de bloques de Wiedemann se puede utilizar en el caso de unos pocos sistemas, cada uno capaz de almacenar la matriz.

El método ingenuo para hallar una congruencia de cuadrados consiste en elegir un número aleatorio, elevarlo al cuadrado, dividirlo por n y esperar que el residuo menos no negativo sea un cuadrado perfecto . Por ejemplo, . Este método sólo encuentra una congruencia de cuadrados en raras ocasiones para n grandes , pero cuando la encuentra, la mayoría de las veces, la congruencia no es trivial y la factorización está completa. Esta es, en líneas generales, la base del método de factorización de Fermat . ${\displaystyle 80^{2}\equiv 441=21^{2}{\pmod {5959}}}$

La criba cuadrática es una modificación del método de factorización de Dixon . Se supone que el tiempo de ejecución general requerido para la criba cuadrática (para factorizar un entero n ) es

${\displaystyle e^{(1+o(1)){\sqrt {\ln n\ln \ln n}}}=L_{n}\left[1/2,1\right]}$

en la notación L. ^[2] La constante e es la base del logaritmo natural.

El enfoque

Para factorizar el entero n , el método de Fermat implica la búsqueda de un único número a , n ^1/2 < a < n −1 , tal que el resto de a ² dividido por n sea un cuadrado. Pero estos a son difíciles de encontrar. La criba cuadrática consiste en calcular el resto de a ² / n para varios a , y luego encontrar un subconjunto de estos cuyo producto sea un cuadrado. Esto dará como resultado una congruencia de cuadrados.

Por ejemplo, considere intentar factorizar el número 1649. Tenemos: . Ninguno de los números enteros es un cuadrado, pero el producto es un cuadrado. También teníamos ${\displaystyle 41^{2}\equiv 32,42^{2}\equiv 115,43^{2}\equiv 200{\pmod {1649}}}$ ${\displaystyle 32,115,200}$ ${\displaystyle 32\cdot 200=80^{2}}$

${\displaystyle 32\cdot 200\equiv 41^{2}\cdot 43^{2}=(41\cdot 43)^{2}\equiv 114^{2}{\pmod {1649}}}$

ya que . La observación que así da una congruencia de cuadrados ${\displaystyle 41\cdot 43\equiv 114{\pmod {1649}}}$ ${\displaystyle 32\cdot 200=80^{2}}$

${\displaystyle 114^{2}\equiv 80^{2}{\pmod {1649}}.}$

Por lo tanto, para algún entero . Podemos entonces factorizar ${\displaystyle 114^{2}-80^{2}=(114+80)\cdot (114-80)=194\cdot 34=k\cdot 1649}$ ${\displaystyle k}$

${\displaystyle 1649=\gcd(194,1649)\cdot \gcd(34,1649)=97\cdot 17}$

utilizando el algoritmo euclidiano para calcular el máximo común divisor .

Así que el problema ahora se ha reducido a: dado un conjunto de números enteros, encuentre un subconjunto cuyo producto sea un cuadrado. Por el teorema fundamental de la aritmética , cualquier número entero positivo puede escribirse de forma única como un producto de potencias primos . Hacemos esto en un formato vectorial; por ejemplo, la factorización de potencias primos de 504 es 2 ³ 3 ² 5 ⁰ 7 ¹ , por lo tanto, se representa por el vector exponente (3,2,0,1). Multiplicar dos números enteros corresponde entonces a sumar sus vectores exponentes. Un número es un cuadrado cuando su vector exponente es par en cada coordenada. Por ejemplo, los vectores (3,2,0,1) + (1,0,0,1) = (4,2,0,2), por lo que (504)(14) es un cuadrado. Para buscar un cuadrado es necesario conocer únicamente la paridad de los números en los vectores, por lo que basta con calcular estos vectores módulo 2: (1,0,0,1) + (1,0,0,1) = (0,0,0,0). Por lo tanto, dado un conjunto de vectores (0,1), necesitamos encontrar un subconjunto que sume al vector cero módulo 2.

Este es un problema de álgebra lineal ya que el anillo puede considerarse como el campo de Galois de orden 2, es decir, podemos dividir por todos los números distintos de cero (solo hay uno, es decir, 1) al calcular el módulo 2. Es un teorema del álgebra lineal que con más vectores que entradas tiene cada vector, siempre existe una dependencia lineal . Se puede encontrar por eliminación gaussiana . Sin embargo, simplemente elevar al cuadrado muchos números aleatorios módulo n produce una gran cantidad de factores primos diferentes y, por lo tanto, vectores muy largos y una matriz muy grande. El truco es buscar específicamente números a tales que a ² módulo n tenga solo factores primos pequeños (son números suaves ). Son más difíciles de encontrar, pero usar solo números suaves mantiene los vectores y matrices más pequeños y más manejables. La criba cuadrática busca números suaves utilizando una técnica llamada tamizado , que se analiza más adelante, de la que el algoritmo toma su nombre. ${\displaystyle \mathbb {Z} /2\mathbb {Z} }$

El algoritmo

Para resumir, el algoritmo básico de tamiz cuadrático tiene estos pasos principales:

1. Elija un límite de suavidad B . El número π( B ), que denota la cantidad de números primos menores que B , controlará tanto la longitud de los vectores como la cantidad de vectores necesarios.
2. Utilice el tamizado para localizar π( B ) + 1 números a _i tales que b _i = ( a _i ² mod n ) es B -suave.
3. Factoriza el b _i y genera vectores exponentes mod 2 para cada uno.
4. Utilice el álgebra lineal para encontrar un subconjunto de estos vectores que, sumados, den como resultado el vector cero. Multiplique los a _i correspondientes y dé al resultado módulo n el nombre a ; de manera similar, multiplique los b _{i ,} lo que da como resultado un cuadrado B -suave b ² .
5. Ahora nos queda la igualdad a ² = b ² mod n de la cual obtenemos dos raíces cuadradas de ( a ² mod n ), una tomando la raíz cuadrada en los números enteros de b ^{2 ,} es decir b , y la otra a calculada en el paso 4.
6. Ahora tenemos la identidad deseada: . Calcular el MCD de n con la diferencia (o suma) de a y b . Esto produce un factor, aunque puede ser un factor trivial ( n o 1). Si el factor es trivial, intentar de nuevo con una dependencia lineal diferente o un a diferente . ${\displaystyle (a+b)(a-b)\equiv 0{\pmod {n}}}$

El resto de este artículo explica detalles y extensiones de este algoritmo básico.

Cómo QS optimiza la búsqueda de congruencias

La criba cuadrática intenta encontrar pares de números enteros x e y ( x ) (donde y ( x ) es una función de x ) que satisfacen una condición mucho más débil que x ² ≡ y ² (mod n ). Selecciona un conjunto de primos llamado base factorial e intenta encontrar x de manera que el residuo absoluto mínimo de y ( x ) = x ² mod n se factorice completamente sobre la base factorial. Se dice que dichos valores de y son suaves con respecto a la base factorial.

La factorización de un valor de y ( x ) que se divide en la base de factores, junto con el valor de x , se conoce como una relación . La criba cuadrática acelera el proceso de búsqueda de relaciones al tomar x cerca de la raíz cuadrada de n . Esto garantiza que y ( x ) será más pequeño y, por lo tanto, tendrá una mayor probabilidad de ser uniforme.

${\displaystyle y(x)=\left(\left\lceil {\sqrt {n}}\right\rceil +x\right)^{2}-n{\hbox{ (where }}x{\hbox{ is a small integer)}}}$

${\displaystyle y(x)\approx 2x\left\lceil {\sqrt {n}}\right\rceil }$

Esto implica que y es del orden de 2 x [ √ n ]. Sin embargo, también implica que y crece linealmente con x multiplicado por la raíz cuadrada de n .

Otra forma de aumentar la probabilidad de suavizado es simplemente aumentando el tamaño de la base factorial. Sin embargo, es necesario encontrar al menos una relación suavizada mayor que el número de primos en la base factorial, para asegurar la existencia de una dependencia lineal.

Relaciones parciales y ciclos

Incluso si para alguna relación y ( x ) no es uniforme, puede ser posible fusionar dos de estas relaciones parciales para formar una completa, si las dos y son productos de los mismos primos fuera de la base factorial. [Tenga en cuenta que esto es equivalente a extender la base factorial.] Por ejemplo, si la base factorial es {2, 3, 5, 7} y n = 91, existen relaciones parciales:

${\displaystyle {21^{2}\equiv 7^{1}\cdot 11{\pmod {91}}}}$

${\displaystyle {29^{2}\equiv 2^{1}\cdot 11{\pmod {91}}}}$

Multiplique estos juntos:

${\displaystyle {(21\cdot 29)^{2}\equiv 2^{1}\cdot 7^{1}\cdot 11^{2}{\pmod {91}}}}$

y multiplica ambos lados por (11 ⁻¹ ) ² módulo 91. 11 ⁻¹ módulo 91 es 58, entonces:

${\displaystyle (58\cdot 21\cdot 29)^{2}\equiv 2^{1}\cdot 7^{1}{\pmod {91}}}$

${\displaystyle 14^{2}\equiv 2^{1}\cdot 7^{1}{\pmod {91}}}$

producir una relación completa. Una relación completa de este tipo (obtenida mediante la combinación de relaciones parciales) se denomina ciclo . A veces, la formación de un ciclo a partir de dos relaciones parciales conduce directamente a una congruencia de cuadrados, pero rara vez ocurre.

Comprobación de la suavidad mediante tamizado

Existen varias formas de comprobar la suavidad de las y . La más obvia es mediante división por tanteo , aunque esto aumenta el tiempo de ejecución de la fase de recopilación de datos. Otro método que tiene cierta aceptación es el método de curva elíptica (ECM). En la práctica, se suele utilizar un proceso llamado tamizado . Si f ( x ) es el polinomio que tenemos ${\displaystyle f(x)=x^{2}-n}$

${\displaystyle {\begin{aligned}f(x)&=x^{2}-n\\f(x+kp)&=(x+kp)^{2}-n\\&=x^{2}+2xkp+(kp)^{2}-n\\&=f(x)+2xkp+(kp)^{2}\equiv f(x){\pmod {p}}\end{aligned}}}$

De esta manera, al resolver f(x) ≡ 0 (mod p ) para x, se genera una secuencia completa de números y para los cuales y = f ( x ), todos los cuales son divisibles por p . Esto es hallar una raíz cuadrada módulo un primo, para lo cual existen algoritmos eficientes, como el algoritmo de Shanks-Tonelli . (De aquí es de donde la criba cuadrática obtiene su nombre: y es un polinomio cuadrático en x , y el proceso de cribado funciona como la Criba de Eratóstenes .)

El tamiz comienza poniendo a cero cada entrada en una gran matriz A [] de bytes. Para cada p , resuelva la ecuación cuadrática módulo  p para obtener dos raíces α y β , y luego agregue una aproximación a log( p ) a cada entrada para la que y ( x ) = 0 mod p ... es decir, A [ kp  +  α ] y A [ kp  +  β ]. También es necesario resolver la ecuación cuadrática módulo pequeñas potencias de p para reconocer números divisibles por pequeñas potencias de un primo de base factorial.

Al final de la base factorial, cualquier A [] que contenga un valor por encima de un umbral de aproximadamente log( x ² − n ) corresponderá a un valor de y ( x ) que se divide en la base factorial. La información sobre exactamente qué primos dividen a y ( x ) se ha perdido, pero solo tiene factores pequeños, y hay muchos buenos algoritmos para factorizar un número que se sabe que solo tiene factores pequeños, como la división de prueba por primos pequeños, SQUFOF , Pollard rho y ECM, que generalmente se usan en alguna combinación.

Hay muchos valores de y ( x ) que funcionan, por lo que el proceso de factorización al final no tiene que ser completamente confiable; a menudo los procesos se comportan mal en, digamos, el 5 % de las entradas, lo que requiere una pequeña cantidad de tamizado adicional.

Ejemplo de tamiz básico

Este ejemplo demostrará el uso de una criba cuadrática estándar sin optimizaciones logarítmicas ni potencias primos. Sea el número a factorizar N = 15347, por lo tanto, el límite superior de la raíz cuadrada de N es 124. Como N es pequeño, el polinomio básico es suficiente: y ( x ) = ( x + 124) ² − 15347.

Recopilación de datos

Como N es pequeño, solo se necesitan cuatro primos. Los primeros cuatro primos p para los cuales 15347 tiene una raíz cuadrada módulo p son 2, 17, 23 y 29 (en otras palabras, 15347 es un residuo cuadrático módulo cada uno de estos primos). Estos primos serán la base para el cribado.

Ahora construimos nuestro tamiz y comenzamos el proceso de tamizado para cada primo en la base, eligiendo tamizar el primer 0 ≤ X < 100 de Y(X): ${\displaystyle V_{X}}$ ${\displaystyle Y(X)=(X+\lceil {\sqrt {N}}\rceil )^{2}-N=(X+124)^{2}-15347}$

${\displaystyle {\begin{aligned}V&={\begin{bmatrix}Y(0)&Y(1)&Y(2)&Y(3)&Y(4)&Y(5)&\cdots &Y(99)\end{bmatrix}}\\&={\begin{bmatrix}29&278&529&782&1037&1294&\cdots &34382\end{bmatrix}}\end{aligned}}}$

El siguiente paso es realizar la criba. Para cada p en nuestra base de factores resuelve la ecuación ${\displaystyle \lbrace 2,17,23,29\rbrace }$

${\displaystyle Y(X)\equiv (X+\lceil {\sqrt {N}}\rceil )^{2}-N\equiv 0{\pmod {p}}}$

para encontrar las entradas en la matriz V que son divisibles por p .

Para resolver para obtener la solución . ${\displaystyle p=2}$ ${\displaystyle (X+124)^{2}-15347\equiv 0{\pmod {2}}}$ ${\displaystyle X\equiv {\sqrt {15347}}-124\equiv 1{\pmod {2}}}$

Por lo tanto, comenzando en X=1 e incrementando en 2, cada entrada será divisible por 2. Dividir cada una de esas entradas por 2 da como resultado

${\displaystyle V={\begin{bmatrix}29&139&529&391&1037&647&\cdots &17191\end{bmatrix}}}$

De manera similar, para los demás primos p en la ecuación se resuelve. Nótese que para cada p > 2, habrá 2 ecuaciones lineales resultantes debido a que hay 2 raíces cuadradas modulares. ${\displaystyle \lbrace 17,23,29\rbrace }$ ${\displaystyle X\equiv {\sqrt {15347}}-124{\pmod {p}}}$

${\displaystyle {\begin{aligned}X&\equiv {\sqrt {15347}}-124&\equiv 8-124&\equiv 3{\pmod {17}}\\&&\equiv 9-124&\equiv 4{\pmod {17}}\\X&\equiv {\sqrt {15347}}-124&\equiv 11-124&\equiv 2{\pmod {23}}\\&&\equiv 12-124&\equiv 3{\pmod {23}}\\X&\equiv {\sqrt {15347}}-124&\equiv 8-124&\equiv 0{\pmod {29}}\\&&\equiv 21-124&\equiv 13{\pmod {29}}\\\end{aligned}}}$

Cada ecuación resulta divisible por p en x = a y cada valor p más allá de ese. Dividiendo V por p en a , a + p , a +2 p , a +3 p , etc., para cada primo en la base se encuentran los números lisos que son productos de primos únicos (primeras potencias). ${\displaystyle X\equiv a{\pmod {p}}}$ ${\displaystyle V_{x}}$

${\displaystyle V={\begin{bmatrix}1&139&23&1&61&647&\cdots &17191\end{bmatrix}}}$

Cualquier entrada de V que sea igual a 1 corresponde a un número liso. Como , , y son iguales a uno, esto corresponde a: ${\displaystyle V_{0}}$ ${\displaystyle V_{3}}$ ${\displaystyle V_{71}}$

Procesamiento de matrices

Dado que se han encontrado números suaves Y con la propiedad , el resto del algoritmo se sigue de manera equivalente a cualquier otra variación del método de factorización de Dixon . ${\displaystyle Y\equiv Z^{2}{\pmod {N}}}$

Escritura de los exponentes del producto de un subconjunto de las ecuaciones

${\displaystyle {\begin{aligned}29&=2^{0}\cdot 17^{0}\cdot 23^{0}\cdot 29^{1}\\782&=2^{1}\cdot 17^{1}\cdot 23^{1}\cdot 29^{0}\\22678&=2^{1}\cdot 17^{1}\cdot 23^{1}\cdot 29^{1}\\\end{aligned}}}$

Como matriz se obtiene: ${\displaystyle {\pmod {2}}}$

${\displaystyle S\cdot {\begin{bmatrix}0&0&0&1\\1&1&1&0\\1&1&1&1\end{bmatrix}}\equiv {\begin{bmatrix}0&0&0&0\end{bmatrix}}{\pmod {2}}}$

Una solución a la ecuación está dada por el espacio nulo izquierdo , simplemente

${\displaystyle S={\begin{bmatrix}1&1&1\end{bmatrix}}}$

Por lo tanto, el producto de las tres ecuaciones da como resultado un cuadrado (mod N).

${\displaystyle 29\cdot 782\cdot 22678=22678^{2}}$

y

${\displaystyle 124^{2}\cdot 127^{2}\cdot 195^{2}=3070860^{2}}$

Así que el algoritmo encontró

${\displaystyle 22678^{2}\equiv 3070860^{2}{\pmod {15347}}}$

Al probar el resultado se obtiene MCD(3070860 - 22678, 15347) = 103, un factor no trivial de 15347, siendo el otro 149.

Esta demostración también debería servir para mostrar que la criba cuadrática sólo es apropiada cuando n es grande. Para un número tan pequeño como 15347, este algoritmo es excesivo. La división por tanteo o la rho de Pollard podrían haber encontrado un factor con mucho menos cálculo.

Polinomios múltiples

En la práctica, se utilizan muchos polinomios diferentes para y, de modo que cuando y ( x ) comienza a volverse grande, lo que da como resultado una densidad pobre de y suave , este crecimiento se puede restablecer cambiando los polinomios. Como es habitual, elegimos y ( x ) como un cuadrado módulo n , pero ahora con la forma

$${\displaystyle y(x)=(Ax+B)^{2}-n\qquad A,B\in \mathbb {Z} .}$$

${\displaystyle B}$se elige de modo que , por lo que para algún . El polinomio y(x) puede escribirse entonces como . Si A es un cuadrado o un número suavizado, entonces solo se debe comprobar la suavidad del factor. ${\displaystyle B^{2}=n{\pmod {A}}}$ ${\displaystyle B^{2}-n=AC}$ ${\displaystyle C}$ ${\displaystyle y(x)=A\cdot (Ax^{2}+2Bx+C)}$ ${\displaystyle (Ax^{2}+2Bx+C)}$

Este enfoque, llamado Multiple Polynomial Quadratic Sieve (MPQS), es ideal para la paralelización , ya que a cada procesador involucrado en la factorización se le puede dar n , la base de factores y una colección de polinomios, y no tendrá necesidad de comunicarse con el procesador central hasta que haya terminado de tamizar con sus polinomios.

Primos grandes

Un gran primo

Si, después de dividir por todos los factores menores que A , la parte restante del número (el cofactor) es menor que A ² , entonces este cofactor debe ser primo. En efecto, se puede agregar a la base de factores, ordenando la lista de relaciones por cofactor. Si y(a) = 7*11*23*137 e y(b) = 3*5*7*137, entonces y(a)y(b) = 3*5*11*23 * 7 ² * 137 ² . Esto funciona reduciendo el umbral de entradas en la matriz de tamizado por encima del cual se realiza una factorización completa.

Más números primos grandes

Reduciendo aún más el umbral y utilizando un proceso eficaz para factorizar valores y(x) en productos de primos relativamente grandes (el ECM es excelente para esto) se pueden encontrar relaciones con la mayoría de sus factores en la base de factores, pero con dos o incluso tres primos más grandes. La búsqueda de ciclos permite entonces combinar un conjunto de relaciones que comparten varios primos en una sola relación.

Parámetros de un ejemplo realista

Para ilustrar las opciones de parámetros típicos para un ejemplo realista en una implementación real que incluye las optimizaciones de polinomios múltiples y primos grandes, se ejecutó la herramienta msieve en un semiprimo de 267 bits , produciendo los siguientes parámetros:

• Factorización de prueba: valor de corte de 27 bits
• Intervalo de tamiz (por polinomio): 393216 (12 bloques de tamaño 32768)
• Límite de suavidad: 1300967 (50294 primos)
• Número de factores para los coeficientes del polinomio A : 10 (ver Polinomios múltiples arriba)
• Límite de primos grandes: 128795733 (26 bits) (ver Primos grandes arriba)
• Valores suaves encontrados: 25952 mediante tamizado directo, 24462 mediante combinación de números con primos grandes
• Tamaño final de la matriz: 50294 × 50414, reducido mediante filtrado a 35750 × 35862
• Dependencias no triviales encontradas: 15
• Tiempo total (en un UltraSPARC III de 1,6 GHz): 35 min 39 segundos
• Memoria máxima utilizada: 8 MB

Registros de factorización

Hasta el descubrimiento de la criba de cuerpos numéricos (NFS), QS era el algoritmo de factorización de propósito general conocido más rápido desde el punto de vista asintótico. Ahora, la factorización de curva elíptica de Lenstra tiene el mismo tiempo de ejecución asintótico que QS (en el caso en que n tiene exactamente dos factores primos de igual tamaño), pero en la práctica, QS es más rápido ya que utiliza operaciones de precisión simple en lugar de las operaciones de precisión múltiple que utiliza el método de curva elíptica.

El 2 de abril de 1994 se completó la factorización de RSA-129 utilizando QS. Era un número de 129 dígitos, el producto de dos primos grandes, uno de 64 dígitos y el otro de 65 dígitos. La base factorial para esta factorización contenía 524339 primos. La fase de recolección de datos tomó 5000 MIPS-años, realizada de manera distribuida a través de Internet. Los datos recopilados totalizaron 2 GB . La fase de procesamiento de datos tomó 45 horas en la supercomputadora MasPar (masivamente paralela) de Bellcore (ahora Telcordia Technologies ) . Esta fue la factorización más grande publicada por un algoritmo de propósito general, hasta que se utilizó NFS para factorizar RSA-130 , completada el 10 de abril de 1996. Todos los números RSA factorizados desde entonces se han factorizado utilizando NFS.

El récord actual de factorización de QS es el RSA-140 de 140 dígitos (463 bits), que fue factorizado por Patrick Konsor en junio de 2020 utilizando aproximadamente 6000 horas de núcleo durante 6 días. ^[3]

Implementaciones

• PPMPQS y PPSIQS
• mpqs
• SIMPQS es una implementación rápida de la criba cuadrática de polinomios múltiples autoinicializante escrita por William Hart. Proporciona soporte para la variante de primos grandes y utiliza la implementación de Lanczos en bloque de Jason Papadopoulos para la etapa de álgebra lineal. SIMPQS es accesible como el comando qsieve en el paquete de álgebra computacional de SageMath , es parte de la Biblioteca rápida para teoría de números o se puede descargar en formato fuente. SIMPQS está optimizado para su uso en máquinas Athlon y Opteron, pero funcionará en las arquitecturas más comunes de 32 y 64 bits. Está escrito completamente en C.
• una aplicación de factorización de Dario Alpern, que utiliza la criba cuadrática si se cumplen ciertas condiciones.
• El paquete de álgebra computacional PARI/GP incluye una implementación de la criba cuadrática de polinomios múltiples con inicialización automática que implementa la variante de primos grandes. Fue adaptada por Thomas Papanikolaou y Xavier Roblot a partir de una criba escrita para el proyecto LiDIA. El esquema de inicialización automática se basa en una idea de la tesis de Thomas Sosnowski.
• En el paquete de álgebra computacional MAGMA se encuentra disponible una variante de la criba cuadrática . Se basa en una implementación de Arjen Lenstra de 1995, utilizada en su programa de "factorización por correo electrónico".
• msieve, una implementación de la criba cuadrática de polinomios múltiples con soporte para primos grandes simples y dobles, escrita por Jason Papadopoulos. El código fuente y un binario de Windows están disponibles.
• YAFU, escrito por Ben Buhrow, es probablemente la implementación más rápida disponible del tamiz cuadrático. Por ejemplo, RSA-100 se calculó en menos de 15 minutos en cuatro núcleos de una CPU Xeon 6248 de 2,5 GHz. Todas las subrutinas críticas utilizan instrucciones SIMD AVX2 o AVX-512 para procesadores AMD o Intel. Utiliza el código Lanczos en bloque de Jason Papadopoulos. El código fuente y los binarios para Windows y Linux están disponibles.
• Ariel, una implementación sencilla en Java de la criba cuadrática para fines didácticos.
• La biblioteca java-math-library contiene probablemente el tamiz cuadrático más rápido escrito en Java (el sucesor de PSIQS 4.0).
• Java QS, un proyecto Java de código abierto que contiene la implementación básica de QS. Publicado el 4 de febrero de 2016 por Ilya Gazman
• C Quadratic Sieve, un factorizador escrito completamente en C que contiene la implementación de Quadratic Sieve con inicialización automática. El proyecto está inspirado en el factorizador FLINT de William Hart. El código fuente publicado en 2022 por Michel Leonard no depende de una biblioteca externa, es capaz de factorizar números de 240 bits en un minuto y números de 300 bits en 2 horas.
• El paquete RcppBigIntAlgos de Joseph Wood proporciona una implementación eficiente de la criba cuadrática de polinomios múltiples para el lenguaje de programación R. Está escrito en C++ y es capaz de factorizar cómodamente números semiprimos de 100 dígitos . Por ejemplo, un semiprimo de 300 bits (91 dígitos) se factorizó en 1 hora y el RSA-100 se factorizó en menos de 10 horas en una MacBook Air con un procesador Apple M2.

Véase también

• Factorización de curva elíptica de Lenstra
• prueba de primalidad

Referencias

1. Carl Pomerance, Análisis y comparación de algunos algoritmos de factorización de enteros, en Métodos computacionales en teoría de números, Parte I, HW Lenstra, Jr. y R. Tijdeman, eds., Math. Centre Tract 154, Ámsterdam, 1982, págs. 89-139.
2. Pomerance, Carl (diciembre de 1996). "A Tale of Two Sieves" (PDF) . Avisos de la AMS . Vol. 43, núm. 12. págs. 1473–1485.
3. "Logro inútil: factorización RSA-140 con tamiz cuadrático - mersenneforum.org" www.mersenneforum.org . Consultado el 7 de julio de 2020 .

• Crandall, Richard ; Pomerance, Carl (2001). "Sección 6.1: El método de factorización de criba cuadrática". Números primos: una perspectiva computacional (1.ª ed.). Springer. pp. 227–244. ISBN 0-387-94777-9.
• Wagstaff, Samuel S. Jr. (2013). El placer de factorizar . Providence, RI: American Mathematical Society . págs. 195–202. ISBN. 978-1-4704-1048-3.
• Contini, Scott Patrick (1997). Factorización de números enteros con la criba cuadrática autoinicializante (PDF) (tesis de maestría). Universidad de Georgia. Archivado desde el original (PDF) el 5 de abril de 2015. Describe muchos detalles de implementación práctica.

Otros enlaces externos

• Documento de referencia "El algoritmo de factorización de tamiz cuadrático" de Eric Landquist