Prueba de simplicidad

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 21 de mayo de 2020; la verificación requiere 1 edición .

La cuestión de determinar si un número natural es primo se conoce como problema de primalidad. $norte$

Una prueba de primalidad (o prueba de primalidad) es un algoritmo que, habiendo tomado un número como entrada , permite no confirmar la suposición sobre la composición del número o afirmar con precisión su simplicidad. En el segundo caso, se denomina prueba de primalidad verdadera. Por lo tanto, la prueba de primalidad es solo una hipótesis de que si el algoritmo no confirma la suposición de que el número es compuesto , entonces este número puede ser primo con cierta probabilidad . Esta definición implica menos confianza en la conformidad del resultado de la prueba con el verdadero estado de cosas que una verdadera prueba de primalidad, que da un resultado verificado matemáticamente. $norte$ $norte$

Introducción

Los problemas de matemáticas discretas se encuentran entre los más complejos desde el punto de vista matemático . Uno de ellos es el problema de factorización , que consiste en encontrar la factorización de un número en factores primos. Para resolverlo, necesitas encontrar números primos, lo que lleva al problema de la simplicidad. El problema de prueba de primalidad pertenece a la clase de complejidad P , es decir, el tiempo de ejecución de los algoritmos para resolverlo depende polinómicamente del tamaño de los datos de entrada, lo cual se demostró en 2002 . Hay una declaración similar, pero no probada, para el problema de factorización .

Algunas aplicaciones de las matemáticas que utilizan la factorización requieren una serie de números primos muy grandes elegidos al azar. El algoritmo para su obtención, basado en el postulado de Bertrand :

Algoritmo:

Entrada : número natural $norte$
Solución (búsqueda de un número primo aleatorio P)
1. $P\obtiene$ La función de generar un número natural arbitrario en un segmento $[N,2N]$
2. Si es compuesto entonces $PAGS$
  1. $P\flecha izquierda\,P+1$
  2. si entonces $P=2N$
    1. $P\flecha izquierda\,N$
3. Devuelve " -primo aleatorio" $PAGS$

El tiempo para resolver el problema por este algoritmo no está definido, pero existe una alta probabilidad de que siempre sea polinomial, siempre que haya suficientes números primos y estén distribuidos más o menos uniformemente . Para números aleatorios simples, estas condiciones se cumplen.

Se sabe ( teorema de Euclides ) que el conjunto de primos es infinito. El teorema de Dirichlet ( 1837 ) dice que si mcd , entonces hay infinitos primos congruentes con módulo . En otras palabras, los números primos se distribuyen uniformemente en clases de residuos según la función de Euler [1] para cualquier valor de . Sin embargo, si los primos están distribuidos uniformemente, pero hay muy pocos, la búsqueda puede no ser posible en la práctica. Para resolver este segundo problema, utilizamos el Teorema de los Números Primos ( 1896 ), según el cual el número de primos en un intervalo aumenta a medida que . Este número tiende al infinito con bastante rapidez, de lo que podemos concluir que incluso para valores grandes existe una probabilidad bastante alta ( ) de encontrar un número primo al azar. De esto podemos concluir que el algoritmo descrito anteriormente puede dar la respuesta en tiempo polinomial si existe un algoritmo polinomial que nos permita verificar la simplicidad de un número arbitrariamente grande , lo que lleva al problema de la primalidad. $(a,n)=1$ $a$ $norte$ $modelo$ $\varfi (n)$ $norte$ $[2,n]$ $norte$ $n/registro(n)$ $norte$ $1/ln(n)$ $norte$

Información histórica

