Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
mathoverflow.net/questions/115560/… –  user51427 Dec 6 '12 at 19:01
1  
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 6 '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 6 '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 6 '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. –  Henning Makholm Dec 6 '12 at 19:15

1 Answer 1

up vote 6 down vote accepted

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$.

share|improve this answer
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 6 '12 at 19:11
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. –  Henning Makholm Dec 6 '12 at 19:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.