JavaScript上的米勒·拉宾素性检验错误
JavaScript上的米勒·拉宾素性检验错误
提问于 2017-07-30 09:27:33
为了让三种不同的算法在相同的代码中工作，我在JavaScript上工作，我为每种算法设置了一个函数。我正在尝试三种素性测试方法:试验划分法、费马素性测试法和Miller-Rabin素性测试法。前两个都工作得很好，但米勒-拉宾并非如此。我对JavaScript和一般的编程都很陌生，所以如果你能找到我哪里出了错，或者能想出一个办法让它工作，请让我知道！谢谢!
// 1531 6389 68819 688889 6388819
// 68883889 688838831 1000000009
// 561 is a Carmichael number; a Fermat pseudoprime with the property a^n-1 = 1 mod n, for any "a" coprime to 561.
input = 5491763;
numTrials = 2000;
document.getElementById("input").innerHTML = input;
function TrialDiv(n) {
if (n === 1) {
return false;
} else if (n === 2) {
return true;
} else {
for (var x = 2; x < n; x++) {
if (n % x === 0) {
return false;
}
}
return true;
}
}
if ((TrialDiv(input)) === true) {
a = "Prime"
} else if ((TrialDiv(input)) === false) {
a = "Composite"
}
//---------------------------------------------------------------------------
function gcd(x, y) {
while (y !== 0) {
var z = x % y;
x = y;
y = z;
}
return x;
}
function getRndInteger(max) {
return Math.floor(Math.random() * (max - 2)) + 2;
}
//--------------------------------------------------------------------------
function Fermat(n) {
for (var t = 0; t = numTrials; t++) {
m = getRndInteger(input);
if (gcd(m, n) !== 1) {
return false;
}
}
return (Math.pow(m, n - 1) % n !== 1);
}
if ((Fermat(input)) === true) {
b = "Prime";
} else if ((Fermat(input)) === false) {
b = "Composite";
}
//---------------------------------------------------------------------------
function genD(n) { // Generates "d" such that "n-1 = 2^s * d"
var p = n - 1;
var d = p / 2;
while (d % 2 === 0) {
d = d / 2;
}
return d;
}
function genS() { // Generates "s" such that "n-1 = 2^s * d"
var s = Math.log2(p / d);
return s;
}
//---------------------------------------------------------------------------
function MillerRabin(n) {
for (var t = 0; t < numTrials; t++) {
m = getRndInteger(input);
if (gcd(m, n) !== 1) {
return false;
} else {
for (var r = 0; r < genS(); r++) {
power = (Math.pow(2, r) * genD(input));
if (Math.pow(m, genD(input)) % n === 1 || Math.pow(m, power) % n === -1) {
return true;
} else {
return false;
}
}
return true;
}
return true;
}
}
if ((MillerRabin(input)) === true) {
c = "Prime";
} else if ((MillerRabin(input)) === false) {
c = "Composite";
}<body>
<button type="button" onclick='document.getElementById("TrialDivision").innerHTML = a; document.getElementById("FermatTest").innerHTML = b; document.getElementById("MillerRabinTest").innerHTML = c; '>Show</button>
<hr>
<b style="color:rgb(0,0,120)">PRIMALITY TESTS</b>
<p></p>
Input:
<l id="input"></l>
<hr>
<h5 style="color:rgb(160,0,0)">TRIAL DIVISION</h5>
<p></p>
Output:
<i id="TrialDivision"></i>
<hr>
<h5 style="color:rgb(160,0,0)">FERMAT PRIMALITY TEST</h5>
<p></p>
Output:
<i id="FermatTest"></i>
<hr>
<h5 style="color:rgb(160,0,0)">MILLER-RABIN PRIMALITY TEST</h5>
<p></p>
Output:
<i id="MillerRabinTest"></i>
</body>
<script>
这就是我如何写出来的，这完全是我根据每个测试的原始数学算法创建的。发生的情况是，当输入数字是质数时，Miller-Rabin输出不会显示任何内容；算法无法识别它。但它确实正确地识别了复合体。
请让我知道你想到的任何改进！
回答 1
Stack Overflow用户
回答已采纳
发布于 2017-07-30 10:07:07
你有一些循环不能运行的问题。我不确定算法应该如何工作，所以我不知道它是否工作，但直接的问题是由泄漏变量和未在函数中声明的变量引起的(这使它们成为全局的)。
这个迫在眉睫的问题的解决办法是在函数中声明局部变量，这样您就不需要依赖其他函数来设置它们。
function genD(n) { // Generates "d" such that "n-1 = 2^s * d"
var p = n - 1;
var d = p / 2;
while (d % 2 === 0) {
d = d / 2;
}
return d;
}
function genS(n) { // Generates "s" such that "n-1 = 2^s * d"
var p = n - 1
var d = p / 2
var s = Math.log2(p / d);
return s;
}一旦你开始修复崩溃的错误，还有一些其他的大问题。例如，您的fermat()可能会永远运行：
for (var t = 0; t = numTrials; t++) {应该是：
for (var t = 0; t == numTrials; t++) {=为每个循环将t设置为numTrails
我认为你应该从一开始就开始，把你所有的函数放在一起，把所有其他调用这些函数的逻辑代码放在一起，这样你就可以看到发生了什么。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/45395530
复制相关文章
相似问题
腾讯云开发者
Copyright © 2013 - 2026 Tencent Cloud. All Rights Reserved. 腾讯云 版权所有
深圳市腾讯计算机系统有限公司 ICP备案/许可证号：粤B2-20090059 
粤公网安备44030502008569号
腾讯云计算（北京）有限责任公司 京ICP证150476号 | 京ICP备11018762号