tamiz cuadrático

Algoritmo de factorización de enteros

El algoritmo de criba cuadrática ( QS ) es un algoritmo de factorización de enteros y, en la práctica, el segundo método más rápido conocido (después del tamiz de campo numérico general ). Sigue siendo el más rápido para números enteros de menos de 100 dígitos decimales aproximadamente, y es considerablemente más simple que el tamiz de campos 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 del tamiz lineal de Schroeppel . ^[1]

Objetivo básico

El algoritmo intenta establecer una congruencia de cuadrados módulo n (el número entero 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 pone 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 con muchos procesadores, pero la fase de procesamiento de datos requiere grandes cantidades de memoria y es difícil paralelizar de manera eficiente en muchos nodos o si los nodos de procesamiento no tienen cada uno de ellos suficiente memoria para almacenar toda la matriz. El algoritmo de bloques de Wiedemann se puede utilizar en el caso de unos pocos sistemas, cada uno de ellos capaz de contener la matriz.

El enfoque ingenuo para encontrar una congruencia de cuadrados es elegir un número aleatorio, elevarlo al cuadrado, dividirlo por n y esperar que el resto menos no negativo sea un cuadrado perfecto . Por ejemplo, . Este enfoque encuentra una congruencia de cuadrados rara vez para n grande , pero cuando encuentra una, la mayoría de las veces, la congruencia no es trivial y la factorización es completa. Esta es aproximadamente 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 . El tiempo de ejecución general requerido para el tamiz cuadrático (para factorizar un número 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 número 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 son difíciles de encontrar. La criba cuadrática consiste en calcular el resto de a ² / n para varios a , para luego encontrar un subconjunto de estos cuyo producto sea un cuadrado. Esto producirá 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 tuvimos ${\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}}}$

desde . La observación que da así 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 número entero . Entonces podemos 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, encontrar un subconjunto cuyo producto sea un cuadrado. Según el teorema fundamental de la aritmética , cualquier número entero positivo puede escribirse únicamente como producto de potencias primas . Hacemos esto en formato vectorial; por ejemplo, la factorización de potencias primas de 504 es 2 ³ 3 ² 5 ⁰ 7 ¹ , por lo tanto está representada por el vector exponente (3,2,0,1). Multiplicar dos números enteros corresponde entonces a sumar sus vectores exponentes. Un número es cuadrado cuando su vector exponente es par en todas las coordenadas. Por ejemplo, los vectores (3,2,0,1) + (1,0,0,1) = (4,2,0,2), entonces (504)(14) es un cuadrado. La búsqueda de un cuadrado requiere conocimiento únicamente de la paridad de los números en los vectores, por lo que es suficiente calcular estos vectores mod 2: (1,0,0,1) + (1,0,0,1) = (0 ,0,0,0). Entonces, dado un conjunto de (0,1) -vectores, necesitamos encontrar un subconjunto que se sume al vector cero mod 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, a saber, 1) al calcular el módulo 2. Es un teorema de álgebra lineal que con más vectores de los que cada vector tiene entradas, siempre existe una dependencia lineal . Se puede encontrar mediante eliminación gaussiana . Sin embargo, simplemente elevar al cuadrado muchos números aleatorios mod n produce una gran cantidad de factores primos diferentes y, por lo tanto, vectores muy largos y una matriz muy grande. El truco consiste ^en buscar específicamente números a tales que 2 mod n tenga solo factores primos pequeños (son números suaves ). Son más difíciles de encontrar, pero usar sólo números suaves mantiene los vectores y matrices más pequeños y manejables. La criba cuadrática busca números uniformes utilizando una técnica llamada cribado , que se analiza más adelante, de donde el algoritmo toma su nombre. ${\displaystyle \mathbb {Z} /2\mathbb {Z} }$

el algoritmo

En resumen, 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 el número de números primos menores que B , controlará tanto la longitud de los vectores como el número de vectores necesarios.
2. Utilice el tamizado para localizar π( B ) + 1 números a _i tales que b _i = ( a _i ² mod n ) sea B -liso.
3. Factoriza el b _i y genera vectores exponentes mod 2 para cada uno.
4. Utilice álgebra lineal para encontrar un subconjunto de estos vectores que se suman al vector cero. Multiplica los a _i correspondientes y dale al resultado mod n el nombre a ; de manera similar, multiplique el b _i para obtener un cuadrado B liso 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 de los números enteros de b ² es decir b , y la otra la a calculada en el paso 4.
6. Ahora tenemos la identidad deseada: . Calcule el MCD de n con la diferencia (o suma) de a y b . Esto produce un factor, aunque puede ser un factor trivial ( no 1). Si el factor es trivial, intente nuevamente con una dependencia lineal diferente o 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 números primos llamado base del factor e intenta encontrar x tal que el resto mínimo absoluto de y ( x ) = x ² mod n se factorice completamente sobre la base del factor. Se dice que estos valores de y son suaves con respecto a la base del factor.

La factorización de un valor de y ( x ) que se divide sobre la base del factor, junto con el valor de x , se conoce como relación . La criba cuadrática acelera el proceso de encontrar relaciones al acercar x a la raíz cuadrada de n . Esto asegura que y ( x ) será más pequeño y, por lo tanto, tendrá mayores posibilidades de ser suave.

