高效地生成一个范围内的随机素数

Question

我只需要在 [2, n^2] 范围内获得一个随机素数，其中 n 可以很大（10^9 到 10^32）。我知道那些作业题"how to print prime numbers in a given range"、"Eratosthene's sieve"等等

如果可能的话，我想避免计算所有质数，并且 select 随机计算一个。

我也不确定从范围中选择一个随机数并检查素数是否是解决此问题的 elegant/efficent 方法。

这与安全目的无关。它只是算法实现（尝试实现）的一部分，它检查两个非常大的文件（> 1TB）是否相同。

关于如何获得一个绝对素数且注重性能的任何想法？

编辑我正在尝试做的事情的一个非常天真和简化的实现：

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

如果具有 100% 置信度的 yMp != xMp 文件不同，则算法无法识别它们不同的可能性很小。

Answer 1

在 x 处找到素数的概率是 1/ln(x)。在你的例子中，那是 n²，n=10^32。所以可能性是 ln(10^64) 或大约 1/150。这意味着您必须平均测试大约 150 个数字，直到找到素数。

我没有可用的 Java，但我可以根据 PSW primality test. Credits go to @primo from Codegolf, especially this answer.

为您提供 Python 的结果

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

10000000000000000000000000000000000000000000000000000000000000057 calcualted in  0.00302 sec

所以是的，同时以一种有效的方式是可能的。

结果被Wolfram Alpha确认。

Answer 2

使用`BigInteger`, and its `nextProbablePrime()`方法。

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

另一种方法是使用 BigInteger(int bitLength, int certainty, Random rnd) 构造函数，但它会找到恰好 bitLength 位的数字，这很不方便，因为它不会低于 n ^ (bitLength - 1) .

高效地生成一个范围内的随机素数

Efficently generate one random prime number in a range

java

performance

primes

使用`BigInteger`, and its `nextProbablePrime()`方法。

高效地生成一个范围内的随机素数

Efficently generate one random prime number in a range

java

performance

primes

使用BigInteger, and its nextProbablePrime()方法。

使用`BigInteger`, and its `nextProbablePrime()`方法。