123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114 |
- #!/usr/bin/perl
- # The elliptic-curve factorization method (ECM), due to Hendrik Lenstra.
- # Algorithm presented in the below video:
- # https://www.youtube.com/watch?v=2JlpeQWtGH8
- # See also:
- # https://en.wikipedia.org/wiki/Lenstra_elliptic-curve_factorization
- use 5.020;
- use strict;
- use warnings;
- use Math::GMPz qw();
- use experimental qw(signatures);
- use ntheory qw(is_prime_power logint gcd);
- use Math::Prime::Util::GMP qw(primes invmod);
- sub ecm ($N, $zrange = 100, $plimit = 10000) {
- if (is_prime_power($N, \my $p)) {
- return $p;
- }
- my @primes = @{primes($plimit)};
- foreach my $z (-$zrange .. $zrange) {
- my $x = 0;
- my $y = 1;
- foreach my $p (@primes) {
- my $k = $p**logint($plimit, $p);
- my ($xn, $yn);
- my ($sx, $sy, $t) = ($x, $y, $k);
- my $first = 1;
- while ($t) {
- if ($t & 1) {
- if ($first) {
- ($xn, $yn) = ($sx, $sy);
- $first = 0;
- }
- else {
- my $u = invmod($sx - $xn, $N);
- if (not defined $u) {
- my $d = gcd($sx - $xn, $N);
- $d == $N ? last : return $d;
- }
- $u = Math::GMPz->new($u);
- my $L = ($u * ($sy - $yn)) % $N;
- my $xs = ($L * $L - $xn - $sx) % $N;
- $yn = ($L * ($xn - $xs) - $yn) % $N;
- $xn = $xs;
- }
- }
- my $u = invmod(2 * $sy, $N);
- if (not defined $u) {
- my $d = gcd(2 * $sy, $N);
- $d == $N ? last : return $d;
- }
- $u = Math::GMPz->new($u);
- my $L = ($u * (3 * $sx * $sx + $z)) % $N;
- my $x2 = ($L * $L - 2 * $sx) % $N;
- $sy = ($L * ($sx - $x2) - $sy) % $N;
- $sx = $x2;
- $sy || return $N;
- $t >>= 1;
- }
- ($x, $y) = ($xn, $yn);
- }
- }
- return $N; # failed
- }
- if (@ARGV) {
- my ($str, $B1, $B2) = @ARGV;
- my $n = Math::GMPz->new($str);
- printf("[*] Factoring: %s (%d digits)...\n", $n, length("$n"));
- my $factor = ecm($n, $B1 // 100, $B2 // 1000);
- if ($factor > 1 and $factor < $n) {
- say "`-> found factor: $factor";
- exit 0;
- }
- else {
- say "`-> no factor found...";
- exit 1;
- }
- }
- say ecm(Math::GMPz->new("14304849576137459"));
- say ecm(79710615566344993);
- say ecm(Math::GMPz->new(2)**128 + 1); # takes ~3.4 seconds
|