1234567891011121314151617181920212223242526272829303132333435363738394041 |
- #!/usr/bin/ruby
- # Pollard-Strassen O(n^(1/4)) factorization algorithm.
- # Illustrated by David Harvey in the following video:
- # https://yewtu.be/watch?v=_53s-0ZLxbQ
- func pollard_strassen_factorization(n, d = min(200, 1+n.ilog2), tries = min(1000, 10*d)) {
- # In the original algorithm, d = ceil(n^(1/4))
- # d = 1+n.iroot(4)
- # However, the polynomial evaluation is very slow when d is too large.
- var a = random_prime(n)
- var baby_steps = @(1..d).map_reduce {|b|
- mulmod(b, a, n)
- }
- var x = PolyMod(1, n)
- var f = baby_steps.map {|k| (x-k) }.binsplit {|a,b| a * b }
- for k in (2 .. tries) {
- var b = powmod(a, k*d, n)
- var g = gcd(f(b), n)
- if (g.is_between(2, n-1)) {
- return g
- }
- }
- return 1
- }
- say pollard_strassen_factorization(43*97)
- say pollard_strassen_factorization(503*863)
- say pollard_strassen_factorization(2**32 + 1)
- say pollard_strassen_factorization(2**64 + 1)
|