## Integer Factorization – New Code for characterize.pl

I believe this is running correctly. I’ll certainly correct it if it is not. EDIT: I have indeed updated the code. I suspect it’s almost if not entirely in its final form. A couple of small values in the entire set of discrete semiprimes whose primes are less than 100 showed negative discriminants, but I do not know whether I should even worry about that infrequent occurrence.

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

my \$m = \$ARGV;
my \$twopow = 0;
my ( \$f1, \$f2, \$f3 );

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 ) ); # ceiling square of m
print "The Ceiling Square of \$m is \${c0}^2.\n";
my \$mm4 = \$m % 4;
my \$cc2 = \$c0 % 2;
print "\$m is congruent to \$mm4 modulo 4, and the ceiling square is ";
if ( \$cc2 ) {
print "odd";
}
else {
print "even";
}
print ".\nAll expressions of \$m as the difference of two squares will have\n";
print "  the form s^2 - t^2 where s is ";
if ( \$mm4 == 1 ) {
print "odd and t is even.\n";
}
else {
print "even and t is odd.\n";
}
if ( ( ( \$mm4 == 1 ) && ( \$cc2 == 0 ) )
|| ( ( \$mm4 == 3 ) && ( \$cc2 == 1 ) ) ) {
print "This means we must adjust the initial ceiling square from \$c0 to ";
\$c0++;
print "\$c0.\n";
}
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 + 2;
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 + 2;
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;
}
\$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=";
print " values of the characteristic";
print " polynomial as:\n";
print "  \$v0, \$v1, and \$v2, leading to characteristic polynomial:\n";
\$f1 = (\$v0 - 2 * \$v1 + \$v2) / 8;
\$f2 = ( 3 * \$v1 - \$v2 ) / 2 - \$v0;
\$f3 = ( 15 * \$v0 - 10 * \$v1 + 3 * \$v2 ) / 8;
}
else {
\$f2 = \$v1 - ( 3 * \$v0 + \$v2 ) / 4;
\$f3 = \$v0;
}
print "  F(X) = \$f1", "X^2 + \$f2", "X + \$f3.\n";
my \$discrim = \$f2 * \$f2 - 4 * \$f1 * \$f3;
print "  The Discriminant of F(x) is \$discrim.\n";
``````

# Sample Run:

``````➜  Programs characterize.pl 3589
The Ceiling Square of 3589 is 60^2.
3589 is congruent to 1 modulo 4, and the ceiling square is even.
All expressions of 3589 as the difference of two squares will have
the form s^2 - t^2 where s is odd and t is even.
This means we must adjust the initial ceiling square from 60 to 61.
3589 = 61^2 - 132, putting it between
A0 = 3577 = 61^2 - 12^2 and
B0 = 3600 = 61^2 - 11^2.
M - A0 = 12. Span of this range is 23.
3589 = 63^2 - 380, putting it between
A1 = 3569 = 63^2 - 20^2 and
B1 = 3608 = 63^2 - 19^2.
M - A1 = 20. Span of this range is 39.
3589 = 65^2 - 636, and the linear progression of range gives:
A2 = 3441 = 65^2 - 28^2 and
B2 = 3496 = 65^2 - 27^2.
M - A2 = 148. Span of this range is 55.
(Note that this time, M falls to the right of B2.)

This gives the x=1, 3, 5 values of the characteristic polynomial as:
12, 20, and 148, leading to characteristic polynomial:
F(X) = 15X^2 + -56X + 53.
The Discriminant of F(x) is -44.``````

### 2 responses to “Integer Factorization – New Code for characterize.pl”

1. […] Here is the link to the post from yesterday with the script in the form I updated today. […]

2. […] I have fixed it and placed the updated code in my original characterize.pl post. […]