math.primes.pollard-rho-brent: Add vocab for finding factors

needs to give up after some number of iterations and needs
integration with the `factors` word

can be optimized

Related to #2401

diff --git a/basis/math/primes/pollard-rho-brent/authors.txt b/basis/math/primes/pollard-rho-brent/authors.txt
new file mode 100644 (file)
index 0000000..7c1b2f2
--- /dev/null
+++ b/basis/math/primes/pollard-rho-brent/authors.txt
@@ -0,0 +1 @@
+Doug Coleman

diff --git a/basis/math/primes/pollard-rho-brent/pollard-rho-brent-tests.factor b/basis/math/primes/pollard-rho-brent/pollard-rho-brent-tests.factor
new file mode 100644 (file)
index 0000000..7f21955
--- /dev/null
+++ b/basis/math/primes/pollard-rho-brent/pollard-rho-brent-tests.factor
@@ -0,0 +1,8 @@
+! Copyright (C) 2021 Doug Coleman.
+! See http://factorcode.org/license.txt for BSD license.
+USING: math.primes.pollard-rho-brent sorting tools.test ;
+IN: math.primes.pollard-rho-brent.tests
+
+{ { 2 2 2507191691 1231026625769 } } [ 12345678910111213141516 brent-factors natural-sort ] unit-test
+{ { 2 2 2 2 3 257 7221391 696389341 } } [ 62036506940903331216 brent-factors natural-sort ] unit-test
+{ { 13 4253 15823 32472893749823741 } } [ 28408516453955558205925627 brent-factors natural-sort ] unit-test

diff --git a/basis/math/primes/pollard-rho-brent/pollard-rho-brent.factor b/basis/math/primes/pollard-rho-brent/pollard-rho-brent.factor
new file mode 100644 (file)
index 0000000..90f3f96
--- /dev/null
+++ b/basis/math/primes/pollard-rho-brent/pollard-rho-brent.factor
@@ -0,0 +1,68 @@
+! Copyright (C) 2021 Doug Coleman.
+! See http://factorcode.org/license.txt for BSD license.
+USING: kernel make math math.order math.primes math.ranges
+random ;
+IN: math.primes.pollard-rho-brent
+
+! https://comeoncodeon.wordpress.com/2010/09/18/pollard-rho-brent-integer-factorization/
+:: (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!
+        ] do while
+    ] when
+    g ;
+
+: brent-factor ( n -- factor )
+    dup even? [ drop 2 ] [ (brent-factor) ] if ;
+
+DEFER: brent-factors
+
+! 1) brent-factor can return a composite number
+! 2) also it can hang if you give it a prime number
+! 3) factors can be found in random order
+! therefore we check these conditions
+:: (brent-factors) ( n! -- )
+    n brent-factor :> factor
+    ! 1) check for prime
+    factor prime? [
+        factor ,
+    ] [
+        factor brent-factors %
+    ] if
+    n factor = [
+        n factor /i
+        ! 2) check for prime
+        dup prime? [ , ] [ (brent-factors) ] if
+    ] unless ;
+
+: brent-factors ( n! -- factors )
+    dup 1 <= [
+        drop { }
+    ] [
+        [ (brent-factors) ] { } make
+    ] if ;