-2
爲了讓三種不同的算法在相同的代碼中工作，我使用JavaScript進行工作，我爲每種算法設置了一個函數。我試圖得到三個Primality測試方法：試驗分部，費馬原始性測試和米勒拉賓原始性測試。前兩個工作正常，但米勒拉賓不是。我對JavaScript和編程一般都很陌生，所以如果你能找到我出錯的地方或想辦法讓它工作，請告訴我！謝謝！JavaScript上的Miller Rabin Primality測試錯誤
// 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>這就是我寫的了，這是純粹從我每次測試原來的數學算法產生的。發生的情況是，當輸入數字爲素數時，米勒拉賓輸出不顯示任何內容;該算法無法識別它。但它確實可以識別複合材料。
請讓我知道你想到的任何改進！
你做了什麼調試？錯誤來自哪裏？ – Carcigenicate
當輸入數字爲素數時，Miller-Rabin「輸出」將不顯示任何內容，但可正確識別合成物。 –
你應該修復你的縮進。您可能在某個分支中錯過了return語句。儘管事物縮進不正確，但很難說清楚。 – Carcigenicate