La hipótesis de Agrawal

La hipótesis de Agrawal , propuesta por Manindra Agrawal en 2002 [1] , constituye la base de la prueba Agrawal-Kayala-Saxena . La hipótesis de Agrawal establece:

Sean y dos enteros positivos coprimos. si un $norte$ $r$

(X-1)^{n}\equiv X^{n}-1{\pmod {n,X^{r}-1}}\,

entonces o es simple o . $norte$ $n^{2}\equiv 1{\pmod {r))$

Consecuencias

Si la conjetura de Agrawal es correcta, esto reducirá la complejidad computacional de la prueba Agrawal-Kayal-Saxena de a . ${\tilde {O}}(\log^{6}n)$ ${\tilde {O}}(\log^{3}n)$

Hipótesis verdadera o falsa

La hipótesis de Agrawal fue probada por computadora para y . Sin embargo, el argumento heurístico de Carl Pomerans y Hendrik Lenstra sugiere que existen infinitos contraejemplos [2] . En particular, los argumentos heurísticos muestran que tales contraejemplos tienen una densidad asintótica que es grande para cualquier . ${\ estilo de visualización r <100}$ ${\ estilo de visualización n<10^{10}}$ ${\ Displaystyle {\ tfrac {1} {n ^ {\ varepsilon}}}}$ $\varepsilon >0$

Si la conjetura de Agrawal no es cierta de acuerdo con los argumentos anteriores, una versión modificada de la conjetura de Popovich aún puede ser cierta:

Sean y dos enteros positivos coprimos. si un $norte$ $r$

(X-1)^{n}\equiv X^{n}-1{\pmod {n,X^{r}-1))

(X+2)^{n}\equiv X^{n}+2{\pmod {n,X^{r}-1))

entonces primo o [3] . $norte$ $n^{2}\equiv 1{\pmod {r))$

Notas

↑ Agrawal, Kayal, Saxena, 2004 , pág. 781–793.
↑ Lenstra, Pomerance, 2013 .
↑ Popovych, Roman, Una nota sobre la conjetura de Agrawal , < http://eprint.iacr.org/2009/008.pdf > Archivado el 15 de octubre de 2018 en Wayback Machine .

Literatura

Manindra Agrawal, Neeraj Kayal, Nitin Saxena. PRIMOS está en P . - 2004. - T. 160 , núm. 2 . — S. 781–793 . -doi : 10.4007 / annals.2004.160.781 . — .
Lenstra HW, Carl Pomerance. Comentarios sobre la conjetura de Agrawal. . — Instituto Americano de Matemáticas, 2013.