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 ,
y del mismo modo, para el adecuado , tenemos
- .
Pero y son congruentes módulo , 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.
(donde los ai y bi 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 a2≡b2 (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):
- 21305070 = 2 ≡ 189 = 20335071.............(1)
- 20305170 = 5 ≡ 192 = 26315070.............(2)
- 20325070 = 9 ≡ 196 = 22305072.............(3)
- 23305071 = 56 ≡ 243 = 20355070.............(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 24 ≡ 38, o 42 ≡ 812. 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 32 ≡ 142 (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 pm, 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 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 n1/d para algún entero positivo d (típicamente 3 o 5), a diferencia del orden n que es requerido aquí.
Notas
- ↑ 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).
- ↑ 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 www.std.org/~msm/common/f9paper.ps.
- 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