3. Problemas computacionales


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.... .