1 ! Copyright (C) 2021 Doug Coleman.
2 ! See http://factorcode.org/license.txt for BSD license.
3 USING: arrays kernel make math math.order math.primes
4 ranges random sorting ;
5 IN: math.primes.pollard-rho-brent
7 ! https://comeoncodeon.wordpress.com/2010/09/18/pollard-rho-brent-integer-factorization/
8 :: (brent-factor) ( n -- factor )
11 n [1..b) random :> ( y! c m )
18 y sq n mod c + n mod y!
24 y sq n mod c + n mod y!
25 x y - abs q * n mod q!
34 ys sq n mod c + n mod ys!
35 x ys - abs n gcd nip g!
40 : brent-factor ( n -- factor )
41 dup even? [ drop 2 ] [ (brent-factor) ] if ;
43 DEFER: pollard-rho-brent-factors
45 ! 0) can hang if given a large prime, so check prime? first
46 ! 1) brent-factor can return a composite number
47 ! 2) also it can hang if you give it a prime number
48 ! 3) factors can be found in random order
49 ! therefore we check these conditions
50 :: (pollard-rho-brent-factors) ( n! -- )
51 n brent-factor :> factor
56 factor pollard-rho-brent-factors %
61 dup prime? [ , ] [ (pollard-rho-brent-factors) ] if
64 : pollard-rho-brent-factors ( n! -- factors )
71 [ (pollard-rho-brent-factors) ] { } make