Criba racional

En matemáticas, la criba racional es un algoritmo general para la factorizar enteros en factores primos. Es esencialmente un caso especial de la criba general del cuerpo de números, y mientras que es mucho menos eficiente que el algoritmo general, es conceptualmente más simple. Así que, mientras es más bien un algoritmo de factorización sin utilidad en la práctica, es de utilidad como primer paso para aquellos que tratan de entender cómo funciona la criba general de cuerpo de números.

Método

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á.

Ejemplo

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.

Limitaciones del algoritmo

La criba racional, como la criba general del cuerpo de números, no puede factorizar números de la forma p^m, donde p es un primo y m es un entero. Esto no es un gran problema, dado que tales números son estadísticamente raros, y más aún, hay un proceso simple y rápido para verificar si un número dado es de esta forma. Probablemente el método más elegante es verificar si ${\displaystyle \lfloor n^{1/b}\rfloor ^{b}=n}$  se cumple para cualquier 1 < b < log(n) usando una versión entera del método de Newton para la extracción de raíces.^[2]​

El mayor problema es encontrar un número suficiente de z tales que para ambos, z y z+n, sean B-lisos. Para cualquier B dado, las proporción de números que son B-lisos decrece rápidamente con el tamaño del número. Así que si n es grande (digamos, un centenar de dígitos), será difícil o imposible encontrar los suficientes z para que el algoritmo funcione. La ventaja de la criba general del cuerpo de números es que se necesita únicamente buscar números lismo del orden de n^1/d para algún entero positivo d (típicamente 3 o 5), a diferencia del orden n que es requerido aquí.

Notas

1. Nótese que los factores comunes no pueden en general ser cancelado en una congruencia, pero pueden en este caso, dado que todos los primos del factor base requerido son coprimos con n, como se mencionó antes. Vea inverso multiplicativo (aritmética modular).
2. R. Crandall and J. Papadopoulos, On the implementation of AKS-class primality tests, disponible en [1]

Referencias

• A. K. Lenstra, H. W. Lenstra, Jr., M. S. Manasse, and J. M. Pollard, The Factorization of the Ninth Fermat Number, Math. Comp. 61 (1993), 319-349. A draft is available at .

• A. K. Lenstra, H. W. Lenstra, Jr. (eds.) The Development of the Number Field Sieve, Lecture Notes in Mathematics 1554, Springer-Verlag, New York, 1993.

•   Datos: Q4116848