12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667 |
- #!/usr/bin/perl
- # A new factorization algorithm for semiprimes, by estimating phi(n).
- # The algorithm is called "Phi-Finder" and is due to Kyle Kloster (2010), described in his thesis:
- # Factoring a semiprime n by estimating φ(n)
- # See also:
- # http://gregorybard.com/papers/phi_version_may_7.pdf
- use 5.020;
- use strict;
- use warnings;
- use experimental qw(signatures);
- use Math::GMPz;
- use ntheory qw(is_prime is_square sqrtint logint powmod random_nbit_prime);
- sub phi_factor($n) {
- return () if $n <= 1;
- return ($n) if is_prime($n);
- if (is_square($n)) {
- return sqrtint($n);
- }
- $n = Math::GMPz->new($n);
- my $E = $n - 2 * sqrtint($n) + 1;
- my $E0 = Math::GMPz->new(powmod(2, -$E, $n));
- my $L = logint($n, 2);
- my $i = 0;
- while ($E0 & ($E0 - 1)) {
- $E0 <<= $L;
- $E0 %= $n;
- ++$i;
- }
- my $t = 0;
- foreach my $k (0 .. $L) {
- if (powmod(2, $k, $n) == $E0) {
- $t = $k;
- last;
- }
- }
- my $phi = abs($i * $L - $E - $t);
- my $q = ($n - $phi + 1);
- my $p = ($q + sqrtint($q * $q - 4 * $n)) >> 1;
- return $p;
- }
- foreach my $k (10 .. 30) {
- my $n = Math::GMPz->new(random_nbit_prime($k)) * random_nbit_prime($k);
- my $p = phi_factor($n);
- say "$n = ", $p, ' * ', $n / $p;
- }
|