| 123456789101112131415161718192021222324252627282930313233 |
- #!/usr/bin/ruby
- # Pollard's rho integer factorization algorithm.
- # See also:
- # https://facthacks.cr.yp.to/rho.html
- # https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
- func rho_factor(n, tries = 50000) {
- func f(x) { # can be any polynomial
- powmod(x, 2, n) + 1
- }
- var x = f(1)
- var y = f(x)
- tries.times {
- x = f(x)
- y = f(f(y))
- is_coprime(n, x-y) || break
- }
- return gcd(x-y, n)
- }
- say rho_factor(503*863) #=> 863
- say rho_factor(33670570905491953) #=> 36169843
- say rho_factor(314159265358979323) #=> 317213509
- say rho_factor(242363923520394591022973) #=> 786757556719
|
