Integer Factorization: A Preliminary Characterization Script, in Perl

Advertisements

I am posting a Perl script here that illustrates the algorithm I described in my previous post, a first step to what I hope could be a new approach to integer factorization.

The characterize.pl source code follows:

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

my $m = $ARGV[0];
my $twopow = 0;

while ( ( $m % 2 ) == 0 ) {
  $twopow++;
  $m /= 2;
}
if ( $twopow ) {
  print "$m has a factor of 2 to the power of $twopow.\n";
  if ( $m == 1 ) {
    print "$m has no other factors.\n";
    exit;
  }
  else {
    print "Proceeding with characterization of $m.\n";
  }
}

my $c0 = ceil( sqrt( $m ) );
my $r0 = $c0 * $c0 - $m;
if ( $r0 == 0 ) {
  print "$m is a perfect square: $c0 times $c0.\n";
  print "For further characterization, resubmit with argument of $c0.\n";
  exit;
}
my $d0 = ceil( sqrt( $r0 ) );
if ( ( $d0 * $d0 ) == $r0 ) {
  print "$m = $c0", "^2 - ", $d0, "^2.\n";
  print "  Factorization into ", $c0 - $d0, " times ", $c0 + $d0;
  print " immediately follows.\n";
  exit;
}
my $a0 = $c0 * $c0 - $d0 * $d0;
my $b0 = $c0 * $c0 - ( $d0 - 1 ) ** 2;
my $v0 = $m - $a0;
print "$m = $c0", "^2 - $r0, putting it between\n";
print "  A0 = $a0 = $c0", "^2 - $d0", "^2 and\n";
print "  B0 = $b0 = $c0", "^2 - ", $d0 - 1, "^2.\n";
print "  M - A0 = $v0. Span of this range is ", $b0 - $a0, ".\n";
my $c1 = $c0 + 1;
my $r1 = $c1 * $c1 - $m;
my $d1 = ceil( sqrt( $r1 ) );
if ( ( $d1 * $d1 ) == $r1 ) {
  print "$m = $c1", "^2 - ", $d1, "^2.\n";
  print "  Factorization into ", $c1 - $d1, " times ", $c1 + $d1;
  print " immediately follows.\n";
  exit;
}
my $a1 = $c1 * $c1 - $d1 * $d1;
my $b1 = $c1 * $c1 - ( $d1 - 1 ) ** 2;
my $v1 = $m - $a1;
print "$m = $c1", "^2 - $r1, putting it between\n";
print "  A1 = $a1 = $c1", "^2 - $d1", "^2 and\n";
print "  B1 = $b1 = $c1", "^2 - ", $d1 - 1, "^2.\n";
print "  M - A1 = $v1. Span of this range is ", $b1 - $a1, ".\n";
my $c2 = $c1 + 1;
my $r2 = $c2 * $c2 - $m;
my $d2 = ceil( sqrt( $r2 ) ); # *** not the actual d2 value we will use ***
if ( ( $d2 * $d2 ) == $r2 ) {
  print "$m = $c2", "^2 - ", $d2, "^2.\n";
  print "  Factorization into ", $c2 - $d2, " times ", $c2 + $d2;
  print " immediately follows.\n";
  exit;
}
if ( ( $d2 * $d2 ) == $r2 ) {
  print "$m = $c2", "^2 - ", $d2, "^2.\n";
  print "  Factorization into ", $c2 - $d2, " times ", $c2 + $d2;
  print " immediately follows.\n";
  exit;
}
$d2 = 2 * $d1 - $d0;
my $a2 = $c2 * $c2 - $d2 * $d2;
my $b2 = $c2 * $c2 - ( $d2 - 1 ) ** 2;
my $v2 = $m - $a2;
print "$m = $c2", "^2 - $r2, and the linear progression of range gives:\n";
print "  A2 = $a2 = $c2", "^2 - $d2", "^2 and\n";
print "  B2 = $b2 = $c2", "^2 - ", $d2 - 1, "^2.\n";
print "  M - A2 = $v2. Span of this range is ", $b2 - $a2, ".\n";
if ( $b2 < $m ) {
  print "  (Note that this time, M falls to the right of B2.)\n";
}
print "\n  This gives the x=0,1,2 values of the characteristic";
print " polynomial as:\n";
print "  $v0, $v1, and $v2, leading to characteristic polynomial:\n";
my $f1 = ($v0 + $v2) / 2 - $v1;
my $f2 = 2 * $v1 - ( 3 * $v0 + $v2 ) / 2;

Sample runs follow:

➜  Programs characterize.pl 2523746963
2523746963 = 50237^2 - 9206, putting it between
  A0 = 2523746953 = 50237^2 - 96^2 and
  B0 = 2523747144 = 50237^2 - 95^2.
  M - A0 = 10. Span of this range is 191.
2523746963 = 50238^2 - 109681, putting it between
  A1 = 2523746420 = 50238^2 - 332^2 and
  B1 = 2523747083 = 50238^2 - 331^2.
  M - A1 = 543. Span of this range is 663.
2523746963 = 50239^2 - 210158, and the linear progression of range gives:
  A2 = 2523634497 = 50239^2 - 568^2 and
  B2 = 2523635632 = 50239^2 - 567^2.
  M - A2 = 112466. Span of this range is 1135.
  (Note that this time, M falls to the right of B2.)

  This gives the x=0,1,2 values of the characteristic polynomial as:
  10, 543, and 112466, leading to characteristic polynomial:
  F(X) = 55695X^2 + -55162X + 10.

➜  Programs characterize.pl 527
527 = 23^2 - 2, putting it between
  A0 = 525 = 23^2 - 2^2 and
  B0 = 528 = 23^2 - 1^2.
  M - A0 = 2. Span of this range is 3.
527 = 24^2 - 7^2.
  Factorization into 17 times 31 immediately follows.

Leave a Reply Cancel reply