Generar número primo grande con los últimos dígitos especificados

Question

¿Se preguntaba cómo es posible generar números primos de 512 bits (155 dígitos decimales), los últimos cinco dígitos decimales que se especifican/fijan (por ejemplo, *** 28071)?

Los principios de generar primos simples sin ninguna especificación son bastante comprensibles, pero mi caso va más allá.

¿Alguna sugerencia para, al menos, dónde debería comenzar?

Java o C# es preferible.

Gracias!

Answer 1

supongo que la única manera sería generar primero un número aleatorio de 150 dígitos decimales, a continuación, añadir el 28071 detrás de él haciendo number = randomnumber * 100000 + 28071 fuerza luego simplemente bruta hacia fuera con algo así como

while (!IsPrime(number)) 
    number += 100000; 

Por supuesto, esto podría tomar un tiempo para calcular ;-)

Answer 2

¿Intentó simplemente generar esos números y verificarlos? Yo esperaría que sea aceptablemente rápido. La densidad principal disminuye solo como el logaritmo del número, por lo que esperaría que probaras unos pocos cientos de números hasta llegar a la primogenitura. ln(2^512) = 354 así que aproximadamente un número en 350 será primo.

En términos generales, el teorema del número primo establece que si cercano se selecciona algún número grande N un número aleatorio, la posibilidad de que sea primo es aproximadamente 1/ln (N), donde ln (N) denota lo natural logaritmo de N. Por ejemplo, cerca de N = 10,000, aproximadamente uno de cada nueve números es primordial, mientras que cerca de N = 1,000,000,000, solo uno de cada 21 números es primo. En otras palabras, la diferencia media entre los números primos cerca de N es más o menos ln (N)

(desde http://en.wikipedia.org/wiki/Prime_number_theorem)

Sólo tiene que tener cuidado de que existe un número para sus dígitos finales. Pero creo que es tan fácil como verificar que el último dígito no sea divisible entre 2 o 5 (es decir, es 1, 3, 7 o 9).

Según this performance data se puede hacer sobre 2.000 operaciones ModPow en datos de 512 bits por segundo, y desde una simple prueba de acondicionamiento está comprobando 2^(p-1) mod p=1 que es una operación ModPow, usted debe ser capaz de generar varios números primos con sus propiedades por segundo .

Por lo que podría hacer (pseudocódigo):

BigInteger FindPrimeCandidate(int lastDigits) 
{ 
    BigInteger i=Random512BitInt; 
    int remainder = i % 100000; 
    int increment = lastDigits-remainder; 
    i += increment; 
    BigInteger test = BigInteger.ModPow(2, i - 1, i); 
    if(test == 1) 
     return i; 
    else 
     return null; 
} 

Y hacer un control más minucioso privilegiada en el resultado de esa función.

Answer 3

Puede ampliar uno de los standard methods for generating large primes añadiendo una restricción adicional, es decir, los últimos 5 dígitos decimales deben ser correctos. Ingenuamente, puedes agregar esto como una prueba adicional pero aumentará el tiempo para encontrar un primo adecuado por 10^5.

No tan ingenuo: genere un número aleatorio de 512 bits y luego configure suficientes bits de bajo orden para que la representación decimal finalice con la secuencia requerida. Luego continúe con las pruebas de primalidad normales.

Answer 4

Consideremos la fuerza bruta.Echar un vistazo a este texto muy interesante llamado "El número primo lotería":

• http://plus.maths.org/content/prime-number-lottery

Dada la última entrada de la última mesa, hay ~ 2,79 * 10^14 números primos menos de 10^16. Por lo tanto, aproximadamente cada 35º número es un primo en ese rango.

EDIT: Vea el comentario de CodeInChaos - si solo camina unos pocos miles de números de 512 bits con los últimos 5 dígitos corregidos, encontrará uno rápidamente.

Answer 5

Como dijo @Doggot, pero comienza desde el número de 150 dígitos menos posible que termina en 28071, significa 100000 ... 0028071, ahora sume 100000 cada vez y para las pruebas use principalmente miller rabin como el código que proporcioné here, necesita un poco de personalización. Si el valor de retorno es verdadero, compruébalo en forma exacta principalmente.

Answer 6

Puede utilizar un tamiz que contiene sólo números que satisfacen su condición especial para filtrar los números divisibles por pequeños primos.

Para cada prima pequeña p debe encontrar el punto de partida y el paso correcto teniendo en cuenta que solo cada 100000º número está presente en el tamiz.

Para los números que sobreviven al tamiz, puede usar BigInteger.isProbablePrime() para verificar si es primo con suficiente probabilidad.

Answer 7

Reescribí el algoritmo de fuerza bruta del mundo int a la BigDecimal uno con la ayuda de la clase BigSquareRoot de http://www.merriampark.com/bigsqrt.htm. (Tenga en cuenta que de 1 a 1000 no se dice que es exactamente 168 números primos.)

Lo sentimos, pero si se pone allí su rango, es decir ; 10 -1>, puedes dejar que tu computadora funcione y cuando te hayas retirado, puedes tener el resultado ... ¡es muy lento!

Sin embargo, de alguna manera puede encontrar por lo menos una parte de esto, tiene utilidad en combinación con las otras respuestas en este hilo.

 

package edu.eli.test.primes; 

import java.math.BigDecimal; 

public class PrimeNumbersGenerator { 

    public static void main(String[] args) { 
// BigDecimal lowerLimit = BigDecimal.valueOf(10).pow(154); /* 155 digits */ 
// BigDecimal upperLimit = BigDecimal.valueOf(10).pow(155).subtract(BigDecimal.ONE); 

    BigDecimal lowerLimit = BigDecimal.ONE; 
    BigDecimal upperLimit = new BigDecimal("1000"); 

    BigDecimal prime = lowerLimit; 
    int i = 1; 

    /* http://www.merriampark.com/bigsqrt.htm */ 
    BigSquareRoot bsr = new BigSquareRoot(); 
    upperLimit = upperLimit.add(BigDecimal.ONE); 
    while (prime.compareTo(upperLimit) == -1) { 

     bsr.setScale(0); 
     BigDecimal roundedSqrt = bsr.get(prime); 

     boolean isPrimeNumber = false; 
     BigDecimal upper = roundedSqrt; 
     while (upper.compareTo(BigDecimal.ONE) == 1) { 

     BigDecimal div = prime.remainder(upper); 
     if ((prime.compareTo(upper) != 0) && (div.compareTo(BigDecimal.ZERO) == 0)) { 
      isPrimeNumber = false; 
      break; 
     } else if (!isPrimeNumber) { 
      isPrimeNumber = true; 
     } 

     upper = upper.subtract(BigDecimal.ONE); 
     } 

     if (isPrimeNumber) { 
     System.out.println("\n" + i + " -> " + prime + " is a prime!"); 
     i++; 
     } else { 
     System.out.print("."); 
     } 
     prime = prime.add(BigDecimal.ONE); 
    } 
    } 

} 
 

Answer 8

Deje que ABCDE sea el número de cinco dígitos en base diez, lo que está considerando. Basado en Dirichlet's theorem on arithmetic progressions, si ABCDE y 100000 son coprime, entonces hay infinitos números primos de la forma 100000 * k + ABCDE. Ya que busca números primos, ni 2 ni 5 dividirían ABCDE de todos modos, por lo tanto, ABCDE y 100000 son coprime. Entonces hay infinitamente muchos números primos del formulario que está considerando.