Metodo Probabilistico De Mr.rabin; Traduccion En Los Calculos Algoritmicos - HP 40G Manual Del Usuario

8.6 Metodo probabilistico de Mr.Rabin

Si N es primo todos los números K, estrictamente inferiores a N, son primos
deN, por lo tanto según el Teorema de Fermat, tenemos:
N-1
K = 1 (mod N)
Si N no es primo, los números enteros K que verifican:
N-1
K = 1 (mod N)
Son poco numerosos.
Con más precisión se puede demostrar que si N > 4 la probabilidad de obtener
es número k es inferior a 0,25.
Un número N siendo K
pseudoprimo. El método probabilístico de consiste en coger al azar un número
K (1 < K < N) y calcular:
N-1
K (mod N)
N-1
Si K = 1 (mod N) se coge otro número y si K
no es primo.
N-1
Si se obtiene K = 1 (mod N) para 20 valores de K podemos determinar que
K es primo
con una probabilidad de error inferior a 0.25
Este método se utiliza únicamente para saber si números muy grandes son
pseudo-primos.
8.6.1

Traduccion en los Calculos Algoritmicos

Suponemos que:
Hasard(N) da un número entero al azar entre 0 y N – 1.
el cálculo de:
N-1
K mod N
Se hace con el algoritmo de la potencia rápida (véase 13).
Teclee:
Puismod (K, P, N) la función que calcula K
Funcion esprim(N)
local K, I, P
Programas de Aritmetica
Calculo Simbólico y Matemático con la HP 40G
N-1
= 1 (mod N) para 20 pruebas de es un número
N-1
20 –12
de orden...10 .
P
mod N
163