Fundamentos del algoritmo Quadratic Sieve

Question

Estoy tratando de entender el algoritmo Quadratic Sieve para la factorización de enteros, sigo la descripción en el libro "Prime Numbers" de Crandall y Pomerance, específicamente el Algoritmo 6.1.1. (Aunque la pregunta de abajo se aplica a cualquier descripción de QS, por lo que puedo ver).

Por favor, tengo algunas preguntas muy básicas sobre el método:

• en la fase de inicialización se encuentran las raíces cuadradas ( $a_i$ ) en el número que se factoriza ( $N$ ) módulo de algún primo ( $p_i$ ). Pero en la descripción no se vuelven a mencionar las raíces, ¿para qué sirven?

• fase de tamizado, esto es posiblemente sólo yo no entender el texto completamente, que debería "tamizar para $B$ -valores suaves". Creo que se puede leer en la palabra "suave" que tengo que probar todos los primos hasta el límite, pero creo que lo que se quiere decir aquí es que sólo debo probar los primos que tienen símbolo de Legendre igual a uno, de la fase anterior. (He probado ambos y no había ninguna diferencia )

• por qué tengo que tener $(K+1) \times K$ en el paso de álgebra lineal ( $K$ es el número de primos encontrados durante la inicialización)? Es decir, si tengo suerte podría acabar teniendo sólo tres vectores de exponentes que sumen cero vector así que asumo que es porque el algoritmo utiliza el método de álgebra lineal para encontrar el subconjunto correcto, ¿correcto?

• en el último paso, ¿qué hacer si el GCD no revela un factor no trivial? ¿Calcular simplemente más vectores de exponentes para el paso de álgebra lineal? ¿Quitar algunos de los ya calculados?

Answer 1

$(1)$ El propósito de las raíces es acelerar la búsqueda de números $x$ con la propiedad de que $\ \ x^2\mod N\ \ $ tiene factores pequeños. El algoritmo también funcionaría para números aleatorios, pero los residuos cuadráticos suponen una mejora significativa en cuanto a velocidad.

$(2)$ Un número es $B$ -suave , si no tiene ningún factor primo mayor que $B$ . El objetivo de la criba de campos numéricos es encontrar suficientes congruencias $x^2\equiv y\mod N$ con $B$ -suave $y$

$(3)$ De hecho, podríamos tener un vector cero con menos de $K$ filas, pero la probabilidad no será muy grande, si la matriz es grande. Además, podemos necesitar muchas congruencias de la forma $\ \ x^2\equiv y^2\mod N\ \ $ . En teoría, existe la posibilidad de $\frac{1}{2}$ que tal congruencia da un factor no trivial, pero las congruencias construidas no son aleatorias.

$(4)$ Es como tú dices. De hecho, a veces , no se encuentra ningún factor, se borran algunas congruencias y se calculan nuevas congruencias. Sin embargo, no conozco los detalles.

Answer 2

En cuanto a la 1:

El problema es que se quiere tamizar la presencia de factores primos en x * x mod N, con ceil(sqrt( N )) <= x < ceil(sqrt( 2 * N )) y, por lo tanto, x * x mod N = x * x - N, sin calcular realmente el caro x * x o x * x mod N. El a_i permite esto.

Se buscan los p en 2 < p <= B para que [ a * a = N ] mod p contenga 2 soluciones a_1 y a_2. El número de soluciones de [ a * a = N ] mod p puede ser cero, uno o dos. Si hay una solución, entonces p | N, por lo que esto no suele ocurrir. Los casos de cero y dos soluciones ocurren - aparentemente - con casi la misma probabilidad.

Las x se tamizan en base a [ x = a_i ] mod p, por lo que se aumentan s y t en x = a_1 + s * p y x = a_2 + t * p.

Para tal x, se cumple que [ x * x mod N ] mod p = [ a_i * a_i + 2 * p * a_i + p * p - N ] mod p = [ a_i * a_i - N ] mod p = 0.

A la inversa, cualquier x puede escribirse como x = q * p + r. ¿Qué nos dice [ x * x mod N ] mod p = 0 sobre r?

Se cumple que 0 = [ x * x mod N ] mod p = [ x * x - N ] mod p = [ q * q * p * p + 2 * p * q * r + r * r - N ] mod p = [ r * r - N ] mod p.