JavaScript实现Miller-Rabin测试时如何生成符合要求的随机BigInt

关于现有方案随机性是否满足Miller Rabin测试需求 #

你的现有拒绝采样方案本身不会破坏随机性：只要Math.random()生成的单十六进制位是均匀的，循环重试得到的结果就是均匀分布在指定上下限区间内的，完全可以满足Miller Rabin素性测试的需求。你观察到的随机性不达预期的问题，大概率和Math.random()本身的实现精度有关（部分运行环境的Math.random()只有32位精度，生成超过32位的大数时高位重复率会偏高），但对于非密码学安全要求的Miller Rabin测试来说，这种级别的偏差几乎不会影响测试结果的正确性。

关于更高效的区间随机BigInt生成方案 #

你可以通过限制随机数的生成上限为大于区间长度的最小2的幂次，把单次重试的概率控制在50%以内，平均仅需2次循环就能得到符合要求的结果，远优于现有直接生成和upper等长十六进制数的方案。同时可以去掉字符串拼接逻辑，直接用位运算生成BigInt，进一步提升运行效率。

优化后的代码示例：

function getRandomBigint(lower, upper) {
  lower = BigInt(lower);
  upper = BigInt(upper);
  if (lower > upper) throw new RangeError('lower must be less than or equal to upper');
  
  const range = upper - lower + 1n;
  // 计算区间长度对应的比特位数量
  let bits = 0;
  let temp = range - 1n;
  while (temp > 0n) {
    bits++;
    temp >>= 1n;
  }

  let rand;
  do {
    rand = 0n;
    // 每次生成4比特对应1个十六进制数，平衡实现复杂度和效率
    for (let i = 0; i < bits; i += 4) {
      rand = (rand << 4n) | BigInt(Math.floor(Math.random() * 16));
    }
    // 清除超出所需长度的高位
    rand &= (1n << BigInt(bits)) - 1n;
  } while (rand >= range);

  return lower + rand;
}

内容的提问来源于stack exchange，提问作者Tangentially Perpendicular