JCSBimp's Hexagonal Orthogonal

A little over a month’s worth of mathematical and numerical study and effort, ending in an amazing week of realization about the structure of numbers and their factors, have led me to a finished product which, despite probably not being revolutionary, leaves me feeling very satisfied about what I have learned, and all the ways I was able to figure out on my own how to visualize, implement, and program those insights.

I have written a new Perl script based on the ceiling squares concept I have been discussing in the past several posts here, and in the accompanying study reports to which I have linked in those posts. This perl script finds and returns a factor of m, prints that factor and how many iterations it took to find it, and exits.

As I have mentioned in other posts, I do not believe I have found some new, lightning fast method for integer factorization. This is, however, the fastest algorithm I have written yet to test the concepts I have discovered. I daresay it might blow trial-division-based schemes out of the water, but I have not done comparison testing even at that rudimentary a level. I believe it is certainly a small enough set of code for anyone who is interested to perform further testing with a minimum of bother.

The program uses standard integer variables in Perl. That is, I did not put arbitrary precision arithmetic in the packages I included near the top of the code. I assume for anyone familiar with adding such data structures to Perl code, this modification would be easy. And for someone running computer algebra software such as MAGMA, entering the algorithm would not be difficult, since the Perl code is only 21 lines long and uses only the mathematical functions ceil, floor, and sqrt.

Someone with experience in running advanced algorithms for integer factorization, such as the Number Field Sieve, could if they wished compare the performance of this short script to such methods. This algorithm works to factor an integer m=pq especially rapidly when the factors are somewhat but not necessarily especially close to the square root of m. The basic realization that led me to write this code occurred very early this morning and I described it briefly in my blog post here, “Some Number Theory.”

Here is the source code; again, it is very short, so there are no comments. However, I have used a plugin with settings specifically for Perl source code:

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

my $m = $ARGV[0];
my ( $r_cand, $s_cand, $rc_floor, $n_iters );

$n_iters = 1;
$s_cand = ceil( sqrt( $m ) );
$r_cand = $s_cand * $s_cand - $m;
$rc_floor = floor( sqrt( $r_cand ) );
while ( ( $rc_floor * $rc_floor ) < $r_cand ) {
  $s_cand++;
  $r_cand = $s_cand * $s_cand - $m;
  $rc_floor = floor( sqrt( $r_cand ) );
  $n_iters++;
}
print "\n", $s_cand - $rc_floor, " is a factor of $m.\n";
print "cf_exam.pl found this factor in $n_iters iterations.\n";

And here is the output from a few sample runs, again with values of m well within Perl’s normal integer limits:

 ~/Programs/ cf_exam.pl 2523746963

32299 is a factor of 2523746963.
Factor found in 4982 iterations.
 ~/Programs/ cf_exam.pl 197389428373

198953 is a factor of 197389428373.
Factor found in 151262 iterations.
 ~/Programs/ vim cf_exam.pl         
 ~/Programs/ cf_exam.pl 115185812569

191953 is a factor of 115185812569.
Factor found in 56623 iterations.
 ~/Programs/ cf_exam.pl 203440623317

256423 is a factor of 203440623317.
Factor found in 73858 iterations.
 ~/Programs/ time cf_exam.pl 197389428373

198953 is a factor of 197389428373.
Factor found in 151262 iterations.
cf_exam.pl 197389428373  0.04s user 0.01s system 91% cpu 0.057 total

I wrote and ran this Perl script on a MacBook Pro 13-inch 2020 with an Intel chip, running macOS Monterey Version 12.3.1