P−1 Método de Pollard

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 4 de abril de 2019; las comprobaciones requieren 2 ediciones .

$p-1$ El método de Pollard es uno de los métodos de factorización de enteros .

Publicado por primera vez por el matemático británico John Pollard en 1974 [1] . Fue la aparición de este algoritmo lo que llevó [2] a un cambio en el concepto de número primo fuerte utilizado en criptografía , en términos generales, un número primo para el que tiene divisores suficientemente grandes. En los criptosistemas modernos , se intenta [2] utilizar números primos fuertes, ya que esto aumenta la seguridad de los algoritmos utilizados y de los sistemas en su conjunto. $p-1$

Definiciones y trasfondo matemático

Un número se llama - potencia - suave [3] si todos sus divisores primos, en las potencias en que están incluidos en la expansión de este número , satisfacen . Según el pequeño teorema de Fermat , para cualquier número primo y para cualquier número entero tal que y son coprimos , o, lo que es equivalente en este caso, no divide , tenemos: $B$ ${\ estilo de visualización pag^ {\ nu}}$ $p^{\nu }\leq B$ $pags$ $a$ $a$ $pags$ $pags$ $a$

a^{(p-1)}\equiv 1\mod p

, además .

\forall M=(p-1)l,l\in N\Rightarrow a^{M}\equiv 1\mod p

El algoritmo original (1974)

John Pollard publicó por primera vez el algoritmo que se describe a continuación en su artículo de 1974 "Teoremas de factorización y pruebas de primalidad" en las Actas de la Sociedad Filosófica de Cambridge [ 1] . El artículo está dedicado a la estimación teórica de la complejidad de factorizar un número grande o, en el caso de un número primo , a comprobar su simplicidad. El siguiente algoritmo fue una consecuencia e ilustración de los cálculos teóricos de Pollard. ${\ estilo de visualización N}$ ${\ estilo de visualización N}$

Primera etapa

La tarea es encontrar su propio divisor de un número distinto de uno. En primer lugar, debe elegir dos números tales que . $norte$ ${\ estilo de visualización B, M,}$ $1<B<M<{\sqrt {N)),M<B^{2}$
Calculemos ahora el número , donde todos los números primos son menores que . Aquí se permite cierta libertad en la elección de , pero se sabe a ciencia cierta que para pequeño , debe ser mayor que uno [1] . $M(B)=\prod_{k=1}^{m}p_{k}^{c_{k))$ $paquete}$ ${\ estilo de visualización B}$ $c_{k}$ $paquete}$ $c_{k}$
Elegimos un entero pequeño y calculamos $a>1$

b=a^{M(B)}\mod N

{\ estilo de visualización q = (b-1, N)}

si hemos encontrado el divisor , en caso contrario pasamos a la segunda etapa.

{\ estilo de visualización q \ neq 1}

norte

Segunda etapa

En este paso, es necesario calcular la secuencia

F_{m}\equiv b^{m-1}-1\mod N,

donde es un primo, esperando que en algún paso obtengamos

metro

{\ estilo de visualización B<m<M}

g_{m}=(F_{m},N)>1

La manera más fácil [1] de hacer esto es calcular para cada número impar multiplicando por , tomando intervalos regulares. Si se encuentra el divisor. Si , entonces es necesario estudiar esta área con mayor precisión. $b^m$ $metro$ $segundo^{2}$ $G_{i}=(b^{i},N)$ $1<G_{i}<N$ $G_{i}=N,G_{i-1}=1$

Nota

Con este método, solo podremos encontrar los divisores primos del número para los que [1] es verdadero : $pags$ $norte$

p-1=A

o , donde es -power-smooth y es primo tal que [1] .

p-1=Aq

A

B

q

{\ estilo de visualización B<q<M}

Versión moderna

Esta versión revisada del algoritmo en comparación con el original utiliza los conceptos de suavidad de ley de potencia y se centra en aplicaciones prácticas. La primera etapa sufrió cambios significativos, mientras que la segunda permaneció prácticamente sin cambios, nuevamente, desde un punto de vista teórico, no se agregó nada significativo en comparación con la versión anterior. Es el siguiente algoritmo al que se refiere cuando la gente habla del "método Pollard" [4] [5] .

Primera etapa

Sea potencia -suave, y se requiere encontrar el divisor del número . En primer lugar, se calcula el número donde el producto se realiza sobre todos los números primos en potencias máximas ${\ estilo de visualización N}$ $B$ $norte$ $M(B)=\prod_{i}p_{i}^{k_{i))$ $Pi}$ $k_{i}:p_{i}^{k_{i}}<B$
Entonces el divisor deseado [4] , donde . ${\ estilo de visualización q = (b-1, N)}$ $b=a^{M(B)}\mod N$

