My Fastest Factorization Script So Far

Advertisements

This won’t set any algorithmic speed records, but I am happy with it, for now. It comes in at 48 lines of Perl code. factor_it_4.pl is definitely faster than factor_it_3.pl, and routinely gets its answer in fewer than half the iterations of factor_it_2.pl.

Once again, I am not experienced with writing arbitrary-precision arithmetic scripts in Perl (I have used Magma for such purposes, but do not have a Magma license at the present time). Those who can program for arbitrarily large integers are welcome to have at it. Again, though, this is not to my knowledge one of the speedier algorithms like the modern “sieve” techniques. It simply uses the Ceiling Square and characteristic polynomial concepts I have worked out to good effect.

EDITED TO ADD: I corrected the upper loop bound, albeit a little sloppily.

Sample Run:

➜  Programs factor_it_4.pl 169350257651 
Factorization found: 169350257651 = 255859 * 661889.
Result found in 23677 iterations.

Program Code for factor_it_4.pl:

#!/usr/bin/perl
use strict;
use warnings;
use POSIX qw/ceil/;

my $m = $ARGV[0];
my $twopow = 0;
my ( $idx, $fidx, $ridx );
my $m_orig = $m;
while ( ( $m % 2 ) == 0 ) {
  $twopow++;
  $m /= 2;
}
if ( $twopow ) {
  print "$m_orig has a factor of 2 to the power of $twopow.\n";
  if ( $m == 1 ) {
    print "$m_orig has no other factors.\n";
    exit;
  }
  else {
    print "Proceeding with factorization of $m.\n";
  }
}
my $c0 = ceil( sqrt( $m ) ); # ceiling square of m
my $mm4 = $m % 4;
my $cc2 = $c0 % 2;
my $add1 = 0;
if ( ( ( $mm4 == 1 ) && ( $cc2 == 0 ) )
     || ( ( $mm4 == 3 ) && ( $cc2 == 1 ) ) ) {
  $add1 = 1;
}
my $r0 = $c0 * $c0 - $m;
my $notdone = 1;
my $n_iters = 1;
for ( $idx = $add1; ( $idx < $m ) && $notdone; $idx += 2 ) {
  $fidx = $idx * $idx + 2 * $c0 * $idx + $r0;
  $ridx = ceil( sqrt( $fidx ) );
  if ( ( $ridx * $ridx ) == $fidx ) {
    print "Factorization found: $m = ", $c0 + $idx - $ridx;
    print " * ", $c0 + $idx + $ridx, ".\n";
    print "Result found in $n_iters iterations.\n";
    $notdone = 0;
  }
  $n_iters++;
}
if ( $notdone ) { # We tried!
  print "Unable to factor $m.\n";
}

2 responses to “My Fastest Factorization Script So Far”

  1. […] the Perl routine factor_it_4.pl performed as shown in the following scatter plot of m=pq vs. the number of iterations it required to factor m: […]

  2. […] ran factor_it_4.pl tonight on the collection of 10-digit and 12-digit discrete semiprimes I had generated earlier in […]

Leave a Reply to Integer Factorization: A More Uniform Test, and a Similar Result – JCSBimp’s Hexagonal Orthogonal Cancel reply