En teoría de números , la conjetura de Agrawal , debida a Manindra Agrawal en 2002, [1] forma la base para la prueba ciclotómica AKS . La conjetura de Agrawal establece formalmente:
Dejar y ser dos enteros positivos coprimos . Si
entonces tambien es primo o
Ramificaciones
Si la conjetura de Agrawal fuera cierta, disminuiría la complejidad del tiempo de ejecución de la prueba de primalidad AKS de a .
Verdad o falsedad
La conjetura fue formulada por Rajat Bhattacharjee y Prashant Pandey en su tesis de 2001. [2] Se ha verificado computacionalmente para y , [3] y para. [4]
Sin embargo, un argumento heurístico de Carl Pomerance y Hendrik W. Lenstra sugiere que hay infinitos contraejemplos. [5] En particular, la heurística muestra que tales contraejemplos tienen una densidad asintótica mayor que para cualquier .
Suponiendo que la conjetura de Agrawal es falsa por el argumento anterior, Roman B. Popovych conjetura que una versión modificada aún puede ser cierta:
Dejar y ser dos enteros positivos coprimos. Si
y
entonces tambien es primo o . [6]
Computación distribuída
Tanto la conjetura de Agrawal como la de Popovych están siendo probadas por el proyecto de computación distribuida Primaboinca, que se inició en 2010 con base en BOINC . En junio de 2017, el proyecto no encontró contraejemplos de.
Notas
- ^ Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitin (2004). "PRIMES está en P" (PDF) . Annals of Mathematics . 160 (2): 781–793. doi : 10.4007 / annals.2004.160.781 . JSTOR 3597229 .
- ^ Rajat Bhattacharjee, Prashant Pandey (abril de 2001). "Prueba de primordialidad" . Informe técnico . IIT Kanpur .
- ^ Neeraj Kayal, Nitin Saxena (2002). "Hacia una prueba de primalidad determinista polinomial-tiempo". Informe técnico . IIT Kanpur. CiteSeerX 10.1.1.16.9281 .
- ^ Saxena, Nitin (diciembre de 2014). "Primalidad y generación de números primos" (PDF) . UPMC París. Archivado desde el original (PDF) el 25 de abril de 2018 . Consultado el 24 de abril de 2018 .
- ^ Lenstra, HW; Pomerance, Carl (2003). "Comentarios sobre la conjetura de Agrawal" (PDF) . Instituto Americano de Matemáticas . Consultado el 16 de octubre de 2013 .
- ^ Popovych, Roman (30 de diciembre de 2008), A note on Agrawal conjeture (PDF) , consultado el 21 de abril de 2018