Siguiente: Máquinas probabilísticas Un nivel arriba: Algoritmos probabilísticos Anterior: .

Método de Monte-Carlo para probar primicidad

El siguiente algoritmo, debido a Solovay y Strassen, decide probabilísticamente si acaso n es un número primo.


Input:

Output:




Even more

$$\mbox{\rm Prob}(\mbox{\rm Yes}\vert n\not\in\mbox{\rm Primes})<\frac{1}{2}.$$

1234567890123456789012345678901234567890 Choose $a\in [1,n-1]$
; 

		 $x:=\mbox{\rm gcd}(a,n)$
; 

		 if x>1 then ``No'' 

		 else { 

				 $\epsilon :=a^{\frac{(n-1)}{2}}\mbox{\rm mod }n$
;


				 $\delta := \left(\frac{a}{n}\right)$
; 

				 if $\epsilon=\delta$
then ``Yes'' else ``No'' 

				}  

Observaciones: 1. Igual que antes, al reiterar m veces la selección de números de prueba a la probabilidad de error se minimiza, a lo sumo es 2^-m. 2. La complejidad del algoritmo, en cuanto a operaciones aritméticas y cálculos de residuos entre números menores que n², es

$$O(m\log n).$$