java - 有效地生成一个范围内的一个随机素数

Question

我只需要获取 [2, n^2] 范围内的一个随机素数，其中 n 可以非常大(10^9 到 10^32)。我知道那些作业问题“如何打印给定范围内的素数”，“埃拉托斯特尼筛子”等。

如果可能的话，我希望避免计算所有素数并随机选择一个。

我也不确定从范围中选择随机数并检查素数是否是解决此问题的优雅/有效的方法。

这与安全目的无关。它只是算法实现(尝试实现)的一部分，该算法检查两个非常大的文件(> 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

使用BigInteger ，及其 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)。