Integer Factorization: A Preliminary Characterization Script, in Perl

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.
``````