 ! Copyright (C) 2008 Doug Coleman.
 ! See http://factorcode.org/license.txt for BSD license.
 USING: combinators kernel locals math math.functions math.ranges
-random sequences sets combinators.short-circuit ;
+random sequences sets combinators.short-circuit math.bitwise ;
 IN: math.miller-rabin
 
 <PRIVATE

    1 + 6 divisor? ;

: next-safe-prime-candidate ( n -- candidate )
    1 - 2/
    next-prime dup safe-prime-candidate?
    [ next-safe-prime-candidate ] unless ;


    n 1 - :> n-1
    n-1 factor-2s :> s :> r
    0 :> a!
    trials [
        drop
        n 1 - [1,b] random a!
        a s n ^mod 1 = [
            f
        ] [
            r iota [
                2^ s * a swap n ^mod n - -1 =
            ] any? not 
        ] if
    ] any? not ;

PRIVATE>

