www.matematicas.net

LO DIJO...

Isaac Asimov  
 
El aspecto más triste de la vida actual es que la ciencia gana en conocimiento más rápidamente que la sociedad en sabiduría.
 
www.matematicas.net - Criptotaller ~ Números primos, teoría y práctica
.: Criptotaller :.
 
Números primos, teoría y práctica

    Los números primos además de tener un papel señalado en muchas ramas de las matemáticas, ejercen una cierta fascinación sobre algunas personas entre las que me cuento. Además son importantes para algúnos métodos criptográficos como los de clave pública RSA

    Primero la definición: un número primo es un entero positivo mayor que 1 que es divisible sólo por si mismo y la unidad. El resto de los enteros mayores que 1 se llaman compuestos.

    Buena parte de su alcance se debe a un teorema fundamental en la aritmética que nos asegura que cualquier entero positivo se expresa de forma única como producto de primos.

Pequeños números primos

    El algoritmo simplemente hace las divisiones necesarias y es por tanto lento con números "grandes".

     El número debe ser un entero positivo si quieres obtener resultados correctos.

Número

Resultado

    Por si no quieres o puedes calcularlos tu mismo, aquí tienes la lista de los primos del 1 al 10.000 y aquí del 1 al 100.000. También puedes bajarte el programa que usé para generarlas: ejecutable (MS-DOS) y fuente (en C)

Distribución

    Sobre la distribución de estos números podemos hacernos dos preguntas: ¿cuántos hay? ¿están espaciados regularmente?

    A la primera pregunta se contesta que hay infinitos números primos. Una demostración elemental por reducción al absurdo se la debemos a Euclides. En notación moderna sería más o menos así: supongamos que p fuese el último primo, consideramos el número n= p!+1 (p! denotará el factorial de p, es decir p(p-1)(p-2)...1 ). Pues bien n como cualquier número tendrá al menos un factor primo, llamémoslo q. Si q fuese menor que p entonces q divide a p! por definición de factorial, pero entonces q dividiría simultáneamente a los números n y n-1 lo cual es imposible. Es decir que q>p en contra de la hipótesis de que p es el mayor.

    En cuanto a como están distribuidos diremos en primer lugar que son cada vez más escasos a medida que crece su tamaño pudiendo encontrar "rachas" tan grandes como queramos sin números primos. A la vez se conjetura que existen infinitos pares de primos gemelos (p y p+2 como por ejemplo 11 y 13).

    Más exactamente se demuestra que el número de primos menores que x denotado PI(x) (aquí tendría que haber la letra griega PI, ya me entendéis) se aproxima asintóticamente a x/Ln x. La demostración de este hecho la debemos independientemente a Hadamard y de la Vallée Poussin. Una aproximación mejor aún a PI(x) es la integral entre 2 y x de dt/Ln t. Si llamamos a esta función LI(x) observemos en una tabla el número real de primos menores que x en comparación con LI(x) y x/Ln x:

x PI(x) x/Ln x PI(x)/ (x/Ln x) LI(x) PI(x)/
LI(x)
10^3 168 145 1'160 178
0'947820
10^6 78.498 72.382 1'085 78.628 0'998347
10^9 50.847.534 48.254.942 1'054 50.849.235 0'999966
10^12 37.607.912.018 36.191.206.825 1'039 37.607.950.281 0'999999

Otros resultados sobre la distribución de primos

  • Para cada N>1 existe un primo entre N y 2N (Chebyshev)
  • Si a y b son números naturales primos entre sí, la sucesión a+n.b contiene infinitos números primos.
Clases especiales de números primos

Números de Fermat: son de la forma 22k+1, Fermat conjeturó que todos eran primos y de hecho {3,5,17,257,65.537} , los cinco primeros lo son pero desde el 6º hasta el 17º no lo son, ni muchos otros posteriores. Se ignora si hay más primos en esta serie.

Números de Mersenne: son de la forma 2k-1 y aparecen al estudiar los números perfectos (iguales a la suma de sus divisores propios). Sólo pueden ser primos si k lo es. Se conocen gracias al ordenador un buen número de ellos. Los mayores primos conocidos son de esta forma; por ejemplo en el 2001 se calculó el mayor conocido, que es 2^13466917 - 1 , ¡un primo con 4.053.946 dígitos nada menos!

Aún sin resolver

    La teoría de números primos presenta varios problemas fáciles de plantear pero muy difíciles de resolver. Por ejemplo:

  • La existencia o no de infinitos primos gemelos (p y p+2)
  • Cualquier número par mayor que 2 puede ponerse como suma de dos primos (Conjetura de Goldbach)
Test avanzado de primalidad

    Determinar si un número es primo haciendo todas las divisiones hasta la raíz cuadrada como se hace en la calculadora de esta página es un método muy ineficiente, aunque elemental, especialmente para grandes primos (digamos mayor que 10.000.000). Dado que en algoritmos como RSA se necesitan primos de cien dígitos o mas necesitamos hacer algo mejor.

