JCSBimp's Hexagonal Orthogonal

Reality has tempered and sobered my earlier excitement, but I still think this new approach holds promise. And there’s a lot I can’t yet tell about the new Perl factorization script jumpfactor.pl just yet – it’s brand new code, after all.

On the sobering side, my initial assessment that the inter-Zone jumps grew rapidly is somewhat true, somewhat not. I was distressed to observe that the number of jumps seems, at least for the values of m I’ve tested, to be greater, and typically nuch greater, than the Ascent, the number n to add to the Ceiling Root c to make the “raised” Ceiling Square (c+n)² differ from m by a perfect square.

But the main loop in this case is just a small handful of instructions and numerical operations, and that brings me to the promising part: This script does not get hung up on some of the random numbers I tested, numbers that would definitely hang up, or have huge run times for, my earlier factorization algorithms.

Is this going to be a historically faster factorization algorithm? I have grave doubts about that. Is it going to be a fast technique to apply to arbitrary precision integers? I do not yet know this, and have not written code in a language to investigate this, but it’s an enticing question.

So first, a chart and then the Perl source code follow.

This is a scatter plot of Ascent/2 vs. number of “Zone Jumps”, for a set of fifty discrete semiprimes of ten to twelve digits in length.

And here is the “free software” source code for jumpfactor.pl:

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

# Name: jumpfactor.pl
# Author: J. Calvin Smith
#
# Notice: Copyright 2023 J. Calvin Smith <jcsbimp@me.com>
#         <https://jcsbimp.com> Ceiling-Square-based
#         integer factorization script and algorithm.
#
#         Licensed for use under terms of GNU-GPL v3,
#         publicly available at the web link:
#         https://opensource.org/license/gpl-3-0/, as
#         follows:
#
# This program is free software: you can redistribute it
# and/or modify it under the terms of the GNU General Public
# License as published by the Free Software Foundation, either
# version 3 of the License, or (at your option) any later version.
# This program is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
# General Public License (linked above) for more details.
#
# --------
#
# Revision History:
#   7 March 2023 - Initial Release; put on jcsbimp.com blog
#   8 March 2023 - Added usage line; sped up to bypass odd/even Zones
# 
# --------
#
# Usage: jumpfactor.pl <pos_int>
#
#    pos_int - the integer the user wishes to factor
#
# This Perl script factors pos_int, finding a non-trivial factorization,
# if possible, after dividing by 2 as necessary to make pos_int odd.
# It uses a method derived from analytic geometry based on boundary
# lines between "zones" of integers between consecutive perfect
# squares, traveling these along a line suggested by remainders of
# pos_int subtracted from an increasing series of perfect squares
# larger than it.
#
# NOTES FOR USE: This script does not necessarily factor pos_int
# completely into powers of primes. It is possible that one of the odd
# factors jumpfactor.pl will itself be composite. This software works
# with integer arguments and variables of the standard size represented
# in Perl. No use of arbitrary-precision variables or arithmetic appears,
# but a developer wishing to make a future such version to test the
# algorithm on arbitrarily large integers has both the author's permis-
# sion and his blessing, this being free and proof-of-concept  software.

# Test for argument vector; give usage line if empty.

my $num_args = $#ARGV + 1;
if ( $num_args == 0 ) {
  print "Usage: jumpfactor.pl <pos_int>\n",
        "  pos_int = positive integer to factor\n";
}

# Declare variables.

my $m = $ARGV[0];
my $c; # the (Adjusted) Ceiling Root of m
my $r0; # c^2-m, the first remainder
my $r1; # (c+1)^2-m, the second remainder
my ( $rr0, $rr1 ); # ceil(sqrt(r0)) and ceil(sqrt(r1))
                   # since we have r0 and r1 anyway, this
                   # speeds us up if perfect squares 
my $meo; # holds whether (m+1)/2 is even or odd
my $ceo; # holds whether ceil(sqr(m)) is even or odd
my ( $zbeo, $rbeo ); # similar even/odd check for zb and rb
my ( $r0x, $r0y ); # the (x,y) of remainder 0 on Jump Chart
my ( $r1x, $r1y ); # the (x,y) of remainder 1 on Jump Chart
my $ydist; # the y distance between remainders 0 and 1 
my ( $ra, $rb ); # the slope and intercept of the Remainder Line
my ( $za, $zb ); # the slope and intercept for each Zone Line
my ( $ix, $iy ); # the intersection point between the Remainder
                #   Line and the current Zone Line
my ( $inum, $idenom); # the numerator and denominator of the x-value
                      # of the intersection point
