An implementation of the Lucas-Lehmer primality test in go (with a few optimizations).
- For all Mersenne primes (of the form 2p-1) p has to be a prime number, so before doing the more costly Lucas-lehmer test we make sure p is prime.
- The modulus in the Lucas-Lehmer test is made a lot faster in the fastMod function which uses bitwise operators instead of division, moving the slowest part of the test to the multiplication of s*s.
- replace
import "math/big"withimport big "github.com/ncw/gmp"ends up 8+ times speedup. - log to file
- use the built-in
func (*Int) ProbablyPrime