${\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 las posibilidades de suavidad es simplemente aumentando el tamaño de la base del factor. Sin embargo, es necesario encontrar al menos una relación suave mayor que el número de primos en la base de factores, para asegurar la existencia de una dependencia lineal.

Relaciones parciales y ciclos.

Incluso si para alguna relación y ( x ) no es uniforme, es 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 del factor. [Tenga en cuenta que esto equivale a ampliar la base del factor.] Por ejemplo, si la base del factor 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}}}}$

Multiplica 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}}}$

produciendo una relación plena. Tal relación completa (obtenida combinando relaciones parciales) se llama ciclo . A veces, formar un ciclo a partir de dos relaciones parciales conduce directamente a una congruencia de cuadrados, pero rara vez.

Comprobar la suavidad mediante tamizado

Hay varias formas de comprobar la suavidad de las y s. La más obvia es por división de prueba , 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 la curva elíptica (ECM). En la práctica, se suele utilizar un proceso llamado tamizado . Si f ( x ) es el polinomio 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}}}$

Por lo tanto, resolver f(x) ≡ 0 (mod p ) para x genera una secuencia completa de números y para los cuales y = f ( x ), todos los cuales son divisibles por p . Se trata de encontrar una raíz cuadrada módulo primo, para lo cual existen algoritmos eficientes, como el algoritmo de Shanks-Tonelli . (De aquí es de donde el tamiz cuadrático recibe su nombre: y es un polinomio cuadrático en x , y el proceso de tamizado funciona como el tamiz 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 mod  p para obtener dos raíces α y β , y luego agregue una aproximación a log( p ) a cada entrada para la cual y ( x ) = 0 mod p ... es decir, A [ kp  +  α ] y A [ kp  +  β ]. También es necesario resolver la ecuación cuadrática módulo de potencias pequeñas de p para reconocer números divisibles por potencias pequeñas de un primo en base de factores.

Al final de la base del factor, 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 del factor. La información sobre exactamente qué primos dividen a y ( x ) se ha perdido, pero solo tiene factores pequeños, y existen muchos buenos algoritmos para factorizar un número que se sabe que solo tiene factores pequeños, como la división de prueba por números 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 final no tiene que ser completamente confiable; a menudo los procesos se comportan mal en, digamos, el 5% de los insumos, lo que requiere una pequeña cantidad de tamizado adicional.

Ejemplo de tamiz básico

Este ejemplo demostrará el tamiz cuadrático estándar sin optimizaciones logarítmicas ni potencias primas. Sea el número a factorizar N = 15347, por lo tanto el techo 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, sólo se necesitan cuatro números primos. Los primeros cuatro primos p para los cuales 15347 tiene un módulo de raíz cuadrada p son 2, 17, 23 y 29 (en otras palabras, 15347 es un módulo de residuo cuadrático de cada uno de estos primos). Estos primos serán la base para el tamizado.

Ahora construimos nuestro tamiz y comenzamos el proceso de tamizado para cada prima 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 el tamiz. 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. Dividiendo cada una de esas entradas entre 2 se obtiene

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

De manera similar, para los números primos restantes, se resuelve p en la ecuación . Tenga en cuenta que por 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 ser divisible por p en x = a y cada pésimo valor más allá de eso. 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 suaves 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 suave. Como , y es igual a uno, esto corresponde a: ${\displaystyle V_{0}}$ ${\displaystyle V_{3}}$ ${\displaystyle V_{71}}$

Procesamiento matricial

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

Escribir 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 viene dada por el espacio nulo izquierdo , simplemente

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

Por tanto, el producto de las tres ecuaciones produce un cuadrado (mod N).

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

y

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

Entonces 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, el otro es 149.

Esta demostración también debería servir para demostrar 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 de prueba o Pollard rho podrían haber encontrado un factor con mucho menos cálculo.

Múltiples polinomios

En la práctica, se utilizan muchos polinomios diferentes para y , ya que solo un polinomio normalmente no proporcionará suficientes pares ( x , y ) que sean suaves sobre la base del factor. Los polinomios utilizados deben tener una forma especial, ya que necesitan ser cuadrados módulo n . Todos los polinomios deben tener una forma similar a la original y ( x ) = x ² − n :

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

Suponiendo que es múltiplo de A, de modo que el polinomio y(x) pueda escribirse como . Si A es un cuadrado, entonces sólo hay que considerar el factor. ${\displaystyle B^{2}-n}$ ${\displaystyle B^{2}-n=AC}$ ${\displaystyle y(x)=A\cdot (Ax^{2}+2Bx+C)}$ ${\displaystyle (Ax^{2}+2Bx+C)}$

Este enfoque (llamado MPQS, Multiple Polynomial Quadratic Sieve) 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 terminar con sus polinomios.

primos grandes

Un primo grande

^{Si, después de} dividir por todos los factores menores que A , la parte restante del número (el cofactor) es menor que A2 , entonces este cofactor debe ser primo. De hecho, se puede agregar a la base de factores clasificando la lista de relaciones por cofactor. Si y(a) = 7*11*23*137 y 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.

Primos más grandes

Reducir aún más el umbral y utilizar un proceso efectivo para factorizar valores de y(x) en productos incluso de números primos relativamente grandes (ECM es excelente para esto) puede 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 números primos en una sola relación.

Parámetros de un ejemplo realista

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

• Límite de factorización de prueba: 27 bits
• Intervalo de tamiz (por polinomio): 393216 (12 bloques de tamaño 32768)
• Límite de suavidad: 1300967 (50294 números primos)
• Número de factores para los coeficientes del polinomio A : 10 (consulte Polinomios múltiples arriba)
• Límite primo grande: 128795733 (26 bits) (consulte Primos grandes arriba)
• Valores suaves encontrados: 25952 tamizando directamente, 24462 combinando números con números primos grandes
• Tamaño de matriz final: 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 factoraje

Hasta el descubrimiento del tamiz de campos numéricos (NFS), QS era el algoritmo de factorización de propósito general asintóticamente más rápido conocido. Ahora, la factorización de curva elíptica de Lenstra tiene el mismo tiempo de ejecución asintótica que QS (en el caso de que n tenga exactamente dos factores primos del mismo tamaño), pero en la práctica, QS es más rápido ya que utiliza operaciones de precisión simple en lugar de operaciones de precisión múltiple. operaciones utilizadas por el método de la curva elíptica.

El 2 de abril de 1994, se completó la factorización de RSA-129 utilizando QS. Se trataba de un número de 129 cifras, producto de dos números primos grandes, uno de 64 cifras y otro de 65 cifras. La base factorial para esta factorización contenía 524339 números primos. La fase de recopilación de datos tomó 5000 años MIPS y se realizó de forma distribuida a través de Internet. Los datos recopilados ascendieron a 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 mediante un algoritmo de propósito general, hasta que se utilizó NFS para factorizar RSA-130 , completado el 10 de abril de 1996. Todos los números RSA factorizados desde entonces se han factorizado utilizando NFS.

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

Implementaciones

• PPMPQS y PPSIQS
• mpqs
• SIMPQS Archivado el 6 de mayo de 2020 en Wayback Machine es una implementación rápida del tamiz cuadrático polinomial múltiple de autoinicialización escrito por William Hart. Proporciona soporte para la variante prima grande y utiliza la implementación de Lanczos en bloque de Jason Papadopoulos para la etapa de álgebra lineal. Se puede acceder a SIMPQS como el comando qsieve en el paquete de álgebra informática de SageMath , es parte de Fast Library for Number Theory 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 íntegramente en C.
• un subprograma de factorización de Dario Alpern, que utiliza el tamiz cuadrático si se cumplen ciertas condiciones.
• El paquete de álgebra informática PARI/GP incluye una implementación de la criba cuadrática polinómica múltiple autoiniciativa que implementa la variante prima grande. Fue adaptado por Thomas Papanikolaou y Xavier Roblot a partir de un tamiz escrito para el proyecto LiDIA. El esquema de autoinicialización se basa en una idea de la tesis de Thomas Sosnowski.
• Una variante de la criba cuadrática está disponible en el paquete de álgebra informática MAGMA . Se basa en una implementación de Arjen Lenstra de 1995, utilizada en su programa de "factoring por correo electrónico".
• msieve, una implementación de la criba cuadrática polinomial múltiple con soporte para números 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 factorizó 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 de bloque Lanczos 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 con fines didácticos.
• La biblioteca java-math 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 una implementación básica de QS. Publicado el 4 de febrero de 2016 por Ilya Gazman
• C Quadratic Sieve, un factorizador escrito íntegramente en C que contiene la implementación de Quadratic Sieve autoinicializante. El proyecto está inspirado en el factorizador FLINT de William Hart. La fuente publicada 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 del tamiz cuadrático polinómico múltiple para el lenguaje de programación R. Está escrito en C++ y es capaz de factorizar cómodamente semiprimos de 100 dígitos . Por ejemplo, un semiprime de 300 bits (91 dígitos) se tuvo en cuenta en 1 hora y el RSA-100 se tuvo en cuenta en menos de 10 horas en una MacBook Air con un procesador Apple M2.

Ver también

• Factorización de la 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). "Una historia de dos tamices" (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 ; Pomerancia, Carl (2001). "Sección 6.1: El método de factorización de tamiz cuadrático". Números primos: una perspectiva computacional (1ª ed.). Saltador. págs. 227–244. ISBN 0-387-94777-9.
• Wagstaff, Samuel S. Jr. (2013). El placer del factoraje . Providence, RI: Sociedad Estadounidense de Matemáticas . págs. 195-202. ISBN 978-1-4704-1048-3.
• Contini, Scott Patrick (1997). Factorización de números enteros con el tamiz cuadrático autoinicializante (PDF) (tesis de maestría). Universidad de Georgia. Archivado desde el original (PDF) el 5 de abril de 2015. Describe muchos detalles prácticos de implementación.

Otros enlaces externos

• Artículo de referencia "El algoritmo de factorización de tamiz cuadrático" de Eric Landquist