Hay dos casos posibles en los que el algoritmo anterior fallará [5] .

En el caso de que se pueda decir con certeza que y tiene un divisor que es potencia suave y una elección diferente debe resolver el problema . ${\ estilo de visualización (b-1, N) = N}$ $norte$ $B$ $a$
En un caso más frecuente, cuando vale la pena pasar a la segunda etapa del algoritmo, que aumenta significativamente la probabilidad de un resultado, aunque no lo garantiza. ${\ estilo de visualización (b-1, N) = 1}$

Ejemplo

Elijamos , luego , tomemos y calculemos ahora , y finalmente . ${\ estilo de visualización N = 10001}$ ${\ estilo de visualización B = 10}$ $M(B)=2^{3}\cdot 3^{2}\cdot 5\cdot 7=2520$ ${\ estilo de visualización a = 2}$ $b=a^{M(B)}\mod N=2^{2520}\mod 10001=3578$ ${\ estilo de visualización (b-1, N) = (3578-1,10001) = 73}$

Notas

Para números grandes , el número puede resultar muy grande, comparable en valor a , en tales casos puede ser recomendable factorizar aproximadamente el mismo valor y calcular la secuencia $B$ ${\ estilo de visualización M (B)}$ ${\ estilo de visualización B!}$ ${\ estilo de visualización M (B)}$ ${\displaystyle M(B)=\prod_{i}M_{i))$

a_{1}=a^{M_{1}}\mod N;

a_{k+1}=a_{k}^{M_{k+1}}\mod N

Segunda etapa

En primer lugar, debe fijar los límites , generalmente [5] [4] . $B_{1}=B,B_{2}\gg B$ $B_{2}\leq B^{2}$
La segunda etapa del algoritmo encuentra divisores , tales que , donde es una potencia suave y prima tal que . $norte$ $p-1=q\cdot A$ $A$ $B$ $q$ ${\displaystyle B_{1}<q<B_{2))$

Para lo que sigue, necesitaremos un vector de números primos de a , del cual es fácil obtener un vector de diferencias entre estos números primos , además , son números relativamente pequeños, y , donde es un conjunto finito [4] . Para acelerar la operación del algoritmo, es útil precalcular todo [4] y usar valores preestablecidos. $q_{yo}$ $B_1$ $B_{2}$ ${\displaystyle D=(D_{1},D_{2},...),D_{i}=q_{i+1}-q_{i))$ $D_{yo}$ $D_{i}\in \Delta$ $\Delta$ $b^{\delta _{i)),\forall \delta _{i}\in \Delta$
Ahora es necesario calcular secuencialmente , donde , calculado en la primera etapa, contando en cada paso . Tan pronto como , puede dejar de computar. $c_{0}=b_{1}\mod N,c_{i}=c_{i-1}^{\delta _{i))\mod N$ $b_{1}=a^{M(B_{1})}\mod N$ $G=(c_{i}-1,N)$ ${\ estilo de visualización G \ neq 1}$

Condiciones de convergencia

Deje que el divisor más pequeño , el máximo se tome entre todas las potencias que dividen [4] . $pags$ $norte$ $q^{t}=máx(q_{i}^{t_{i)))$ $q_{i}^{t_{i))$ $p-1$
- Si , entonces el divisor se encontrará en la primera etapa del algoritmo
[4] . $q^{t}<B_{1}$
De lo contrario, para el éxito del algoritmo, es necesario que , y todos los demás divisores de la forma sean menores que [4] . $q^{t}<B_{2}$ $p-1$ ${\ estilo de visualización q^{r}}$ $B_1$

Modificaciones y mejoras

Más tarde, el mismo Pollard expresó una opinión sobre la posibilidad de acelerar el algoritmo utilizando la transformada rápida de Fourier [4] en la segunda etapa, pero no dio formas reales de hacerlo [6] .
Incluso más tarde, en 1990, los matemáticos Peter Montgomery y Robert Silverman lo hicieron [6] . Los autores lograron lograr un aumento en la velocidad de ejecución de la segunda etapa del algoritmo.

Evaluación del desempeño

