Test de primalidad

El 39º número primo de Mersenne era el mayor conocido hasta la fecha de creación de este artículo.

La cuestión de la determinación de si un número n dado es primo es conocida como el problema de la primalidad. Un test de primalidad (o chequeo de primalidad) es un algoritmo que, dado un número de entrada n, no consigue verificar la hipótesis de un teorema cuya conclusión es que n es compuesto.

Esto es, un test de primalidad sólo conjetura que “ante la falta de certificación sobre la hipótesis de que n es compuesto podemos tener cierta confianza en que se trata de un número primo”. Esta definición supone un grado menor de confianza que lo que se denomina prueba de primalidad (o test verdadero de primalidad), que ofrece una seguridad matemática al respecto.

Introducción

Los problemas que implican a las matemáticas discretas están entre los más difíciles de las matemáticas. Concretamente el de la factorización es un problema para el que todavía no se ha encontrado una solución que se pueda acotar en tiempo polinomial.[1]

Por otra parte, algunas aplicaciones de las matemáticas que utilizan el problema de la factorización precisan de una serie de números primos muy grandes escogidos de forma aleatoria. El algoritmo para obtener un número primo aleatorio muy grande sería algo así:

Algoritmo Obtención de un número primo aleatorio

/*Basado en el postulado de Bertrand*/

Entrada: Un número natural n.

Salida : P (el número primo aleatorio buscado).

  1. Función Genera_numero_aleatorio_en_intervalo
  2. Mientras no sea un número primo haga lo siguiente:
    1. Si entonces:
  3. Retorne

El tiempo de finalización de este algoritmo no es determinado, pero existe una alta probabilidad de que finalice en tiempo polinomial siempre y cuando haya suficientes números primos y estos estén distribuidos de forma más o menos uniforme. Afortunadamente para las aplicaciones que precisan números primos aleatorios, esto es así. Veamos por qué.

Lo primero que podemos establecer es que el cardinal del conjunto de primos en el conjunto de los números naturales es infinito (esto es, que hay infinitos números primos). El teorema de Dirichlet ( 1837) dice que si mcd(a, n) = 1 entonces hay infinitos primos congruentes con a módulo n. En otras palabras (y utilizando un corolario de Dirichlet), los números primos están uniformemente distribuidos en las clases congruentes con la función φ de Euler en para cualquier valor de n.

Claro que, si los números primos están uniformemente distribuidos, pero hay un número pequeño de ellos, la búsqueda podría ser imposible en la práctica. Para resolver este segundo problema podemos acudir al teorema de Hadamard ( 1896) que establece que la cardinalidad del conjunto de números primos en el intervalo [2..n] es asintótico a . Este número tiende a infinito muy suavemente, lo que implica que aún para valores grandes de n existe una probabilidad suficientemente alta de dar con un número primo de forma aleatoria.

De lo visto hasta aquí podemos concluir que el algoritmo anterior puede obtener una respuesta en tiempo polinomial si existe un algoritmo polinomial para comprobar que un número n arbitrariamente grande es primo. Lo que nos devuelve al problema de la primalidad.

En cualquier caso una modificación muy frecuente para hacer el algoritmo determinista es partir de una semilla aleatoria y luego hacer una búsqueda secuencial de la cota inferior del conjunto de primos mayores que la semilla de partida.

Other Languages
Deutsch: Primzahltest
Esperanto: Primeca provo
magyar: Prímteszt
日本語: 素数判定
Nederlands: Priemgetaltest
norsk bokmål: Primtallstest
Simple English: Primality test
svenska: Primtalstest
українська: Тест простоти
中文: 素性测试