my $imod; # the remainder when idenom divides inum
my $keepgoing = 1; # Indicates not done yet; set to 0 to finish
my $powtwo = 0; # the largest power of 2 dividing m
my ( $m1, $m2 ); # the odd factors of m to output
my $iters; # main loop index
my $idx; # zone number index
my $ascent; # amount to add to c to get answer
my ( $s, $t ); #terms for s^2-t^2 representation of m

print "Factoring $m:\n";

# Divide out powers of 2.

while ( ( $m % 2 ) == 0 ) { # m is still even
  print "$m is even - dividing 2 completely out.\n";
  $m /= 2;
  $powtwo++;
}
if ( $powtwo > 0 ) {
  print "$ARGV[0] = 2 to the power of $powtwo times $m.\n";
  if ( $m > 1 ) {
    print "Proceeding with factorization of $m.\n";
  }
  else {
    exit;
  }
}

# Compute Ceiling Root of odd $m and the first two remainders $r0 and $r1.

$c = ceil( sqrt( $m ) );
$meo = ( ( $m + 1 ) / 2 ) % 2;
$ceo = $c % 2;

unless ( $meo == $ceo ) {
  $c++;
}

# The Ceiling Square of m, c^2, is the smallest perfect square greater
# than m having the same even/odd parity as (m+1)/2. Call c the
# Ceiling Root of m.
#
# Calculate remainders for Ceiling Root c and for c+1.

$r0 = $c * $c - $m;
# print "$m is $c squared minus $r0.\n";
$r1 = ( $c + 1 ) * ( $c + 1 ) - $m;

# Deal with "simple" factorization based on perfect square remainders.
# If there are such based on $r0 or $r1, return the answer and exit.

$rr0 = ceil( sqrt( $r0 ) );
if ( ( $rr0 * $rr0 ) == $r0 ) {
  print "Factorization found (special case): $m = ", ( $c - $rr0 ),
    " * ", ( $c + $rr0 ), ".\n";
  exit;
}
$rr1 = ceil( sqrt( $r1 ) );
if ( ( $rr1 * $rr1 ) == $r1 ) {
  print "Factorization found (special case): $m = ", ( $c + 1 - $rr1 ),
    " * ", ( $c + 1 + $rr1 ), ".\n";
  exit;
}

# Locate $r0 and $r1 as Cartesian Plane points and compute
# the slope/intercept coefficients of the Remainder Line.

$r0x = $rr0;
$r1x = $r0x + 1;
$r0y = $r0 - $r0x * ( $r0x + 1 );
$r1y = $r1 - $r1x * ( $r1x + 1 );
# print "Remainders give line through (${r0x},${r0y}) and (${r1x},${r1y}).\n";
$ra = $r1y - $r0y;
$rb = $r1y - $r1x * $ra;
$rbeo = $rb % 2;
# print "Slope is $ra and y-intercept is $rb.\n";

# Main Loop: Compute successive slope/intercept coefficients for
# Zone Lines and calculate the intersection points of the Jump Line
# with them until such a point has integer x and y. This will give
# the desired Ascent to add to the Ceiling Square of pos_int ($m)
# to enable its factorization in the Fermat form.

$idx = 0; # the index for the Zone in the following loop
$iters = 0; # the number of iterations of the loop
# print "Calculating intersection points: Zone ";
while ( $keepgoing ) {
  # print "$idx";
  $zbeo = $idx % 2;
  unless ( $zbeo == $rbeo ) {
    $idx++;
  }
  $za = 2 * $idx - 1;
  $zb = $idx * $idx;
  if ( $za >= $ra ) { # I hope this condition will never happen! - JCS
    print "\nFAILURE - Remainder line will not intersect.\n";
    print "Factorization not found.\n";
    exit;
  }
  if ( ( ( $zb - $rb ) % ( $ra - $za ) ) == 0 ) {
    # We have an integer-valued intersection point.
    $keepgoing = 0; # Exit the loop
  }
#  else {
#    print "... ";
#  }
#  if ( $iters < 5 ) {
#    $inum = $zb - $rb;
#    $idenom = $ra - $za;
#    $ix = $inum / $idenom;
#    $iy = $ra * $ix + $rb;
#    $imod = $inum % $idenom;
#    print "Zone $idx intercept x value is ${inum}/${idenom}. Rem $imod.\n" 
#  }
  $idx += 2; # jumps will be between even numerators
  $iters++;
}

# Output the factorization.
# $idx--;
$inum = $zb - $rb;
$idenom = $ra - $za;
$ix = $inum / $idenom;
$iy = $ra * $ix + $rb;
# print "\nSUCCESS at Zone $idx intersection point (${ix},${iy}).\n";
$ascent = $ix - $r0x;
$s = $c + $ascent;
$t = sqrt( $s * $s - $m );
print "$m factors into ", ( $s - $t ), " times ", ( $s + $t ), ".\n";
print "jumpfactor.pl executed $iters iterations of the main loop.\n";