Definición

     Sea n un entero positivo con n-1 = 2s.t , siendo s un entero no negativo y t un entero positivo impar. Decimos que n pasa el test de Miller en la base b si bt = 1 (mod n) o bien que b2j.t = -1 (mod n) para algún j, con 0<= j <= s-1.

    Ahora bien, puede demostrarse que un número primo pasa el test de Miller para todas los enteros menores que él. Los números compuestos que pasan el test de Miller, aunque extraordinariamente raros son infinitos en cantidad.

Definición

     Los números compuestos que pasan el test de Miller para la base b se denominan pseudoprimos fuertes en base b.

    Para centrar ideas: si un entero no pasa el t. de M. para algúna base b entonces es automáticamente compuesto y en otro caso podría ser primo.

    A algúnos resultados experimentales junto con el test de Miller constituyen un test rápido de primalidad para enteros relativamente pequeños.

  • Si n<2.047 es P.F. en base 2 entonces es primo.
  • Si n<1.373.653 es P.F. en bases 2 y 3 entonces es primo.
  • Si n<25.326.001 es P.F. en bases 2,3 y 5 entonces es primo.
  • Si n<118.670.087.467 es P.F. en bases 2,3,5 y 7 entonces o bien n=3.215.031.751 o bien n es primo.
  • Si n<2.152.302.898.747 es P.F. en bases 2,3,5,7 y 11 entonces n es primo.
  • Si n<3.747.749.660.383 es P.F. en bases 2,3,5,7,11 y 13 entonces n es primo.
  • Si n<341.550.071.728.321 es P.F. en bases 2,3,5,7,11,13 y 17 entonces n es primo.
(Datos de la página de Chris Caldwell) Ahora bien para números aún mayores utilizaremos el siguiente

Test probabilístico de primalidad de Rabin

    Sea n un entero positivo, tomemos k diferentes enteros positivos menores que n y realizaremos el test de Miller para cada uno de ellos. Si n es compuesto la probabilidad de que los pase todos es menor que (1/4)k.

    Bien, este test no nos dice que un número es primo sino que lo es con tanta certeza como nosotros deseemos (según el número de pruebas realizadas). Por ejemplo, tomando 100 bases al azar entre 1 y n, la probabilidad de que n pase todos los tests siendo compuesto es de sólo 10-60, un número pequeñísimo. De hecho es más creíble que el ordenador haya cometido un error en los cálculos (especialmente usando un Pentium-TM :-) ) que no que el número sea compuesto.

Referencias

Atlas de Matemáticas, Rinhardt y Soeder
Elementary number theory and its applications, Rosen
http://www.utm.edu/research/primes

Area On-Line
  Todo tipo de material, para disfrutar de él completamente On-Line, sin necesidad de descargar archivos ni tener que andar descomprimiendo estos. No te olvides de pasar por el Diccionario, y las secciones Origami y Geointeractiva. Son de lo más interesante.

Criptotaller

Criptografía (clásica y moderna), criptoanálisis (primos, primos de Mersenne, etc.) y otras técnicas.

Material para descargar

Código Fuente C

Método Hill
Método Jefferson
Exponenciación Modular
Cálculo números primos
Test de Lucas-Lehmer
Factores num. Mersenne
Verificación FIPS 140.2
Teorema chino del resto
+ Códigos Fuente C

Código Fuente Python

Generación de claves

Artículos

La máquina Enigma
Criptografía y seguridad
    M. J. Lucena
Seguridad Informática
   y Criptografía PDF PPT
    J. Ramió
Criptografía clásica PDF
    J. Ramió

Programas
Cripto1 ZIP 2391 KB
    J. L. Rubio

Enlaces

Página personal de Jaime Suárez Martínez, colaborador de esta sección.

Munitions, colección de programas para Linux.

Kriptopolis, toda una referencia en castellano.

Ciphersaber

Criptonomicón: la página de Gonzalo Alvarez Marañón.

Página de Chris Caldwell, una página bien elaborada sobre números primos.

Colección de links de Peter Gutmann.

www.gnupg.org es la página original de GPG, un programa libre alternativo a PGP.

Viernes, 24 / 10 / 2014
   BUSCADOR
 

   TU CORREO
Usuario
Contraseña

   MATRACAS
Lista de correo gratuita
.: Chismes de Adán y Eva :.
Adios a Elisenda Fo...
WolframAlpha: El mo...
WIRIS para Mac...
Third CEU Summersch...
¡Más y más actualiz...
Cerca de 500 MB de ...
Ha llegado el momen...
WIRIS, matemáticas ...
El Universo Matemát...
Segundas Jornadas d...
Los Elementos de Eu...
VI Semana de la Cie...
Tras varios meses d...
¡Chiflados por los ...
Otro verano más, to...

 

Todos los derechos reservados. El Paraíso de las Matemáticas 2010Información Legal Política de PrivacidadAyudaEmail