La complejidad de la primera etapa se estima como , dejando solo el término de mayor orden, obtenemos la estimación de la primera etapa del algoritmo [4] . $O(B\cdot \ln B\cdot (\ln N)^{2}+(\ln N)^{3})$ $O(B\cdot \ln B\cdot (\ln N)^{2})$
Según la estimación de Montgomery, la complejidad de la segunda etapa, hasta los términos del orden más alto, es [1] [4] , donde el número de primos es menor que . La estimación de Chebyshev da una igualdad aproximada . ${\ estilo de visualización O (\ pi (B_ {2}))}$ ${\ estilo de visualización \ pi (s)}$ $s$ ${\ estilo de visualización \ pi (s) \ aproximadamente {\ frac {s} {\ ln s}}}$

Registros

Por el momento (10/10/2016), los tres divisores primos más grandes encontrados por el método P-1 consisten en 66, 64 y 59 dígitos decimales [7] .

Número de dígitos	pags	divisor de números	Encontrado por quien	cuando se encuentra	B	B2
66	672038771836751227845696565342450315062141551559473564642434674541 = 2 2 3 5 7 17 23 31 163 401 617 4271 13681 22877 43397 203459 1396027 6995393 13456591 2110402817 + 1	${\ estilo de visualización 960 ^ {119} -1}$	T.Nogara	29/06/2006	$10^{8}$	$10^{{10}}$
64	1939611922516629203444058938928521328695726603873690611596368359 = 2 3 11 1187 9233729 13761367 43294577 51593573 100760321 379192511 2282985164293 + 1	$10^{243}-4\cdot 10^{121}-1$	M. Tervuren	13/09/2012	$10^{{9}}$	${\ estilo de visualización 10^{13}}$
59	12798830540286697738097001413455268308836003073182603569933 = 2 2 17 59 107 113 20414117 223034797 269477639 439758239 481458247 1015660517 + 1	${\ estilo de visualización 8069000260399979023963141 ^ {17} -1}$	A. Krupp	30/06/2011	$10^{9}$	$10^{{10}}$

Aplicaciones

GMP-ECM [8] - el paquete incluye la aplicación efectiva del método. $p-1$
Prime95 y MPrime, clientes oficiales de GIMPS , utilizan un método para descartar candidatos.

Véase también

Notas

↑ 1 2 3 4 5 6 7 Pollard, 1974 .
↑ 1 2 Karaarslan E. Técnicas de prueba de primalidad y la importancia de los números primos en los protocolos de seguridad // ICMCA'2000 : Actas del Tercer Simposio Internacional de Aplicaciones Matemáticas y Computacionales - Konya : 2000. - P. 280-287.
↑ Vasilenko, 2003 , pág. 60
↑ 1 2 3 4 5 6 7 8 9 10 11 Ishmukhametov, 2011 , pág. 53-55.
↑ 1 2 3 Cohen, 2000 , págs. 439.
↑ 1 2 Montgomery, Silverman, 1990 .
↑ Zimmermann, Paul . Registre los factores encontrados por el método p-1 de Pollard . Las páginas de personal de LORIA y del Centro Inria NGE. Consultado el 10 de octubre de 2016. Archivado desde el original el 11 de octubre de 2016.
↑ InriaForge: GMP-ECM (Método de curva elíptica): Inicio del proyecto . Consultado el 15 de noviembre de 2012. Archivado desde el original el 21 de julio de 2012. (indefinido)

Literatura

Pollard J. M. Teoremas sobre factorización y pruebas de primalidad (inglés) // Actas matemáticas de la Sociedad Filosófica de Cambridge / B. J. Green - Cambridge University Press , 1974. - Vol. 76, edición. 3.- Pág. 521-528. - 8p. — ISSN 0305-0041 ; 1469-8064 - doi:10.1017/S0305004100049252
Cohen A. A Course in Computational Algebraic Number Theory - 4th Print Edition - Berlin , Heidelberg , New York : Springer , 2000. - 550 p. - ( Textos de Posgrado en Matemáticas ) - ISBN 978-3-540-55640-4 - ISSN 0072-5285 ; 2197-5612
Vasilenko O. N. Algoritmos teóricos de números en criptografía - M. : MTsNMO , 2003. - 328 p. — ISBN 978-5-94057-103-2
Ishmukhametov Sh. T. Métodos de factorización para números naturales : libro de texto - Kazan : Universidad de Kazan , 2011. - P. 53-55. — 190 págs.
Montgomery P. , Silverman R. D. Una extensión FFT del algoritmo de factorización P-1 // Matemáticas . compensación -AMS , 1990. -Vol . 54, edición. 190. - Pág. 839-854. — ISSN 0025-5718 ; 1088-6842 - doi:10.1090/S0025-5718-1990-1011444-3