He encontrado múltiples formas de determinar si un número es primo, pero me preguntaba cómo se elige un número en primer lugar. Por ejemplo, el proyecto GIMPS supongo que se limita a probar diferentes números para elevar al cuadrado 2, pero ¿qué pasa con otros métodos? ¿O se trata simplemente de un proceso de prueba de todos y cada uno de los números desconocidos?
GIMPS sólo considera los primos de Mersenne, por lo que existe una fórmula fija.
Sin embargo, si se busca un primo "grande", por ejemplo de 1024 bits, que sea adecuado para la criptografía, es un primo $p$ con $2^{1024} < p < 2^{1025}$ . Fuera del $2^{1024}$ números en el rango, aproximadamente $$\frac{2^{1025}}{\log 2^{1025}} - \frac{2^{1024}}{\log 2^{1024}}$$ son primos. Así que la fracción que es prima es $$\frac{2}{\log 2^{1025}} - \frac{1}{\log 2^{1024}}= \frac{2}{1025\log 2} - \frac{1}{1024\log 2} = 0.001406$$ Como puedes probar todos los que quieras, no son tan malas probabilidades.
Ver es.wikipedia.org/wiki/Teorema del primer número para más información sobre la densidad de los primos.
Por el teorema frívolo de la aritmética, los grandes primos que se han encontrado son bastante pequeños. Digamos que $p$ es el mayor primo conocido. Entonces entre $p$ y $p^p$ hay aproximadamente $$\frac{p^p}{\log p^p} - \frac{p}{\log p}$$ primos que son mayores que $p$ , y por supuesto $p^p$ sigue estando bastante lejos del infinito. Este es un número bastante grande (para nosotros) cuando conectamos algo como $p = 2^{74207281} - 1$ el mayor número primo conocido ahora mismo según las páginas principales .
No es sorprendente que este mayor primo conocido sea un primo de Mersenne, un número de la forma $2^n - 1$ (y $n$ también es primo). Las otras personas que han respondido ya han mencionado la prueba de Lucas-Lehmer. Sólo por diversión pruébalo con $2^{31} - 1$ puede resultar bastante más rápido que la división de prueba hasta $\sqrt{2^{31} - 1} \approx 46340$ .
Pero sigue llevando mucho tiempo. Tome nota de estas observaciones de Chris Caldwell sobre $2^{74207281} - 1$ :
Este primo fue detectado por primera vez por una máquina el 17 de septiembre de 2015, pero no fue advertido por un humano hasta el 7 de enero a las 22:30 UTC, por lo que esta es la fecha oficial del descubrimiento.
La prueba de primalidad llevó 31 días de computación ininterrumpida en un PC con una CPU Intel I7-4790. Para demostrar que no hubo errores en el proceso de descubrimiento del primo, el nuevo primo se verificó de forma independiente utilizando software y hardware diferentes. Andreas Hoglund y David Stanfill verificaron el primo utilizando el software CUDALucas en GPUs NVidia Titan Black en 2,3 días. David Stanfill lo verificó utilizando ClLucas en una GPU AMD Fury X en 3,5 días. Serge Batalov también lo verificó utilizando el software MLucas de Ernst Mayer en dos servidores Amazon EC2 Intel Xeon de 18 núcleos en 3,5 días.
El mayor primo no Mersenne conocido hasta la fecha es $10223\times2^{31172165} + 1$ . Este primo es especial porque pertenece al problema de los números de Sierpinski, que no voy a detallar aquí.
Así que lo que hacen proyectos como GIMPS y Seventeen or Bust es buscar primos que puedan ser expresados de una determinada manera compacta. Pero están limitados en cuanto a su alcance. Por ejemplo, ¿es $2^{2^{127} - 1} - 1$ ¿primas? Algunos dicen que no hay suficientes recursos en el universo para responder a esa pregunta.
Hace unos meses hubo una pregunta relacionada, algo así como cuál es el mayor número primo $p$ de manera que el valor de $\pi(p)$ se conoce con exactitud? (por ejemplo, $\pi(7) = 4$ , $\pi(11) = 5$ etc.) Obviamente $\pi(2^{74207281} - 1)$ por el momento sólo puede estimarse.
Pero, si definimos $\pi_M(n)$ para decirnos cuántos primos de Mersenne hay menores o iguales a $n$ Resulta que $\pi_M(2^{74207281} - 1)$ también se desconoce. Se cree que es el 49, pero podría ser fácilmente el 50 o el 51 (supongo que también podría ser el 52 o más, pero apostaría dinero contra eso).
Supongo que podría hablar de esto durante horas. Quizá lo más útil que podría decirte es que juegues con Wolfram Alpha. Escriba NextPrime[ y luego un número "aleatorio" de 20 dígitos, ] y pulse "Enter". Es posible que obtenga un número primo demasiado pequeño para las aplicaciones prácticas de la criptografía, pero demasiado grande y poco probable que aparezca en una conversación cotidiana.
Se pueden generar números primos utilizando el pequeño teorema de Fermat. Este teorema afirma que si $p$ es primo y $a\neq 0 \bmod p$ entonces:
$$a^{p-1} = 1 \bmod p$$
Supongamos entonces que para algún número $n$ y algunos $a\neq 0 \bmod n$ la ecuación anterior se mantendría al tomar $p$ igual a $n$ . Entonces eso no demuestra que $n$ es primo. Para llegar a una prueba de primalidad rigurosa, hay que hacer más pruebas, véase, por ejemplo aquí . Pero la inversa del pequeño teorema de Fermat es cierta si $n$ es de la forma $h p + 1$ o $h p^2 + 1$ y $h < p$ para algún primo conocido $p$ . Así, esto te permite generar primos cada vez más grandes utilizando sólo el pequeño teorema de Fermat como prueba de primalidad.
He aquí un ejemplo sencillo utilizando mi calculadora HP que permite el cálculo de enteros con un máximo de 12 dígitos. Entonces estoy restringido a encontrar primos más pequeños que $10^6$ debido a tener que calcular repetidamente el módulo cuadrado $n$ para calcular grandes potencias. Si empiezo con $p = 13$ entonces $n_1 = 10\times p + 1 = 131$ pasa la prueba de Fermat, por lo tanto $n_1$ es primo. Entonces $n_2 = 50\times n_1 + 1 = 6551$ pasa la prueba, por lo tanto $n_2$ es primo. Entonces encuentro que $n_3 = 122\times n_2 + 1 = 799,223$ pasa la prueba, por lo que $n_3$ es primo. Así, en pocos minutos pude encontrar este gran primo utilizando únicamente mi antigua calculadora HP.
Utilizando el poder de la computación distribuida para probar posibles números primos de formas específicas.
La más famosa es, por supuesto, la búsqueda de los primos de Mersenne, que son de la forma $2^p - 1$ , donde $p$ también es primordial. Esto ayuda a reducir la búsqueda. Por ejemplo, sabemos inmediatamente que $2^{91} - 1$ no es primo, porque es divisible por $2^7 - 1$ y $2^{13} - 1$ .
Pero no todos los primos dan primos como exponentes de Mersenne. Por ejemplo, $2^{23} - 1 = 47 \times 178481$ . Hay formas de detectar un montón de primos como $23$ , acotando aún más la búsqueda. Según la Gran Búsqueda de Primeros de Mersenne en Internet (GIMPS) los ordenadores más lentos de la red tienen la tarea de buscar primos como $23$ para que los ordenadores más rápidos puedan concentrarse en probar los primos con mayor probabilidad de ser exponentes primos de Mersenne.
Sin embargo, de vez en cuando se encuentran grandes números primos casi por accidente. Por ejemplo, si $a_0 = 20615674205555510$ y $a_1 = 3794765361567513$ la secuencia definida por $a_n = a_{n - 2} + a_{n - 1}$ para $n > 1$ no contiene ningún primo. Sin embargo, si se intercambia $a_0$ y $a_1$ entonces $a_{138} = 439351292910452432574786963588089477522344721$ es primo.
En noviembre $9$ , $2005$ Eric W. Weisstein anunció que $a_{156075}$ también es primo. Consulte Mathworld para más detalles. Son números pequeños comparados con el mayor primo de Mersenne conocido, e incluso más pequeños comparados con números primos más grandes que nuestra comprensión.
La mayoría de los grandes primos que han batido récords recientemente han sido números de Mersenne, es decir, de la forma $2^p-1$ (que sólo puede ser primo para los primos $p$ ), porque tienen una prueba especialmente fácil: https://en.wikipedia.org/wiki/Lucas-Lehmer_primality_test Así que seguimos probando sucesivamente mayores $p$ en decenas de millones. A veces, se utiliza esto en su lugar: https://en.wikipedia.org/wiki/Lucas-Lehmer-Riesel_test
I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.
0 votos
En general, se eligen porque son el resultado de una fórmula cerrada. Mira aquí o aquí .
0 votos
Se han encontrado primos de muchos otros tipos de números (primos factoriales ; forma $n!\pm 1$ , primorosos primorosos ; forma $p$ # $\pm1$ , donde $p$ # $=2\cdot 3\cdot 5\cdots\cdot p$ , primos de fibonacci (números de fibonacci que son primos) , primos de repuntes ; forma $\frac{10^n-1}{9}$ la expansión decimal sólo contiene de $n$ y muchos más) pero, como se indica en las respuestas siguientes, los mayores primos conocidos son los primos de Mersenne. La elección de los números depende del tipo de primos que se quiera obtener.
1 votos
El enfoque general para encontrar números primos grandes consiste en cribar los factores pequeños para obtener candidatos (números que podrían ser primos) antes de comprobar si son realmente primos. Esto lleva bastante tiempo en el caso de números muy grandes y la posibilidad de tener éxito es pequeña incluso si tamizamos los factores primos hasta $10^9$ más o menos. En resumen, encontrar (nuevos) primos muy grandes sigue siendo difícil.