En criptografía se necesitan
generar números primos muy grandes que no se puedan factorizar para
así hacer imposible el descubrimiento de claves.
NÚMEROS PRIMOS
No existe ninguna fórmula algebraica que permita generar números primos. Pero hay métodos para saber si un número grande es primo o no con una gran probabilidad muy grande. Son medidas anticriptoanálisis.
TEST PARA SABER SI UN NÚMERO ES PRIMO O NO:
¿p primo?
Se coge a un número aleatorio tal que a<p
b=a^((p-1)/2) mod p
si b<>1 y b<>p-1 entonces p no primo
sino 50% más de posibilidad de que p sea primo
COMO GENERAR UN PRIMO GORDO:
- Seleccionamos un número muy gordo
- Se divide por los números primos
del 1 al 2000 y si no es divisible por ninguno entonces habrá gran
probabilidad de que sea primo
- Se ejecuta el test anterior 10 o más
veces
- Si supera todo esto existirá
muchísima probabilidad de que sea primo.
PRIMOS FUERTES
Para que dos números sean primos fuertes tienen que cumplir:
1- m.c.d.((p-1),(q-1)) es un número
muy pequeño
2- p-1 y q-1 tienen algún factor
primo (p',q') que es muy grande
3- p'-1 y q'-1 tienen algún factor
primo muy grande
4- p´+1 y q'+1 tienen algún
factor primo muy grande
NÚMEROS ALEATORIOS
Son aquellos números que son totalmente
impredecibles. Generar un número aleatorio es fácil pero
generar una secuencia de números aleatorios es más difícil.
Hay números aleatorios y semialeatorios.
Los semialeatorios son generados a partir
de una semilla, por lo tanto si la semilla es la misma se generaran secuencias
iguales.
Los aleatorios son generados a partir
de sucesos aleatorios como el reloj de un ordenador o el movimiento del
ratón, etc.... .