Jump to content

Miller–Rabin primality test: Difference between revisions

Miller–Rabin primality test (view source)

Revision as of 14:28, 15 August 2021

145 bytes removed ,  2 years ago
This is far accurate version in comparison to previous code, prev code were classifying prime as composite.
(This is far accurate version in comparison to previous code, prev code were classifying prime as composite.)
Line 2,788:
For the return values of this function, <code>true</code> means "probably prime" and <code>false</code> means "definitely composite."
 
<lang JavaScript>function probablyPrime(n, k) {
if (n === 2 || n === 3) return true
if (n % 2 === 0 || n < 2) return false▼
return true;▼
▲ if (n % 2 === 0 || n < 2)
return false;
 
// Write (n - 1) as 2^s * d
var s = 0, d = n - 1;
while (d % 2 d === 0)n - {1
while ((d & 1) == 0) {
d /= 2;
d >>= 1
++s;
++s
}
}
 
let base = 2
WitnessLoop: do {
var x = Math.pow(base, d) % n
// A base between 2 and n - 2
var x = Math.pow(2 + Math.floor(Math.random() * (n - 3)), d) % n;
 
if (x === 1 || x === n - 1) return true
continue;
 
for (var i = s - 1; i-- <= s; i++) {
x = (x * x) % n;
if (x === 1)
return false;
if (x === n - 1)
continue WitnessLoop;
}
 
if (x === n - 1) return false;true
}
} while (--k);
▲ return true;false
 
return true;
}</lang>
 
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/108050"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information