Lan*_*ard 1 javascript algorithm primes bigint
tl;dr如何获得一个非常大的 80 位 BigInt精确素数，而不是“可能的”素数？看来我找到并附在下面的代码只给你一个“可能的”素数。现在的问题是如何确定它是否是“精确”素数（即不是可能的，而是实际的）？
\n我被引导到这个 BigInt“随机值之间”代码，用于生成最小值和最大值之间的随机 BigInt，以及这个 BigInt 素数测试代码，我将其粘贴在下面。然后，我添加了一个简单的while循环来生成一定大小的 bigint，并检查素数（在我的例子中，素数也是p \xe2\x89\xa1 3 mod 4 ( prime % 4 === 3)：
let i = 0n\n\nwhile (i < 1000000000n) {\n let n = randomBigIntBetween(\n 1000000000100000000010000000001000000000100000000010000000001000000000n,\n 10000000001000000000100000000010000000001000000000100000000010000000001000000000n\n )\n if (isPrime(n) && n % 4n === 3n) {\n console.log(String(n))\n }\n\n i++\n}\n\nfunction randomBigIntBetween(minInclusive, maxExclusive) {\n var maxInclusive = (maxExclusive - minInclusive) - BigInt(1)\n var x = BigInt(1)\n var y = BigInt(0)\n while(true) {\n x = x * BigInt(2)\n var randomBit = BigInt(Math.random()<0.5 ? 1 : 0)\n y = y * BigInt(2) + randomBit\n if(x > maxInclusive) {\n if (y <= maxInclusive) { return y + minInclusive }\n // Rejection\n x = x - maxInclusive - BigInt(1)\n y = y - maxInclusive - BigInt(1)\n }\n }\n}\n\n// Javascript program Miller-Rabin primality test\n// based on JavaScript code found at https://www.geeksforgeeks.org/primality-test-set-3-miller-rabin/\n\n// Utility function to do\n// modular exponentiation.\n// It returns (x^y) % p\nfunction power(x, y, p)\n{\n\n // Initialize result\n // (JML- all literal integers converted to use n suffix denoting BigInt)\n let res = 1n;\n\n // Update x if it is more than or\n // equal to p\n x = x % p;\n while (y > 0n)\n {\n\n // If y is odd, multiply\n // x with result\n if (y & 1n)\n res = (res*x) % p;\n\n // y must be even now\n y = y/2n; // (JML- original code used a shift operator, but division is clearer)\n x = (x*x) % p;\n }\n return res;\n}\n\n\n// This function is called\n// for all k trials. It returns\n// false if n is composite and\n// returns false if n is\n// probably prime. d is an odd\n// number such that d*2<sup>r</sup> = n-1\n// for some r >= 1\nfunction millerTest(d, n)\n{\n // (JML- all literal integers converted to use n suffix denoting BigInt)\n\n // Pick a random number in [2..n-2]\n // Corner cases make sure that n > 4\n /*\n JML- I can\'t mix the Number returned by Math.random with\n operations involving BigInt. The workaround is to create a random integer\n with precision 6 and convert it to a BigInt.\n */\n const r = BigInt(Math.floor(Math.random() * 100_000))\n // JML- now I have to divide by the multiplier used above (BigInt version)\n const y = r*(n-2n)/100_000n\n let a = 2n + y % (n - 4n);\n\n // Compute a^d % n\n let x = power(a, d, n);\n\n if (x == 1n || x == n-1n)\n return true;\n\n // Keep squaring x while one\n // of the following doesn\'t\n // happen\n // (i) d does not reach n-1\n // (ii) (x^2) % n is not 1\n // (iii) (x^2) % n is not n-1\n while (d != n-1n)\n {\n x = (x * x) % n;\n d *= 2n;\n\n if (x == 1n)\n return false;\n if (x == n-1n)\n return true;\n }\n\n // Return composite\n return false;\n}\n\n// It returns false if n is\n// composite and returns true if n\n// is probably prime. k is an\n// input parameter that determines\n// accuracy level. Higher value of\n// k indicates more accuracy.\nfunction isPrime( n, k=40)\n{\n // (JML- all literal integers converted to use n suffix denoting BigInt)\n // Corner cases\n if (n <= 1n || n == 4n) return false;\n if (n <= 3n) return true;\n\n // Find r such that n =\n // 2^d * r + 1 for some r >= 1\n let d = n - 1n;\n while (d % 2n == 0n)\n d /= 2n;\n\n // Iterate given nber of \'k\' times\n for (let i = 0; i < k; i++)\n if (!millerTest(d, n))\n return false;\n\n return true;\n}到目前为止，它为我打印了一些范围内的素数，或者我认为应该是素数，对吗？我对所涉及的数学或素数的“米勒测试”了解不够，无法知道该算法是否确实找到了精确的素数，或者是否找到了可能是素数的东西。
\n相应博客文章的作者开头说：
\n\n\n米勒-拉宾素性测试是对素数的可靠测试，尽管它只能确定数字是素数的概率。
\n
（已添加重音）
\n据我所知，这个算法似乎只能帮助我们实现部分目标？我们必须做什么才能建立一个保证是素数的列表？假设我们想要非常大的 BigInt 素数......
\n实际上，对于我当前的用例，我需要查找 70 到 80 位之间的素数，但我想知道如何查找任意大小的数字（最多 65536 位）的素数（如果可能）。
\n我认为，知道“素数恰好有两个因子 \xe2\x80\x94 1 和数字本身”，意味着我们需要以某种方式找到 BigInt 的因子。这引导我来到这里，也引导我到这个函数：
\nfunction primeFactors(n){\n const factors = []\n\n let divisor = 2n\n let i = 0\n\n while (n > 2n) {\n if (n % divisor == 0n) {\n factors.push(divisor)\n n = n / divisor\n } else{\n divisor++\n }\n\n i++\n\n if (i % 100 === 0) {\n console.log(i)\n }\n }\n\n console.log(i)\n\n return factors\n}\n然后我将它添加到我原来的 while 循环中：
\nwhile (true) {\n let n = rbigint(\n 1000000000100000000010000000001000000000100000000010000000001000000000n,\n 10000000001000000000100000000010000000001000000000100000000010000000001000000000n\n )\n if (isPrime(n) && n % 4n === 3n) {\n const factors = primeFactors(n)\n console.log(factors)\n console.log(String(n))\n }\n}\n正如您所看到的，我还添加了这些console.log语句，以便调试正在进行的迭代次数，因为调用primeFactor挂起。几秒钟后，我取消了记录22481400迭代的过程，但似乎尚未接近完成，我不确定需要多长时间。尝试只记录每 1000 万次迭代，但它只是嘎嘎地走，永远不会完成。我在迭代后取消了计算第一个正确300000000数字的因子。isPrime(n) && n % 4n === 3n看来我们至少需要 300000000300000000300000000300000000300000000300000000 或一些疯狂的迭代次数才能完成因式分解......我不知道如何计算这部分，但想知道如何获得素数。
所以问题是，当针对这些极大的值时，如何在 JavaScript 中获得“精确BigInt”素数，而不是“可能”素数？
您不需要检查该数字是否恰好是素数。例如，由于恒星辐射，您的计算机中的某个位可能会发生翻转。这种情况不太可能发生，但只要比 Rabin-Miller 测试标记非素数的可能性更大，因为素数低于你应该可以的。
因此，硬件故障比该数字不是素数的可能性更大，您不能从素数测试中要求更多。