Jump to content

Miller–Rabin primality test: Difference between revisions

Miller–Rabin primality test (view source)

Revision as of 00:46, 12 November 2014

124 bytes removed ,  9 years ago
Added a much more readable, simpler and faster algorithm.
(Added a much more readable, simpler and faster algorithm.)
Line 1,451:
 
=={{header|JavaScript}}==
For the return values of this function, <code>true</code> means "probably prime" and <code>false</code> means "definitely composite."
This covers (almost) all integers in JavaScript (~2^53).
 
<lang JavaScript>function modProdprobablyPrime(an,b,n k) {
if (bn ===0) return2 0;|| n === 3)
if(b==1) return a%ntrue;
if (n % 2 === 0 || n < 2)
return (modProd(a,(b-b%10)/10,n)*10+(b%10)*a)%n;
if(t) return false;▼
}▼
function modPow(a,b,n){
if(b==0) return 1;
if(b==1) return a%n;
if(b%2==0){
var c=modPow(a,b/2,n);
return modProd(c,c,n);
}
return modProd(a,modPow(a,b-1,n),n);
}
function isPrime(n){
if(n==2||n==3||n==5) return true;
if(n%2==0||n%3==0||n%5==0) return false;
if(n<25) return true;▼
for(var a=[2,3,5,7,11,13,17,19],b=n-1,d,t,i,x;b%2==0;b/=2);
for(i=0;i<a.length;i++){
x=modPow(a[i],b,n);
if(x==1||x==n-1) continue;
for(t=true,d=b;t&&d<n-1;d*=2){
x=modProd(x,x,n); if(x==n-1) t=false;
}
▲ if(t) return false;
}
return true;▼
}
 
// Write (n - 1) as 2^s * d
for(var i=1;i<=1000;i++) if(isPrime(i)) console.log(i);</lang>
var s = 0, d = n - 1;
while (d % 2 === 0) {
d /= 2;
++s;
▲ }
 
WitnessLoop: do {
// 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)
continue;
 
for (var i = s - 1; i--;) {
x = x * x % n;
if (x === 1)
return false;
if (x === n - 1)
continue WitnessLoop;
}
 
▲ return truefalse;
} while (--k);
 
▲ if(n<25) return true;
}</lang>
 
=={{header|Julia}}==
Anonymous user
Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/107880"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information