为Miller-Rabin测试创建一个随机的BigInt

Question

我正在使用JavaScript bigint实现Miller Rabin素数测试。

基本算法没有问题-我已经完成了，但它需要一个范围在0到(被测试的数字-3)之间的随机数。我不能使用Math.random()和缩放，因为我使用的是BigInt。

这并不需要加密安全，只要足够随机，所以我选择生成一个随机选择的十六进制数字字符串，并将其转换为BigInt。

代码如下:

function getRandomBigint(lower, upper) {
// Convert to hex strings so that we know how many digits to generate
let hexDigits = new Array(upper.toString(16).length).fill('');
let rand;
let newDigits;
do {
// Fill the array with random hex digits and convert to a BigInt
newDigits = hexDigits.map(()=>Math.floor(Math.random()*16).toString(16));
rand = BigInt('0x'+newDigits.join(''));
} while (rand < lower || rand > upper);
return rand;
}

这里的问题是生成的数字可能超出范围。这个函数通过迭代直到得到一个在范围内的数字来(糟糕地)处理这个问题。显然，这可能需要很长时间。在实践中，它在提供一个数字之前从未迭代超过几十次，但随机性的本质意味着问题是"存在的"，等着咬我!

我可以缩放或截断结果以使其在范围内，而不是迭代，但我担心这会影响随机性。我已经有一些证据表明，这不是随机的，但这在这个应用程序中可能无关紧要。

那么，两个问题:

• 这对米勒·拉宾来说足够随机了吗?
• 如何处理结果超出范围?

这是一个仅使用javascript的项目-请不要使用库。

Answer 1

Miller Rabin检验是一个概率¹检验。也就是说，确定一个数字是而不是是确定性的。一个素数指示仅仅是一个数字可能的指示。是'

原因是在测试中使用的某些基数可能导致素数指示，即使目标数不是素数。在测试中使用随机数作为基数，允许每次使用不同的基数重复运行测试，从而增加结果正确指示素数或非素数²的概率。

因此，选择的随机数必须刚好小于被测试的数。不需要从完整的范围中选择它们。

考虑到这一点，我现在有了这个:

function getRandomBigInt(upper) {
let maxInt = BigInt(Number.MAX_SAFE_INTEGER);
if (upper <= maxInt) {
return BigInt((Math.floor(Math.random()*Number(upper))));
} else {
return BigInt((Math.floor(Math.random()*Number.MAX_SAFE_INTEGER)));
}
}

9007199254740991 (Number.MAX_SAFE_INTEGER)应为此目的提供足够大的数字范围。到目前为止，根据我的测试，它可以与我的Miller-Rabin实现一起工作。

¹对短的特定碱基列表测试3,317,044,064,679,887,385,961,981的数字将产生确定的素数/非素数结果。

²对于非确定性素数结果，仍然需要进行确定性检验(如试除法)来确认。

Answer 2

获取范围内随机数的一种方法是

lower + rand() % (upper - lower)

rand()是返回大于(upper - lower)的随机数的任何函数。数学运算可以用Integer或Bigint来完成。

function rand16() {
// 0 .. 2^16-1
return BigInt(Math.floor(Math.random()*65536));
}
function rand() {
// -2^63 .. 2^63-1
return BigInt( (((rand16() * 65536) + rand16())* 65536 + rand16()) * 65536 + rand16() );
}