CODEWITHSUNDEEP
javaperformanceprimes
Eritrean
Eritrean

Reputation: 16498

Efficently generate one random prime number in a range

I need to get only one random prime number in the range [2, n^2] where n can be very big (10^9 to 10^32). I know those homework questions "how to print prime numbers in a given range", "Eratosthene's sieve" etc.

I want, if possible, to avoid computing all prime numbers and select one at random.

I am also not sure if picking a random number from the range and check for primality is a elegant/efficent way of solving this issue.

This has nothing to do with security purposes. It's just part of an algorithm implementation (a try to implement) which checks if two very big files (>1TB) are identical or not.

Any ideas how to get one definitely prime random number with focus on performance?

EDIT A very naive and simplified implementation of what i am trying to do:

import java.math.BigInteger;
import java.util.stream.Collectors;

public class NewClass1 {    

    public static void main(String[] args) {
        //imagine this is my content of first file which is not at the same place as file two
        String file1 = "RDNZL";        
        //convert the content to bits
        file1 = toBits(file1); // 0101001001000100010011100101101001001100  

        //convert bits to number
        BigInteger  x = new BigInteger (file1, 2); //353333303884

        long p = 1187;  // select a random number between 2 and 1600 (String length * 8 bits = 40)
        // send p and x % p to validiate,
        long xMp = x.mod(BigInteger.valueOf(p)).longValue(); 
        System.out.println(check(p, xMp));
    }
    public static String toBits(String file){
        //convert each char to 8 bits and concat to string
        //just for simplification, i'am going to find a better way to solve this
        return file.chars().boxed()
                .map(Integer::toBinaryString).map(e->String.format("%8s", e).replace(' ', '0'))
                .collect(Collectors.joining("")); 
    }
    public static boolean check(long p, long xMp){
        //the other file which is somewhere else, in the cloud etc. 
        String file2 = "RDNZL";        
        file2 = toBits(file2); 

        BigInteger  y = new BigInteger (file2, 2); 
        long yMp = y.mod(BigInteger.valueOf(p)).longValue();
        return yMp == xMp;
    }
}

If yMp != xMp with 100% confidence files differ, if not an infinitesimal chance that the algorithm doesn't recognize it that they differ.

Upvotes: 0

Views: 803

Answers (2)

Olivier Grégoire
Olivier Grégoire

Reputation: 35427

Use BigInteger, and its nextProbablePrime() method.

public static BigInteger randomPrime(int numBits) {
  BigInteger max = BigInteger.ONE.shiftLeft(numBits);
  BigInteger prime;
  do {
    BigInteger integer = new BigInteger(numBits, ThreadLocalRandom.current()); // Pick a random number between 0 and 2 ^ numbits - 1
    prime = integer.nextProbablePrime(); // Pick the next prime. Caution, it can exceed n^numbits, hence the loop
  } while(prime.compareTo(max) > 0);
  return prime;
}

An alternative would be to use the BigInteger​(int bitLength, int certainty, Random rnd) constructor, but it will find numbers with exactly bitLength bits, which is inconvenient because it doesn't go below n ^ (bitLength - 1).

Upvotes: 3

Thomas Weller
Thomas Weller

Reputation: 59302

The probability to find a prime number at x is 1/ln(x). In your case, that's n² with n=10^32. So the likelyness is ln(10^64) or roughly 1/150. This means that you have to test an average of about 150 numbers until you find a prime.

I don't have Java available, but I can give you a result from Python, based on the PSW primality test. Credits go to @primo from Codegolf, especially this answer.

start = time()
n = next_prime((10**32)**2)
end = time()
print (n, " calcualted in ", end-start)

10000000000000000000000000000000000000000000000000000000000000057 calcualted in  0.00302 sec

So yes, it is possible in an efficient way at the same time.

The result is confirmed by Wolfram Alpha.

Upvotes: 1

Related Questions