Rabin-Miller Primality Test

rabinmiller.go

func BitsN(n int64) []int64 {
    var bits []int64
    bits = make([]int64, 0)
    for {
        if n == 0 {
            return bits
        }

        bits = append(bits, n % 2)
        n >>= 1
    }
}

func MRCompWit(a int64, n int64) bool {
    var rem int64 = 1
    bits := BitsN(n-1)
    for i := len(bits)-1; i >= 0; i-- {
        b := bits[i]
        x := rem
        rem = (rem * rem) % n


        if rem == 1 && x != 1 && x != (n-1) {
            return true
        }

        if b == 1 {
            rem = (rem * a) % n
        }
    }

    if rem != 1 {
        return true
    }
    return false
}

func IsPrimeMR(n int64, trials int) bool {
    if n < 2 {
        return false
    }

    for i := 0; i < trials; i++ {
        if MRCompWit(rand.Int63n(n-1) + 1, n) {
            return false
        }
    }
    return true
}