Certificado de Simplicidad

En matemáticas e informática , un certificado de primalidad es una prueba rigurosa de que un número es primo . Tener un certificado de primalidad te permite comprobar que un número es primo sin recurrir a pruebas de primalidad .

En la teoría de la complejidad computacional , por regla general, se entiende que el tamaño del certificado, así como el tiempo requerido para verificarlo, depende polinómicamente de la longitud de la entrada del número, es decir, del número de dígitos en eso.

La existencia de certificados de primalidad de polinomios muestra que problemas como la prueba de primalidad y la factorización de enteros pertenecen a la clase NP , ya que, según una de las definiciones equivalentes de esta clase, son problemas cuya solución se puede verificar en tiempo polinomial si se añade un se entrega certificado. Además, estos problemas se encuentran en la clase co-NP , que se deriva de su definición como una clase de complementos a los problemas de NP; de hecho, cualquiera de sus divisores no triviales puede ser un certificado polinomial de que un número es compuesto.

Por lo tanto, los certificados de primalidad fueron una de las primeras indicaciones de que la prueba de primalidad no era NP-completa , ya que si lo fuera, se seguiría que una clase NP está anidada en una co-NP, que a su vez suele ser[ aclarar ] considerado[ ¿por quién? ] es incorrecto. Además, el descubrimiento de los certificados polinómicos hizo que la prueba de primalidad fuera el primer problema que se sabe que pertenece tanto a NP como a co-NP, pero no se sabe que esté en la clase P. Con el advenimiento de la prueba Agrawal-Kayal-Saxena en 2002, el primer problema (y actualmente el único[ ¿cuándo? ] ) de la prueba de primalidad polinomial determinista, se encontró que el problema aún radica en P.

Certificado de Pratt

Históricamente, el concepto de certificados de primalidad se introdujo con el advenimiento del certificado Pratt , que fue obtenido en 1975 por Vaughan Pratt [1] , quien describió su estructura y demostró que el tamaño de un certificado depende polinomialmente de la longitud de un registro numérico. , y también que se puede verificar para un tiempo polinomial. El certificado se basa en la prueba de Lucas , que a su vez se deriva del pequeño teorema de Fermat :

(Teorema de Luc) Un número es primo si y solo si hay un elemento en el anillo de módulo de residuos tal que: $pags$ $pags$ $a\in \mathbb {Z} _{p}$

$a^{p-1}\equiv 1{\pmod {p))$ ,
$a^{\frac {p-1}{q}}\no \equiv 1{\pmod {p}}$ para todos los números primos que dividen . $q$ $p-1$

Prueba

Las condiciones escritas significan exactamente que el orden del elemento es . $a$ $p-1$

Si tal elemento existe, entonces al menos los elementos del anillo de residuos son módulos reversibles , es decir, coprimos con . Por lo tanto, todos los números son coprimos con , lo que implica la simplicidad de este número. $p-1$ $pags$ $pags$ ${\ estilo de visualización 1,2, \ puntos, p-1}$ $pags$
Si el número es primo, entonces hay una raíz primitiva en el anillo de módulo de residuos , cuyo orden debe ser igual a . ■ $pags$ $pags$ $p-1$

Al tener dicho número (llamado testigo de la simplicidad ) y dividirlo en factores primos, puede verificar rápidamente las condiciones anteriores: debe realizar exponenciaciones módulo, lo que se puede hacer para multiplicaciones usando exponenciación binaria . Las propias multiplicaciones en la implementación ingenua ("en una columna") se realizan en , lo que da una estimación general del tiempo de ejecución en . $a$ $p-1$ ${\ estilo de visualización O (\ log p)}$ ${\ estilo de visualización O (\ log p)}$ $O(\log ^{2}p)$ $O(\log ^{4}p)$

Al mismo tiempo, debe tenerse en cuenta que además de las condiciones anteriores, también es necesario verificar que los números presentados en el certificado como primos sean realmente tales, por lo tanto, además del testimonio de primalidad y división en factores primos, el certificado de primalidad de un número debe incluir también certificados de primalidad de todos los factores en él indicados. Así, conviene representar un certificado en forma de árbol, en cuyos nodos hay números primos y sus correspondientes testigos de primalidad, y los descendientes del nodo en el que está almacenado el número son divisores primos del número . En consecuencia, el número corresponde a las hojas del árbol . $p-1$ $pags$ $pags$ $p-1$ $pag=2$

Se puede demostrar por inducción que hay a lo sumo nodos internos en dicho árbol , es decir, aquellos que contienen un número primo impar. Considerando que cada nodo del árbol almacena un bit para escribir números en él, podemos concluir que el tamaño total del árbol no excede . El tiempo total de verificación, a su vez, se puede estimar en , ya que es necesario realizar acciones en cada uno de los nodos. ${\ estilo de visualización 4 \ log _ {2} p-4}$ ${\ estilo de visualización O (\ log p)}$ $O(\log ^{2}p)$ $O(\log ^{5}p)$ $O(\log ^{4}p)$ ${\ estilo de visualización O (\ log p)}$

Si bien los certificados de Pratt son útiles en teoría y fáciles de verificar, encontrar un certificado para un número requiere la factorización y otros números potencialmente grandes. Esto es fácil de hacer en algunos casos especiales, por ejemplo, para los números primos de Fermat , pero en el caso general, esta tarea ahora es mucho más difícil que la prueba habitual de la primacía de un número. $norte$ $n-1$

Influencia en "PRIMES está en P"

El artículo "PRIMES is in P" [2] fue un gran avance en la informática teórica . Este artículo, publicado por Manindra Agrawal y sus dos alumnos Niraj Kayal y Nitin Saxena en agosto de 2002, demuestra que el famoso problema de la primalidad se puede resolver de forma determinista en tiempo polinomial. Los autores recibieron el Premio Gödel , que es de $5,000 [3] , y el Premio Fulkerson 2006 por su trabajo.

Debido a que la prueba de primalidad ahora se puede realizar en tiempo polinomial usando la prueba AKS , un número primo puede verse como un certificado de su propia primalidad. Esta prueba se completa a tiempo , lo que hace que dicha verificación sea más costosa que usar el certificado de Pratt, pero no requiere encontrar el certificado en sí. ${\tilde {O}}(\log^{6}n)$

Notas

↑ Vaughan Pratt. "Cada primo tiene un certificado sucinto". Revista SIAM sobre Informática , vol. 4, págs. 214-220. 1975. Citas , texto completo .
↑ Agrawal, Manindra; Kayal, Neeraj; Saxena, Nitín PRIMES está en P (inglés) // Annals of Mathematics : journal. - 2004. - Septiembre ( vol. 160 , no. 2 ). - Pág. 781-793 . -doi :/ annals.2004.160.781 . — .
↑ Premio Gödel 2017 . Asociación Europea de Ciencias de la Computación Teórica . EATCS. Consultado: 29 de marzo de 2017. (indefinido)

Enlaces

Mathworld: Certificado de Primalidad
Certificado Mathworld Pratt
Mathworld: Certificado Atkin-Goldwasser-Kilian-Morain
Vasek Chavatal . Notas de clase sobre las pruebas de primalidad de Pratt . Departamento de Ciencias de la Computación. Universidad Rutgers. Versión PDF en la Universidad de Concordia .

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