Miller Rabin primality test

func miller_rabin(n, k=10) {

    return false if (n <= 1)
    return true  if (n == 2)
    return false if (n.is_even)

    var t = n-1
    var s = t.valuation(2)
    var d = t>>s

    k.times {
        var a = irand(2, t)
        var x = powmod(a, d, n)
        next if (x ~~ [1, t])

        (s-1).times {
            x.powmod!(2, n)
            return false if (x == 1)
            break if (x == t)
        }

        return false if (x != t)
    }

    return true
}

say miller_rabin.grep(^1000).join(', ')

Last updated