(brent-factor) ( n -- factor )

Vocabulary

math.primes.pollard-rho-brent

Inputs

n

an object

Outputs

factor

an object

Definition

USING: kernel math math.order random ranges ;

IN: math.primes.pollard-rho-brent

:: (brent-factor) ( n -- factor )
    n [1..b) random n [1..b) random n [1..b) random
    :> ( y! c m ) 1 1 1 :> ( g! r! q! ) 0 :> x! 0 :> ys!
    [ g 1 = ] [
        y x! r [ y sq n mod c + n mod y! ] times 0 :> k!
        [ k r < g 1 = and ] [
            y ys! m r k - min
            [ y sq n mod c + n mod y! x y - abs q * n mod q! ]
            times q n gcd nip g! k m + k!
        ] while r 2 * r!
    ] while g n = [
        [ g 1 > not ]
        [ ys sq n mod c + n mod ys! x ys - abs n gcd nip g! ]
        while
    ] when g ;