Anonymous user
Miller–Rabin primality test: Difference between revisions
→{{header|PARI/GP}}: split into subsections
m (→{{header|PARI/GP}}: make functions use the same interface) |
(→{{header|PARI/GP}}: split into subsections) |
||
Line 767:
=={{header|PARI/GP}}==
===Built-in
<lang parigp>MR(n,k)=ispseudoprime(n,k);</lang>
===Custom
<lang parigp>sprp(n,b)={
my(s = valuation(n-1, 2), d = Mod(b, n)^(n >> s));
Line 788:
};</lang>
===Deterministic version===
A basic deterministic test can be obtained by an appeal to the
<lang parigp>A006945=[9, 2047, 1373653, 25326001, 3215031751, 2152302898747, 3474749660383, 341550071728321, 341550071728321, 3825123056546413051];
Miller(n)={
if (n%2 == 0, return(n == 2)); \\ Handle even numbers
| |||