yaole
49 lines
850 B
Go
49 lines
850 B
Go
package gmath
|
|
|
|
import (
|
|
"crypto/rand"
|
|
"math/big"
|
|
|
|
"xdx.jelly/xgcl/grand"
|
|
)
|
|
|
|
const MRConst = 10
|
|
|
|
// IsPrimeMR tests if n is prime by the Miller-Rabin prime testing method.
|
|
func IsPrimeMR(n *big.Int) bool {
|
|
return n.ProbablyPrime(MRConst)
|
|
}
|
|
|
|
// MillerRabin tests if n is prime by the Miller-Rabin prime testing method.
|
|
func MillerRabin(n *big.Int) bool {
|
|
// n = 2^s * r
|
|
n1 := new(big.Int)
|
|
n1.Sub(n, BigInt1)
|
|
r := new(big.Int).Set(n1)
|
|
s := 0
|
|
for r.Bit(0) == 0 {
|
|
s++
|
|
r = r.Rsh(r, 1)
|
|
}
|
|
|
|
for i := 0; i < MRConst; i++ {
|
|
a, _ := rand.Int(grand.Reader, n1)
|
|
|
|
//a = a^r mod n
|
|
a.Exp(a, r, n)
|
|
if a.Cmp(BigInt1) != 0 && a.Cmp(n1) != 0 {
|
|
for j := 1; j < s && a.Cmp(n1) != 0; j++ {
|
|
a.Mul(a, a)
|
|
a.Mod(a, n)
|
|
if a.Cmp(BigInt1) == 0 {
|
|
return false
|
|
}
|
|
}
|
|
if a.Cmp(n1) != 0 {
|
|
return false
|
|
}
|
|
}
|
|
}
|
|
return true
|
|
}
|