我只需要在 [2, n^2] 范围内获得一个随机素数，其中 n 可以非常大（10^9 到 10^32）。我知道那些作业问题“如何在给定范围内打印素数”、“Eratosthene 筛”等。
如果可能，我想避免计算所有质数并随机选择一个。
我也不确定从范围中选择一个随机数并检查素数是否是解决这个问题的一种优雅/有效的方法。
这与安全目的无关。它只是算法实现（尝试实现）的一部分，它检查两个非常大的文件（> 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;
}
}
如果 yMp != xMp 与 100% 置信度文件不同，则算法无法识别出它们不同的可能性很小。
在 x 处找到素数的概率是 1/ln(x)。在您的情况下，这是 n²，n=10^32。所以可能性是 ln(10^64) 或大约 1/150。这意味着您必须平均测试大约 150 个数字，直到找到素数。
我没有可用的 Java，但我可以根据PSW primality test为您提供 Python 的结果。积分去@primo从Codegolf，尤其是这个答案。
start = time()
n = next_prime((10**32)**2)
end = time()
print (n, " calcualted in ", end-start)
10000000000000000000000000000000000000000000000000000000000000057 calcualted in 0.00302 sec
所以是的，同时以一种有效的方式是可能的。
Wolfram Alpha证实了这一结果。
本文收集自互联网，转载请注明来源。
如有侵权，请联系 [email protected] 删除。
我来说两句