¿Cómo explicarías un algoritmo de tamiz cuadrático a un estudiante de secundaria?

Answer 1

Antes de pasar al algoritmo de tamiz cuadrático, es útil comprender lo que se llama “método de factorización de Fermat”:
Si un entero impar n es compuesto, digamos n = pq, entonces ambos p, q son impares; entonces las ecuaciones p = x + y; q = xy dará soluciones enteras x = (p + q) / 2 e y = (pq) / 2. (Básicamente, x es el promedio de p, q e y es su distancia de ese promedio)
Por lo tanto, n = pq se puede escribir como n = (x + y) (xy) = x ^ 2-y ^ 2.
Si podemos encontrar algunos enteros x, y que satisfagan esta ecuación, entonces conducirá a la factorización n = pq. Este es el método de Fermat; y desafortunadamente requiere una gran cantidad de pruebas para x, para obtener o refutar la existencia de una factorización.

En el corazón del algoritmo de tamiz cuadrático, está realmente este método de Fermat, pero hace varias adiciones y extensiones inteligentes al algoritmo, para reducir considerablemente el esfuerzo computacional. Antes de describir el algoritmo, aquí hay algunas observaciones que utiliza el algoritmo:
1. En lugar de n = x ^ 2 – y ^ 2, consideramos una ecuación ligeramente general n | x ^ 2 – y ^ 2 (es decir, x ^ 2, y ^ 2 dejan el mismo resto al dividir por n); También conducirá a una factorización. Entonces, estamos buscando una x tal que el resto de x ^ 2 al dividir entre n, sea un cuadrado perfecto.
2. Para que un resto sea un cuadrado perfecto, todos los exponentes primos en su factorización deben ser pares. Entonces, por ejemplo, 12 = 2 ^ 2 x 3 ^ 1 puede representarse por el “vector exponente” (0,1) que indica que el primer exponente es par, el segundo es impar. (Aquí reduciremos todos los vectores a solo 0 y 1, para indicar la paridad, es decir, la naturaleza par o impar; no nos importa el valor real de los exponentes)
2. Incluso si dos o más cuadrados dejan residuos no cuadrados, puede valer la pena verificar si su producto tiene un residuo cuadrado; y para esto necesitamos multiplicar los restos. Sin embargo, multiplicar números es equivalente a sumar sus exponentes primos; así, por ejemplo, si r = 12, s = 6 yt = 2, entonces pueden representarse por los vectores exponentes (0,1), (1,1) y (1,0) respectivamente; entonces el producto primero puede ser representado por (0,1) + (1,1) + (1,0) = (0,0), lo que indica que todas las potencias primas son pares, por lo que tenemos un cuadrado perfecto.

Bueno … eso es todo. El algoritmo de tamiz cuadrático reúne todas estas observaciones en este algoritmo ordenado:
1. Elija un cierto número máximo M, lo que indica que estamos interesados ​​en los residuos que se pueden factorizar utilizando solo los primeros números primos M, por lo tanto, los vectores exponentes de tipo 1-0 tendrán M entradas cada uno.
2. Siga probando aleatoriamente varios números a_i, de modo que el resto de a_i ^ 2 al dividir entre n, pueda factorizarse en los primeros M primos. Por lo tanto, obtenemos un gran grupo de vectores exponentes.
3. Ahora intente encontrar un subconjunto de todos estos a_i ‘s, de modo que la suma de sus vectores exponentes sea el vector cero (0,0, .., 0). lo que indicaría que el cuadrado del producto del a_i correspondiente tiene un resto cuadrado perfecto; y ahora podemos usar la representación de tipo x ^ 2-y ^ 2 para calcular una factorización de n.