Criba racional

Suponga que intenta factorizar el número compuesto n. Se puede elegir una acotación B, e identificar el factor base (que se llamará P), al conjunto de todos los primos menores o iguales a B. A continuación, se buscan los enteros positivos z tales que tanto z y z + n sean B-liso — i.e. todos sus factores primos están en P. Por tanto, podemos escribir, para los exponentes adecuados ${\displaystyle a_{k}}$,

${\displaystyle z=\prod _{p_{i}\in P}p_{i}^{a_{i}}}$

y del mismo modo, para el adecuado ${\displaystyle b_{k}}$, tenemos

${\displaystyle z+n=\prod _{p_{i}\in P}p_{i}^{b_{i}}}$.

Pero ${\displaystyle z}$ y ${\displaystyle z+n}$ son congruentes módulo ${\displaystyle n}$, y por lo que cada número entero tal z que encontramos con dé una relación multiplicativa (mod n) entre los elementos de P, i.e.

${\displaystyle \prod _{p_{i}\in P}p_{i}^{a_{i}}\equiv \prod _{p_{i}\in P}p_{i}^{b_{i}}\;\operatorname {(mod} \;n\operatorname {)} }$

(donde los a_i y b_i son enteros no negativos.)

Cuando se hayan generado las suficientes de estas relaciones (por lo general es suficiente con que el número de relaciones sea un poco más que el tamaño de P), podemos utilizar los métodos del álgebra lineal para multiplicarlos junto a estas varias relaciones de manera que los exponentes de los números primos sean todos pares. Entonces se obtendrá una congruencia de cuadrados de la forma a²≡b² (mod n), que puede convertirse en una factorización de n, n = mcd(a-b,n)×mcd(a+b,n). Esta factorización podría llegar a ser trivial (i.e. n=n×1), en cuyo caso tenemos que intentarlo de nuevo con una combinación diferente de las relaciones; pero con suerte tendremos un par no trivial de los factores de n, y el algoritmo terminará.

Factorizaremos el entero n = 187 usando la criba racional. Tomaremos arbitrariamente el valor B=7, obteniendo el factor base P = {2,3,5,7}. El primer paso es comprobar la divisibilidad de cada uno de los miembros de P en n; claramente si n es divisible por uno de esos primos, entonces habremos finalizado ya. Sin embargo, 187 no es divisible por 2, 3, 5, o 7. Seguidamente, buscamos los valores adecuados de z; los primeros son 2, 5, 9, y 56. Los cuatro valores adecuados de z dan cuatro relaciones multiplicativas (mod 187):

• 2¹3⁰5⁰7⁰ = 2 ≡ 189 = 2⁰3³5⁰7¹.............(1)

• 2⁰3⁰5¹7⁰ = 5 ≡ 192 = 2⁶3¹5⁰7⁰.............(2)

• 2⁰3²5⁰7⁰ = 9 ≡ 196 = 2²3⁰5⁰7².............(3)

• 2³3⁰5⁰7¹ = 56 ≡ 243 = 2⁰3⁵5⁰7⁰.............(4)

Ahora hay esencialmente varias maneras diferentes de combinar estos y acabar con exponentes pares. Por ejemplo,

• (1)×(4): Después de multiplicarlos y, anulando el factor común de 7 (lo cual podemos hacer puesto que 7 se considera un miembro de P, y se ha determinado que estos son coprimos con n^[1]), esto se reduce a 2⁴ ≡ 3⁸, o 4² ≡ 81². La factorización resultante es 187 = mcd(81-4,187) × mcd(81+4,187) = 11×17.

Alternativamente, la ecuación (3) está en la forma adecuada ya:

• (3): Esto dice que 3² ≡ 14² (mod n), que proporciona la factorización 187 = mcd(14-3,187) × mcd(14+3,187) = 11×17.