La primera mención de los números primos se conoce de Euclides ( siglo III a. C. ). Al mismo tiempo, el primer algoritmo para encontrar números primos fue inventado por Eratóstenes ( siglo II a. C. ) y ahora se conoce como el tamiz de Eratóstenes . Su esencia radica en la exclusión secuencial de la lista de enteros de a múltiplos de otros números primos ya encontrados por la "tamiz" [2] . Mucho más tarde, el matemático árabe Ibn al-Banna propuso enumerar números enteros no hasta , sino hasta , lo que permitió reducir el número de operaciones. La desventaja de este método es que en lugar de verificar la simplicidad de un número dado , ofrece una enumeración secuencial [3] de todos los números enteros hasta , y por lo tanto es ineficiente y requiere una potencia informática significativa . $una$ $norte$ $2,3,5$ $norte$ ${\ sqrt {n}}$ $norte$ ${\ sqrt {n}}$

A principios del siglo XIII, Leonardo de Pisa , conocido como Fibonacci, propuso una secuencia de números (que lleva su nombre), una de cuyas propiedades es que el -ésimo número de Fibonacci solo puede ser primo para números primos , excepto para . Esta propiedad se puede usar cuando se prueban números de Fibonacci para primalidad. También, independientemente de ibn al-Banna, propuso un método para verificar la simplicidad de los números mediante la enumeración. Este algoritmo es verdadero (o improbable) porque siempre se obtiene la respuesta, pero extremadamente ineficiente. $norte$ $F_{n}$ $norte$ $n=4$

El primero en utilizar relaciones entre números para definir la primalidad fue Pietro Antonio Cataldi en su trabajo sobre los números perfectos. Los números perfectos son aquellos que son iguales a la suma de sus propios divisores. Los primeros siete números perfectos son 6, 28, 496, 8128, 33550336, 8589869056 y 137438691328. Cataldi estableció que si un número es primo y el número también es primo, entonces el número es perfecto. $norte$ $2^{n}-1$ $2^{{n-1}}(2^{n}-1)$

En el siglo XVII, el matemático francés Marin Mersenne se dedicó al estudio de los números de la forma [4] , más tarde llamados números de Mersenne en su honor . Mersenne descubrió que de los primeros 257 números de Mersenne, solo 11 son primos (para n = 2, 3, 5, 7, 13, 17, 19, 31, 67, 127 y 257). Al hacerlo, cometió varios errores ( no es primo en p = 67 o 257, y lo es en p = 61, 89 y 107). La búsqueda de números primos entre los números de Mersenne es bastante sencilla gracias al test de Luc-Lehmer , que permite encontrar una solución con relativa rapidez. Es por eso que los números de Mersenne son los más grandes entre los números primos conocidos actualmente. En la correspondencia entre Mersenne y Fermat , se expresaron varias ideas más sobre los números primos [4] . $2^{n}-1$ $2^{n}-1$

Entonces, Fermat descubrió que si un número entero no es divisible por un número primo , entonces el número siempre es divisible por ( Pequeño Teorema de Fermat ). El teorema fue posteriormente generalizado por Euler . Varias pruebas de primalidad se basan en el pequeño teorema de Fermat. Fermat también sugirió que los números de la forma de todos los números naturales son primos . Este es de hecho el caso de . Euler encontró un contraejemplo a esta afirmación: . Para probar la primalidad de los números de Fermat, existe una prueba de Pepin eficiente . Hasta la fecha, no se han encontrado nuevos números primos de Fermat. $a$ $pags$ $a^{{p-1}}-1$ $pags$ ${\ estilo de visualización 2^{2^{k}}+1}$ $k$ ${\ estilo de visualización k = 0,1,2,3,4}$ $2^{2^{5}}+1=4294967297=641\cdot 6700417$

Entre otros científicos, Euler, Legendre , Gauss se ocuparon de la simplicidad de los números . El matemático francés Édouard Lucas obtuvo resultados significativos para resolver el problema de la primalidad en su trabajo sobre los números de Fermat y Mersenne. Es el criterio de la simplicidad de los números de Mersenne dado por él que ahora se conoce como la prueba de Lucas-Lehmer.

