Generating a large prime, $p$, such that $2^{k}$ divides $p-1$ for some $k

Question

I want to generate a prime $p$ of a certain size $2^{k}$ divides $p-1$ for some $k < p$. Is there any trick that I can use to do that instead of a brute-force search?

http://mathoverflow.net/questions/115560/primitive-nth-root-of-unity-in-a-finite-field-z-p — , Dec 06 '12 at 19:01
Not really! You need to use an efficient compositeness test, certainly must not check for compositeness by looking for divisors. A "probabilistic" test sounds good. — André Nicolas, Dec 06 '12 at 19:03
Start at a random $320-32$ bit number $n$, try the numbers $2^32 n+14 in sequence until you find a prime. Use an efficient primality test — Hagen von Eitzen, Dec 06 '12 at 19:08
Ok! My bruteforce search went in the other direction. It generated a primes of size $320$ and for every one of them it checked if $2^{32}$ divides $p-1$. That seems similar to what you suggest, but the performance of my procedure isn't great (it ran for 1 hour and didn't find any). I will use your trick. — Social IPhone, Dec 06 '12 at 19:12
@Social: No, if you just generate random primes you'd have to sift about a billion of them before one randomly ended with 31 zeroes and a one. — hmakholm left over Monica, Dec 06 '12 at 19:15
yes, that's exactly what's happening. Doing it the way you suggested is the most efficient. — Social IPhone, Dec 06 '12 at 19:18

hmakholm left over Monica · Accepted Answer · 2012-12-06T19:30:36.490

The following Java program found one in a fraction of a second:

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 ;
        }
    }
  }
}

Output from one run:

found in iteration 143: 949f3fe33aa137d2f289064432e30d1f7533d306c2d277f873a6fc5969b0fdaec873455100000001

And for good measure, here are ones of size 80 and 160 (after I filtered out a couple of tries where the first few bits happened to be 0s):

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

For some less random examples, $13\times 2^{316}+1$ is also prime, as are $29\times 2^{75}+1$ and $315\times 2^{151}+1$.

Note that about 0.45% of 320 bit numbers are prime and your test candidates are at least not divisible by 2 or 5, thus more than 1% of trials will succeed. — Hagen von Eitzen, Dec 06 '12 at 19:11
@Hagen: How do you know the candidates are not divisible by 5? Since $2^{32}$ is coprime with $5$ every fifth number of the required form will be a multiple of 5. — hmakholm left over Monica, Dec 06 '12 at 19:18

Generating a large prime, $p$, such that $2^{k}$ divides $p-1$ for some $k

1 Answers1