Determinista

Las pruebas Deterministas confirman con toda certeza que un número es primo. La primera forma documentada de identificarlos es la  criba de Eratóstenes de Cirene, realizada por Nicómaco de Gerasa en el siglo I, posteriormente Bn-Al Banna al-Murrakushi, siglo XIII, propone mejorar la criba de Eratóstenes indicando que es suficiente con repetir el proceso hasta los divisores primos menores que √x.

 

A partir de aquí muchos han sido seducidos por la incertidumbre y han tratado de encontrarlos por diversos caminos. Los avances teóricos se produjeron con Fermat, Euler y Legendre en el siglo XVII y con Gauss en el XVIII, los computacionales a partir del siglo XX. La búsqueda para hallar una fórmula magistral no se ha detenido y en una huida hacia adelante se han puesto los más importantes matemáticos y potentes ordenadores en sintonía para encontrarlos.

Existen otros algoritmos probabilísticos que con pequeñas modificaciones pueden transformarse en deterministas (Monte Carlo, Solovay-Strassen, Miller-Rabin).

 

A partir de aquí una breve relación de métodos, algoritmos, ideas, variantes e intervinientes más destacados, que no es completa y desarrollaremos en páginas sucesivas:

 

 

• Conjeturas, teoremas y congruencias.
  • Teorema chino del resto.
  • Petit théorème. Pierre de Fermat
  • Conjetura de Goldbach.
  • Primos de Marin Mersenne.
  • Ley de Reciprocidad cuadrática.
  • Teorema de los números primos.
  • …

 

• Cribas.
  • Eratóstenes
  • Geométrica o de la parábola.
  • Grande.
  • Asintótica
  • Rueda
  • Lineal
  • Cuadrática
  • Algebraica
  • Combinatoria
  • …

 

• Algoritmos computacionales
  • APR Adleman – Pomerance – Rumely. H. Cohen, A. K. Lenstra
  • ECPP “Elliptic Curve Primality Proving”, Shafi Goldwasser , Joe Kilian
  • AKS Manindra Agrawal – Neeraj Kayal – Nitin Saxena
  • …

 

Fijaros que todos terminan con puntos suspensivos, la profundidad de este apartado (mundo) es mucho mayor de lo imaginable en una primera lectura. Para ir introduciéndonos proponemos un procedimiento fácil de ejecutar y obtener primos:

 

1. Generamos un número aleatorio impar (n).
2. Dividimos n por una tabla de primos pre-calculados. Esto elimina gran cantidad de no primos de una forma muy rápida, la mayoría (± 90%) de los no primos son divisibles por algún número primo menor de 3.000, un ejemplo está en factorizar, donde se factorizan números hasta los tres mil millones.
3. Ejecutamos una criba o algoritmo sobre n para ver si es primo, en caso contrario volvemos al punto 1.