Test de Primalidad II Primeros métodos

Hay algunas situaciones en las que es necesario conocer si un número entero grande es primo, por ejemplo en la aplicación de la clave pública del sistema de encriptación RSA y en otros sistemas de encriptación en los que es necesario generar de forma aleatoria números primos grandes.

Para las situaciones descritas, el problema consiste en verificar que los números enteros aleatorios generados son primos, por lo tanto es necesario recurrir a los test de primalidad para verificar dicha situación.

Un test de primalidad es un criterio, para determinar si un número n, es primo o no, es decir se puede descomponer en otros o no.

Si n pasa el test de primalidad, entonces “puede” ser primo, en caso de que no lo pase, entendemos que es un número compuesto.

Hay un problema aún mayor, que aplicar el test de primalidad a un entero grande,  consiste en encontrar los factores primos de n, computacionalmente es más costoso este problema en el caso de que en número no supere el test de primalidad.

La seguridad del sistema de encriptación RSA, está basado en la asunción de que, es más fácil encontrar dos números primos p y q, tal que n = p x q, que buscar los dos factores de n.

Sea n un número entero grande, y supongamos que queremos determinar, si este número es primo o no.
El más simple de los test de primalidad es el de la prueba de la división, consiste en que tenemos un entero impar m y vemos si divide o no a n, si n ≠ 1, n  y m|n, entonces n es compuesto, en otro caso n pasa el test de primalidad, de la prueba de la división por m, el siguiente paso es seleccionar más u más pruebas de división , sabemos que n es primo cuando m alcanza a √n, este método consume mucho tiempo probar que  n es o no primo, hay otros métodos mucho más rápidos.

El test de Fermat, se muestra más eficiente, este método está basado en el Pequeño Teorema de Fermat, que dice que si n es primo entonces para algún b tal que m. c. d (b,n) = 1, tenemos:

b^n-1 ≡ 1 mod n.

Si n no es primo, es posible, pero poco probable que la expresión se sostenga, es decir que puede dar falsos positivos de primalidad.

Entonces a menos que n pase el test de Fermat, para todos los posibles b, con m. c. d (n,b) = 1, tenemos el 50 % de probabilidad de que n falle el test de Fermat, para un b seleccionado aleatoriamente.

Se supone que buscamos un entero impar muy grande n, que además sea primo, podemos elegir al azar un número b aleatorio en un rango 0 < b < n, primero buscamos un valor d = m. c. d (b, n) usando el algoritmo de Euclides, si d > 1, pensamos que n no es primo, si d = 1, entonces elevamos b a la (n-1) potencia , si no satisface el test de Fermat, entonces en compuesto.

Si n satisface el test de Fermat, tenemos una evidencia de que es posible que n sea primo, entonces probamos con otro b, y reiniciamos el proceso. Si se falla para algún b, detenemos el proceso, entonces tenemos la certeza de que n es compuesto.

Probamos k valores de b, y buscamos que n sea un pseudoprimo para todas las k bases.