En 2002, se desarrolló una prueba de primalidad polinomial determinista, la prueba de Agrawal-Kayal-Saxena . Su aparición estaba prevista por la existencia de certificados de primalidad polinómica y, en consecuencia, por el hecho de que el problema de comprobar la primalidad de un número pertenecía a las clases NP y co-NP al mismo tiempo.

Pruebas de primalidad verdadera

Los algoritmos existentes para probar la primalidad de un número se pueden dividir en dos categorías: pruebas de primalidad verdadera y pruebas de primalidad probabilística. Las pruebas verdaderas como resultado de cálculos siempre dan el hecho de la simplicidad o composición de un número, una prueba probabilística da una respuesta sobre la composición de un número o su no composición con alguna probabilidad [2] [4] . En pocas palabras, el algoritmo probabilístico dice que lo más probable es que el número no sea compuesto, pero al final puede resultar ser primo o compuesto. Los números que satisfacen la prueba de primalidad probabilística, pero son compuestos, se denominan pseudoprimos [1] . Un ejemplo de tales números son los números de Carmichael [3] . También puede nombrar los números de Euler-Jacobi para la prueba de Solovay-Strassen y los pseudoprimos de Lucas. $\epsilon$

Un ejemplo de pruebas de primalidad verdadera es la prueba de Luc-Lehmer para los números de Mersenne . La desventaja obvia de esta prueba es que solo se aplica a cierto número de ciertos tipos de números. Otros ejemplos incluyen aquellos basados en el Pequeño Teorema de Fermat :

Prueba de Pepin para los números de Fermat .
Teorema de Proth para números de Proth .
Prueba de Agrawal-Kayala-Saxene , la primera prueba de primalidad polinomial.
Prueba de Luc-Lehmer-Riesel .

Tanto como:

método de iteración del divisor .
el teorema de Wilson .
El criterio de Pocklington .
Prueba de Miller .
Prueba de Adleman-Pomerans-Rumeli , mejorada [5] por Cohen y Lenstroy
Prueba de primalidad mediante curvas elípticas .

Pruebas probabilísticas de primalidad

Esta categoría incluye:

Pruebas de simplicidad en criptografía

Actualmente, los números primos son muy utilizados en el campo de la seguridad de la información. En primer lugar, esto se debe a la invención del método de cifrado de clave pública, que se utiliza en el cifrado de información y en los algoritmos de firma digital electrónica . Actualmente, según los estándares, el tamaño de los números primos utilizados en la formación de una firma digital mediante curvas elípticas es, de acuerdo con GOST R 34.10-2012, de al menos 254 bits. Para números tan grandes, la cuestión de determinar la primacía de un número es extremadamente difícil. Los métodos simples, como el método de enumeración, no son adecuados para su uso debido al hecho de que requieren una cantidad extremadamente grande de recursos computacionales y una gran cantidad de tiempo [6] .

Además, la determinación de la primacía de un número es necesaria cuando se descifra información cifrada o firmada mediante el algoritmo RSA . Para abrir un mensaje de este tipo, es necesario poder descomponer un número en dos factores primos, lo cual no es una tarea trivial para números grandes.

Por otra parte, a la hora de generar claves para criptosistemas de clave pública , esquemas de firma electrónica, etc., se utilizan grandes números primos pseudoaleatorios. Por ejemplo, cuando se usa el protocolo Diffie-Hellman, es necesario tener un número primo que especifique el campo final . Por lo tanto, el uso de una prueba de primalidad eficiente permite aumentar la confiabilidad de los algoritmos para generar tales claves.

Véase también

Notas

↑ 1 2 Kormen T., Leiser C. Algorithms. Construcción y análisis. - M. : MTSNMO, 2002. - S. 765-772.
↑ 1 2 Vasilenko O. N. Algoritmos teóricos de números en criptografía. - M. : MTSNMO, 2003. - 328 p.
↑ 1 2 Crandall R., Pomerance C. Números primos: una perspectiva computacional. — Springer, 2005.
↑ 1 2 3 Donald Knuth . El Arte de Programar, Volumen 2. Algoritmos Derivados. - M. : "Williams" , 2007.
↑ Nesterenko Yu. V. Introducción a la criptografía. - Pedro, 2001. - 288 p.
↑ B. Schneier. Criptografía aplicada. - S. 296-300.

