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?
Generating a large prime, $p$, such that $2^{k}$ divides $p-1$ for some k
4
$\begingroup$
prime-numbers
-
0yes, that's exactly what's happening. Doing it the way you suggested is the most efficient. – 2012-12-06
1 Answers
6
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$.
-
1@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. – 2012-12-06