Tamiz racional

Una criba racional es un algoritmo general para convertir enteros en factores primos . El algoritmo es un caso especial del método de tamiz de campo numérico general . Si bien es menos eficiente que el algoritmo general, es conceptualmente más simple. El algoritmo puede ayudar a comprender cómo funciona el método de tamiz de campo numérico general.

Método

Supongamos que estamos tratando de factorizar un número compuesto n . Definimos el límite de B y la base de factores (que denotaremos por P ), el conjunto de todos los números primos menores o iguales que B . Luego buscamos un entero positivo z tal que tanto z como z+n sean B -suaves , es decir , todos sus divisores primos están contenidos en P. Por lo tanto, podemos escribir para potencias adecuadas $Alaska}$

$z=\prod_{p_{i}\in P}p_{i}^{a_{i}}$ ,

y también para adecuado tenemos $b_{k}$

$z+n=\prod_{p_{i}\in P}p_{i}^{b_{i))$ .

Pero y son comparables en módulo , por lo que cualquier entero z que encontremos da un enlace de multiplicación de módulo (mod n ) entre todos los elementos de P , es decir $z$ ${\ estilo de visualización z+n}$ $norte$

\prod_{p_{i}\in P}p_{i}^{a_{i}}\equiv \prod_{p_{i}\in P}p_{i}^{b_{i} }\;\nombre del operador {(mod} \;n\nombre del operador {)}

(donde a i y b i son números enteros no negativos).

Cuando hemos generado suficientes de estas razones (por lo general lo suficiente como para que el número de tales razones sea ligeramente mayor que el tamaño de P ), podemos usar métodos de álgebra lineal para multiplicar estas diversas razones de tal manera que las potencias de todos los factores primos se conviertan en ser parejo. Esto nos dará una comparabilidad de cuadrados módulo de la forma a 2 ≡ b 2 (mod n ), que se puede convertir en una factorización del número n , n = mcd ( a - b , n ) × mcd ( a + b , n ). Tal descomposición puede ser trivial (es decir, n = n × 1), en cuyo caso se debe intentar nuevamente con una combinación diferente de razones. Si tenemos suerte, obtendremos un par no trivial de divisores de n y el algoritmo terminará.

Ejemplo

Factoricemos el número n = 187 usando un tamiz racional. Probemos con el número B =7, para el cual el conjunto P = {2,3,5,7} sirve como base de factores. El primer paso es comprobar si el número n es divisible por números del conjunto P. Está claro que en el caso de que n sea divisible por uno de estos números primos, hemos encontrado una solución. Sin embargo, 187 no es divisible por 2, 3, 5 o 7. En el siguiente paso, buscamos valores adecuados de z , 2, 5, 9 y 56 son números adecuados. Los cuatro valores de z dan el módulo de relaciones 187:

2 1 3 0 5 0 7 0 = 2 ≡ 189 = 2 0 3 3 5 0 7 1 .............(1)
2 0 3 0 5 1 7 0 = 5 ≡ 192 = 2 6 3 1 5 0 7 0 .............(2)
2 0 3 2 5 0 7 0 = 9 ≡ 196 = 2 2 3 0 5 0 7 2 .............(3)
2 3 3 0 5 0 7 1 = 56 ≡ 243 = 2 0 3 5 5 0 7 0 .............(4)

Ahora combinamos estas proporciones de varias maneras y terminamos con potencias iguales. Por ejemplo,

(1)×(4): Después de multiplicar estas razones y cancelar el factor común 7 (que podemos hacer ya que 7, siendo miembro de P , es coprimo de n [1] ). La comparación se simplifica a 2 4 ≡ 3 8 (mod n ), o 4 2 ≡ 81 2 (mod n ). Obtenemos la descomposición 187 = mcd(81-4.187) × mcd(81+4.187) = 11×17.

Alternativamente, la ecuación (3) ya tiene la forma deseada:

(3): Se lee 3 2 ≡ 14 2 (mod n ), lo que da la expansión 187 = mcd(14-3.187) × mcd(14+3.187) = 11×17.

Limitaciones del algoritmo

Una criba racional, como una criba general de un campo numérico, no puede obtener una descomposición de números de la forma p m , donde p es un número primo y m es un número entero. El problema no es demasiado grande: estadísticamente, tales números son raros y, además, existe un proceso simple y rápido para verificar que un número dado tenga esa forma. Aparentemente, el método más elegante es verificar si para 1 < b < log(n), usando la versión entera del método raíz de Newton [2] $\lpiso n^{1/b}\rpiso ^{b}=n$

El mayor problema es encontrar números z tales que tanto z como z + n sean B -suaves . Para cualquier B dado, la proporción de B -números uniformes disminuye rápidamente con el tamaño del número. Entonces, si n es grande (digamos cien dígitos), será difícil o casi imposible encontrar suficiente z para que el algoritmo funcione. La ventaja del algoritmo general de tamiz de campos numéricos es que uno tiene que encontrar números uniformes de orden n 1/ d para algún entero positivo d (generalmente 3 o 5), en lugar del orden n requerido por este algoritmo.

Notas

↑ Tenga en cuenta que los factores comunes en general no se pueden cancelar por comparación, pero en este caso se pueden cancelar porque todos los números primos en la base de factores son coprimos con n . Ver multiplicación inversa en aritmética modular
↑ R. Crandall, J. Papadopoulos, Sobre la implementación de las pruebas de primalidad de la clase AKS. Archivado el 5 de octubre de 2012 en Wayback Machine .

Literatura

AK Lenstra, HW Lenstra, Jr., MS Manasse, JM Pollard. La factorización del noveno número de Fermat // Math. compensación - 1993. - Edición. 61 . - S. 319-349 . . Una versión preliminar del artículo está disponible en
El desarrollo de la criba de campos numéricos / AK Lenstra, HW Lenstra. - Nueva York: Springer-Verlag, 1993. - T. 1554. - (Lecture Notes in Mathematics).

Algoritmos de teoría de números
Pruebas de simplicidad	Molinero Miller - Rabín Luca-Lemaire pepina Agrawala - Kayala - Sajonia Ruiseñor - Strassen
Encontrar números primos	Iterando sobre divisores Tamiz de Eratóstenes tamiz de atkin Tamiz Sundarama
Factorización	Iterando sobre divisores método Fermat p −1 Método de Pollard Algoritmo ρ de Pollard método Lehmann Método de la curva elíptica (algoritmo de Lenstra) algoritmo de dixon tamiz cuadrado
logaritmo discreto	Algoritmo de Gelfond-Shanks Algoritmo de Polig-Hellman Método ρ de Pollard Algoritmo del canguro de Pollard algoritmo de Adleman algoritmo COS
Encontrar MCD	Algoritmo de Euclides Algoritmo avanzado Algoritmo binario
Módulo aritmético	algoritmo de Montgomery Teorema del resto chino
Multiplicación y división de números.	Algoritmo Karatsuba Algoritmo de Toom-Cook Algoritmo de Schönhage-Strassen Algoritmo del Führer Algoritmo de Harvey-van der Hoeven Algoritmo de Burnickel-Ziegler
Calcular la raíz cuadrada	Algoritmo de Tonelli-Shanks Algoritmo de Berlekamp-Rabin