Integer Factorization – New Code for characterize.pl

Advertisements

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[0];
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";
}
my $add1 = 0;
if ( ( ( $mm4 == 1 ) && ( $cc2 == 0 ) )
     || ( ( $mm4 == 3 ) && ( $cc2 == 1 ) ) ) {
  print "This means we must adjust the initial ceiling square from $c0 to ";
  $c0++;
  $add1 = 1;
  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 $add1, ", ", $add1 + 2, ", ", $add1 + 4;
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;
if ( $add1 ) {
  $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. […]

Leave a Reply to Integer Factorization: Web-Publish in Haste, Repent at Leisure! 😀 – JCSBimp’s Hexagonal Orthogonal Cancel reply