123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194 |
- #!/usr/bin/perl
- # Daniel "Trizen" Șuteu
- # Date: 08 March 2018
- # https://github.com/trizen
- # A hybrid factorization algorithm, using:
- # * Pollard's p-1 algorithm
- # * Pollard's rho algorithm
- # * A simple version of the continued-fraction factorization method
- # * Fermat's factorization method
- # See also:
- # https://en.wikipedia.org/wiki/Quadratic_sieve
- # https://en.wikipedia.org/wiki/Dixon%27s_factorization_method
- # https://en.wikipedia.org/wiki/Fermat%27s_factorization_method
- # https://en.wikipedia.org/wiki/Pollard%27s_p_%E2%88%92_1_algorithm
- use 5.020;
- use strict;
- use warnings;
- use experimental qw(signatures);
- use ntheory qw(is_prime random_prime vecprod);
- use Math::AnyNum qw(
- gcd valuation powmod irand ipow
- isqrt idiv is_square next_prime
- );
- sub fermat_hybrid_factorization ($n) {
- return () if $n <= 1;
- return ($n) if is_prime($n);
- # Test for divisibility by 2
- if (!($n & 1)) {
- my $v = valuation($n, 2);
- my $t = $n >> $v;
- my @factors = (2) x $v;
- if ($t > 1) {
- push @factors, __SUB__->($t);
- }
- return @factors;
- }
- my $p = isqrt($n);
- my $x = $p;
- my $q = ($p * $p - $n);
- my $t = 1;
- my $h = 1;
- my $z = Math::AnyNum->new(random_prime($n));
- my $g = 1;
- my $c = $q + $p;
- my $a0 = 1;
- my $a1 = ($a0 * $a0 + $c);
- my $a2 = ($a1 * $a1 + $c);
- my $c1 = $p;
- my $c2 = 1;
- my $r = $p + $p;
- my ($e1, $e2) = (1, 0);
- my ($f1, $f2) = (0, 1);
- while (not is_square($q)) {
- $q += 2 * $p++ + 1;
- # Pollard's rho algorithm
- $g = gcd($n, $a2 - $a1);
- if ($g > 1 and $g < $n) {
- return sort { $a <=> $b } (
- __SUB__->($g),
- __SUB__->($n / $g),
- );
- }
- $a1 = (($a1 * $a1 + $c) % $n);
- $a2 = (($a2 * $a2 + $c) % $n);
- $a2 = (($a2 * $a2 + $c) % $n);
- # Simple version of the continued-fraction factorization method.
- # Efficient for numbers that have factors relatively close to sqrt(n)
- $c1 = $r * $c2 - $c1;
- $c2 = idiv($n - $c1 * $c1, $c2);
- my $x1 = ($x * $f2 + $e2) % $n;
- my $y1 = ($x1 * $x1) % $n;
- if (is_square($y1)) {
- $g = gcd($x1 - isqrt($y1), $n);
- if ($g > 1 and $g < $n) {
- return sort { $a <=> $b } (
- __SUB__->($g),
- __SUB__->($n / $g),
- );
- }
- }
- $r = idiv($x + $c1, $c2);
- ($f1, $f2) = ($f2, ($r * $f2 + $f1) % $n);
- ($e1, $e2) = ($e2, ($r * $e2 + $e1) % $n);
- # Pollard's p-a algorithm (random variation)
- $t = $z;
- $h = next_prime($h);
- $z = powmod($z, $h, $n);
- $g = gcd($z * powmod($t, irand($n), $n) - 1, $n);
- if ($g > 1) {
- if ($g == $n) {
- $h = 1;
- $z = Math::AnyNum->new(random_prime($n));
- next;
- }
- return sort { $a <=> $b } (
- __SUB__->($g),
- __SUB__->($n / $g),
- );
- }
- }
- # Fermat's method
- my $s = isqrt($q);
- return sort { $a <=> $b } (
- __SUB__->($p + $s),
- __SUB__->($p - $s),
- );
- }
- my @tests = map { Math::AnyNum->new($_) } qw(
- 160587846247027 5040 65127835124 6469693230
- 12129569695640600539 38568900844635025971879799293495379321
- 5057557777500469647488909553014309710588182149566739774380944488183531188525863600127265768146701283
- );
- foreach my $n (@tests) {
- my @f = fermat_hybrid_factorization($n);
- say "$n = ", join(' * ', @f);
- die 'error' if vecprod(@f) != $n;
- die 'error' if grep { !is_prime($_) } @f;
- }
- say "\n=> Factoring 2^k+1";
- foreach my $k (1 .. 100) {
- my $n = ipow(2, $k) + 1;
- my @f = fermat_hybrid_factorization($n);
- say "2^$k + 1 = ", join(' * ', @f);
- die 'error' if vecprod(@f) != $n;
- die 'error' if grep { !is_prime($_) } @f;
- }
- # Test the continued-fraction method with factors relatively close to sqrt(n)
- foreach my $k (1 .. 100) {
- my $p = random_prime(ipow(2, 100 + $k));
- my $n = next_prime($p + irand(10**15)) * $p;
- my @f = fermat_hybrid_factorization($n);
- #say join(' * ', @f), " = $n";
- die 'error' if vecprod(@f) != $n;
- die 'error' if grep { !is_prime($_) } @f;
- }
- # Test for small numbers
- for my $n (1 .. 1000) {
- my @f = fermat_hybrid_factorization($n);
- die 'error' if vecprod(@f) != $n;
- die 'error' if grep { !is_prime($_) } @f;
- }
|