Literatura

Vasilenko O. N. Capítulo 1. Prueba de primalidad de números y construcción de números primos grandes // Algoritmos teóricos de números en criptografía . - M. : MTSNMO, 2003. - S. 12-56. — 328 pág. — ISBN 5-94057-103-4 . Archivado el 27 de enero de 2007 en Wayback Machine .
Nesterenko Yu. V. Capítulo 4.6. Cómo verificar la simplicidad de un número grande // Introducción a la criptografía / Ed. V. V. Yashchenko. - Pedro, 2001. - 288 p. - ISBN 5-318-00443-1 . Archivado el 25 de febrero de 2008 en Wayback Machine .
Schneier B. Parte 3. Algoritmos criptográficos. Capítulo 11 11.5. Generación de números primos // Criptografía aplicada. Protocolos, algoritmos, código fuente en lenguaje C = Criptografía Aplicada. Protocolos, Algoritmos y Código Fuente en C. - M. : Triumph, 2002. - S. 296-300. — 816 pág. - 3000 copias. - ISBN 5-89392-055-4 .
Kormen T., Leiser C. Capítulo 33.8. Comprobación de números por simplicidad // Algoritmos. Construcción y Análisis . - M. : MTSNMO, 2002. - S. 765-772. - ISBN 5-900916-37-5 .
Crandall R., Pomerance C. Capítulo 3. Reconocimiento de números primos y compuestos. Capítulo 4. "Demostración de primalidad" // Números primos: una perspectiva computacional . - Springer, 2005. - S. 117-224. — ISBN 0-387-25282-7 .
Donald Knuth . Capítulo 4.5.4. Factorización prima // El arte de la programación, volumen 2. Los algoritmos resultantes = El arte de la programación informática, vol. 2. Algoritmos Semiméricos. - 3ra ed. - M .: "Williams" , 2007. - S. 832. - ISBN 0-201-89684-2 .

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

Algoritmos de teoría de números
Pruebas de simplicidad	prueba AKC prueba de abril Fuente de alimentación Bailey Curva elíptica criterio de pocklington Prueba de granja prueba de lucas Prueba de Luc-Lehmer Prueba de Luc-Lehmer-Riesel teorema de prot prueba de pepina Prueba cuadrática de Frobenius Prueba Nightingale-Strassen Prueba de Miller-Rabin
generación de números primos	tamiz de atkin Tamiz de Eratóstenes Tamiz Sundarama Rueda de decadencia
Factorización de números enteros	método de fracción continua algoritmo de dixon Método de la curva elíptica método de Euler Algoritmo ρ de Pollard p −1 Método de Pollard p +1-Método de Williams tamiz cuadrado Método de tamiz de campo numérico general Método de tamiz de campo numérico especial tamiz racional método Fermat Formas de vástagos cuadráticos Iterando sobre divisores Algoritmo de Shor
Multiplicación	Antiguo Egipto Multiplicación por una columna Karatsuba Algoritmo de Toom-Cook Schönhage - Strassen Führer
logaritmo discreto	Algoritmo de Gelfond-Shanks algoritmo ρ "Canguro" Políga - Hellman orden de calculo Tamiz de campo funcional
Máximo común divisor	Algoritmo binario Algoritmo de Euclides Algoritmo de Euclides extendido Algoritmo GCD de Lemaire
Raíz cuadrada modular	Algoritmo de Cipolla Algoritmo de Pocklington Algoritmo de Gelfond-Shanks
Otros algoritmos	método Chakrawala Algoritmo de Kornakkiya LLL raíz cuadrada entera Módulo de exponenciación algoritmo de Shuf
La fuente en cursiva significa que el algoritmo está diseñado para números de un tipo especial