Miller–Rabin primality test: Difference between revisions
Content deleted Content added
Pari/GP |
|||
| Line 557: | Line 557: | ||
=={{header|J}}== |
=={{header|J}}== |
||
See [[j:Essays/Primality%20Tests#Miller-Rabin|Primality Tests essay on the J wiki]]. |
See [[j:Essays/Primality%20Tests#Miller-Rabin|Primality Tests essay on the J wiki]]. |
||
=={{header|PARI/GP}}== |
|||
<lang>sprp(n,b)={ |
|||
my(d = n, s = 0); |
|||
until(bitand(d,1), d >>= 1; s++); |
|||
d = Mod(b, n)^d; |
|||
if (d == 1, return(1)); |
|||
for(i=1,s-1, |
|||
if (d == -1, return(1)); |
|||
d = d^2; |
|||
); |
|||
d == -1 |
|||
}; |
|||
MR(n,k)={ |
|||
for(i=1,k, |
|||
if(!sprp(n,random(n-2)+2), return(0)) |
|||
); |
|||
1 |
|||
};</lang> |
|||
=={{header|Perl}}== |
=={{header|Perl}}== |
||