Miller–Rabin primality test: Difference between revisions
Content added Content deleted
m (→{{header|REXX}}: added DO-end labels, removed superflous blank lines (before suboutines), changed section header comments, added whitespade in multi-line statements.. -- ~~~~) |
(→{{header|Go}}: added deterministic test) |
||
Line 1,000:
=={{header|Go}}==
;Library
Go has it in
;Deterministic
Below is a deterministic test for 32 bit unsigned integers. Intermediate results in the code below include a 64 bit result from multiplying two 32 bit numbers. Since 64 bits is the largest fixed integer type in Go, a 32 bit number is the largest that is convenient to test.
The main difference between this algorithm and the pseudocode in the task description is that k numbers are not chosen randomly, but instead are the three numbers 2, 7, and 61. These numbers provide a deterministic primality test up to 2^32.
<lang go>package main
import "log"
func main() {
// max uint32 is not prime
c := uint32(1<<32 - 1)
// a few primes near the top of the range. source: prime pages.
for _, p := range []uint32{1<<32 - 5, 1<<32 - 17, 1<<32 - 65, 1<<32 - 99} {
for ; c > p; c-- {
if prime(c) {
log.Fatalf("prime(%d) returned true", c)
}
}
if !prime(p) {
log.Fatalf("prime(%d) returned false", p)
}
c--
}
}
func prime(n uint32) bool {
// bases of 2, 7, 61 are sufficient to cover 2^32
switch n {
case 0, 1:
return false
case 2, 7, 61:
return true
}
// compute s, d where 2^s * d = n-1
nm1 := n - 1
d := nm1
s := 0
for d&1 == 0 {
d >>= 1
s++
}
n64 := uint64(n)
for _, a := range []uint32{2, 7, 61} {
// compute x := a^d % n
x := uint64(1)
p := uint64(a)
for dr := d; dr > 0; dr >>= 1 {
if dr&1 != 0 {
x = x * p % n64
}
p = p * p % n64
}
if x == 1 || uint32(x) == nm1 {
continue
}
for r := 1; ; r++ {
if r >= s {
return false
}
x = x * x % n64
if x == 1 {
return false
}
if uint32(x) == nm1 {
break
}
}
}
return true
}</lang>
=={{header|Haskell}}==
| |||