Generar una gran prima, $p$ tal que $2^{k}$ divide $p-1$ para algunos $k<p$

Question

Quiero generar una prima $p$ de cierto tamaño $2^{k}$ divide $p-1$ para algunos $k < p$ . ¿Hay algún truco que pueda utilizar para hacerlo en lugar de una búsqueda por fuerza bruta?

Answer 1

El siguiente programa Java encontró uno en una fracción de segundo:

import java.io.IOException;
import java.math.BigInteger;
import java.util.Random;

public class Primefinder {
  public static void main(String[] args) throws IOException {
    Random r = new Random();
    for( int i=0; i<1000; i++ ) {
        BigInteger bi = new BigInteger(320-32, r);
        bi = bi.shiftLeft(32);
        bi = bi.add(BigInteger.ONE);
        if( bi.isProbablePrime(100) ) {
            System.out.println("found in iteration "+i+": "+bi.toString(16));
            break ;
        }
    }
  }
}

Resultados de una ejecución:

found in iteration 143: 949f3fe33aa137d2f289064432e30d1f7533d306c2d277f873a6fc5969b0fdaec873455100000001

Y por si fuera poco, aquí están los de tamaño 80 y 160 (después de filtrar un par de intentos en los que los primeros bits eran 0):

found in iteration 20: d070dd4f6b9f00000001
found in iteration 29: a45583b3b54a5946026be213f0366a9200000001

---

Algunos ejemplos menos aleatorios, $13\times 2^{316}+1$ también es primo, al igual que $29\times 2^{75}+1$ y $315\times 2^{151}+1$ .