1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556575859606162636465666768697071727374757677787980818283848586878889909192 |
- #!/usr/bin/perl
- # Pollard's rho integer factorization algorithm.
- # This version uses the polynomial:
- # f(x) = x^e + 2*e - 1
- # where e = lcm(1..B), for a small bound B.
- # See also:
- # https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
- use 5.020;
- use strict;
- use warnings;
- use experimental qw(signatures);
- use Math::GMPz;
- use Math::Prime::Util::GMP qw(consecutive_integer_lcm logint);
- sub rho_exp_factor ($n, $max_iter = 5000) {
- my $B = logint($n, 5)**2;
- my $e = Math::GMPz::Rmpz_init_set_str(consecutive_integer_lcm($B), 10);
- my $c = 2*$e - 1;
- if (length("$n") <= 12) {
- $e = Math::GMPz->new(2);
- }
- my $x = Math::GMPz::Rmpz_init_set_ui(1);
- my $y = Math::GMPz::Rmpz_init();
- my $g = Math::GMPz::Rmpz_init();
- Math::GMPz::Rmpz_powm($x, $x, $e, $n);
- Math::GMPz::Rmpz_add($x, $x, $c);
- Math::GMPz::Rmpz_mod($x, $x, $n);
- Math::GMPz::Rmpz_powm($y, $x, $e, $n);
- Math::GMPz::Rmpz_add($y, $y, $c);
- Math::GMPz::Rmpz_mod($y, $y, $n);
- for (1 .. $max_iter) {
- Math::GMPz::Rmpz_powm($x, $x, $e, $n);
- Math::GMPz::Rmpz_add($x, $x, $c);
- Math::GMPz::Rmpz_mod($x, $x, $n);
- Math::GMPz::Rmpz_powm($y, $y, $e, $n);
- Math::GMPz::Rmpz_add($y, $y, $c);
- Math::GMPz::Rmpz_mod($y, $y, $n);
- Math::GMPz::Rmpz_powm($y, $y, $e, $n);
- Math::GMPz::Rmpz_add($y, $y, $c);
- Math::GMPz::Rmpz_mod($y, $y, $n);
- Math::GMPz::Rmpz_sub($g, $x, $y);
- Math::GMPz::Rmpz_gcd($g, $g, $n);
- if (Math::GMPz::Rmpz_cmp_ui($g, 1) != 0) {
- return undef if ($g == $n);
- return $g;
- }
- }
- return $n;
- }
- my @nums = qw(
- 314159265358979323 350011490889402191 2954624367769580651
- 7167393334524676153 10033529742475370477 20135752530477192241
- 21316902507352787201 2559469924891866771047 63469917720180180377579
- );
- @nums = map { Math::GMPz->new($_) } @nums;
- foreach my $n (@nums) {
- say "rho_exp_factor($n) = ", rho_exp_factor($n);
- }
- __END__
- rho_exp_factor(314159265358979323) = 990371647
- rho_exp_factor(350011490889402191) = 692953181
- rho_exp_factor(2954624367769580651) = 490066931
- rho_exp_factor(7167393334524676153) = 4721424559
- rho_exp_factor(10033529742475370477) = 1412164441
- rho_exp_factor(20135752530477192241) = 5907768749
- rho_exp_factor(21316902507352787201) = 3055371353
- rho_exp_factor(2559469924891866771047) = 266349879973
- rho_exp_factor(63469917720180180377579) = 126115748167
|