Download IMD-IS 2011–2012. Sesión de laboratorio 5. Números primos

IMD-IS 2011–2012. Sesión de laboratorio 5.
Números primos
La hoja de SAGE que corresponde a la práctica puede obtenerse de:
http: // personal. us. es/ ebriand/ practica5. sws
En esta práctica, se propone un reto: hallar al mayor número
primo posible, por varios métodos.
¿ Cómo se hace, en práctica, para crear un gran número primo ? Por ejemplo, en el sistema RSA, se necesita producir números
primos de longitud 1024 bits (son números con más de 300 cifras
decimales). Pues, se producen números de este tamaño aleatoriamente, hasta obtener uno que sea primo. Para esto, es necesario
poder determinar si un número es primo o no. Hay varios “tests de
primalidad”, más o menos eficientes, que realizan este trabajo.
El test ingenuo
El test ingenuo consiste en comprobar que ningún entero entre
2 y p − 1 divide p. Admite una ligera mejora: basta comprobar que
√
ningún entero entre 2 y p divide p. En efecto tenemos el resultado
elemental siguiente:
√
Teorema 1. Si p no es primo, entonces admite un divisor entre 2 y p.
def testingenuo(p):
i=2
while i^2 <= p:
if p%i == 0:
return False
i=i+1
return True
Ejercicio 1. Obtener un número primo tan grande como posible
con el test ingenuo. ¿ Parece realista obtener de esta manera números primos de 1024 bits ?
El test de Fermat.
El test de Fermat se basa, por una parte, en el teorema siguiente:
Teorema 2 (Pequeño teorema de Fermat). Sean a y p dos enteros
positivos, con 1 ≤ a ≤ p − 1. Si a p−1 6≡ 1 mod p, entonces p no es
primo.
Se basa también en el resultado complementario siguiente (no es
un teorema, porque su contenido es algo impreciso):
Si a > 1 y a p−1 ≡ 1 mod p, entonces muy probablemente p es
primo.
2
Sea a > 1. El test de Fermat en base a para un entero p > a
consiste en calcular a p−1 modulo p.
Si a p−1 6≡ 1 mod p, entonces p no es primo, por el pequeño
teorema de Fermat. Decimos que p no pasa el test de Fermat en base
a. Decimos también que a es un testigo de que p no es primo.
Sino, decimos que p pasa el test de Fermat en base a. Hay dos posibilidades:
• La más probable: p es primo.
• La menos probable: p no es primo, a pesar de pasar el test de
Fermat en base a. En este caso decimos que p es una pseudoprimo en base a. Decimos también que a es un falso testigo de
primalidad de p.
Es lo que se llama en estadística un
“falso positivo”.
Si un número p pasa el test de Fermat en base a, probablemente
es primo. Como es solamente “probablemente primo”, este test no
basta para demostrar que un número es primo. Sin embargo, es de
interés para las aplicaciones (por ejemplo, en criptografía) donde una
pequeña incerteza puede ser tolerada.
Si un número p pasa el test de Fermat en base a, podemos hacerle pasar el test de Fermat en otras bases, para tener una probabilidad aún más fuerte que sea primo.
Ejemplo 1. Consideramos p = 341. Pasa el test de Fermat en base 2
(2340 ≡ 1 mod 341). Sin embargo, no pasa el test de Fermat en base
3: 3340 ≡ 56 6≡ 1 mod 341.
♦
Desgraciadamente hay números p (una infinidad) que no son
primos y que pasan el test de Fermat en todas las bases a primas
con p. Estos números se llaman números de Carmichael. Afortunadamente, la proporción de números de Carmichael es bastante
pequeña.
Ejercicio 2.
Escribir una función Fermat1 que toma como argumentos los
enteros a y p y determina si p pasa el test de Fermat en base a.
Comprobar que funciona, sobre pequeños ejemplos (p con poco
más de 10 cifras). La función tienen que calcular a p−1 mod p ¿
Es necesario, para esto, calcular a p−1 (un entero muy largo) ?
Hallar un número no primo (otro que 341) que pasa el test de
Fermat en base 2, pero no lo pasa en base 3.
¿ Se nota alguna mejora significativa con respecto al test ingenuo ? (A continuación mejoraremos el test de Fermat).
¿ Parece realista obtener de esta manera números primos de 1024
bits ?
Utilizando Fermat1, hallar números “probablemente primos” tan
grande como posibles (la elección más simple de a es a = 2).
Cálculos con grandes enteros pueden
bloquear la máquina. Pinchar entonces,
si se puede, en “interrupt”, o “restart”
en el menu “Action” (segundo menu
arriba a la derecha en la hoja de
SAGE).
3
El test de Fermat con exponenciación rápida
En la función Fermat1 se calcula a p−1 con p − 2 multiplicaciones.
Es posible de hacer el mismo cálculo con mucho menos multiplicaciones. Por ejemplo, para calcular a168 no son necesarias 167
multiplicaciones: bastan 9.
Para esto, organizamos los cálculos de la manera siguiente:
Calculamos a2 con una sola multiplicación, como a × a.
Calculamos a4 con una sola multiplicación, como a2 × a2 .
Calculamos a8 con una sola multiplicación, como a4 × a4 .
Calculamos a16 (una multiplicación).
Calculamos a32 (una multiplicación).
Calculamos a64 (una multiplicación).
Calculamos a128 (una multiplicación).
No calculamos a256 , no sirve, es demasiado grande, es mayor
que a168 .
Observamos que a168 = a128 × a32 × a8 , ya que 168 =
128 + 32 + 8 (corresponde al hecho que la escritura binaria de 168 es 10101000). Por lo tanto calculamos a168 con
solamente dos multiplicaciones más.
Esta manera eficiente de calcular una potencia repitiendo elevaciones al cuadrado se llama exponenciación rápida. Hace que el test
de Fermat sea muy eficiente.
Ejercicio 3.
Comprobar (con algunos ejemplos) que la función bits de SAGE
proporciona la escritura binaria de un entero. ¿ Dónde está el bit
menos significativo ?
Escribir una función Fermat2 que realiza el test de Fermat, utilizando la exponenciación rápida.
Utilizar Fermat2 para obtener nuevos records de grandes números primos ¿ Se observa alguna mejora significativa con respeto a
los tests anteriores ?
Ejercicio adicional
Ejercicio 4. Facultativo; para los que acabaron todos los ejercicios
anteriores
Encontrar todos los primeros números pseudoprimos en base 2 (por
ejemplo hasta 2000).
Encontrar todos los primeros números de Carmichael (por ejemplo
hasta 2000).
Se utiliza así: 167.bits() para obtener
los bits de 167.
4
Observaciones adicionales
Existen tests de primalidad más sofisticados que el test de Fermat (como por ejemplo el test de Miller–Rabin) que garantizan que
un número es primo con una probabilidad arbitraria. Por ejemplo,
se puede garantizar que un número p es primo con un probabilidad
99, 99999999999999999 % (o cualquiera probabilidad estrictamente
inferior a 1) a condición de hacer funcionar el test el tiempo necesario. Son estos tests que se utilizan en las aplicaciones industriales
(criptografía).