JCSBimp's Hexagonal Orthogonal

Here is a new script for integer factorization that, though probably not faster than the current best algorithms, has on its side compactness, which does help with speed. I have not written it for, or tested it on, arbitrary-precision discrete semiprimes, but expect the speeds to be comparable, and hope they might even be better than that.

The script bases its function on the Ceiling Square/Remainder idea I have discussed in past posts here, and also uses relationships I noticed when examining what I call the “zone boundaries” made apparent in various plots (“Beehive plots” and the Zone Grid) with which I have tinkered during the past inspiration-filled year.

Here is the code, followed by a chart and graph comparing quickfact.pl’s iteration count with the number of jumps that my previous routine jumpfactor.pl used to get to the same answers.

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

# Name: quickfact.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:
#   28 September 2023 - Initial Release; put on jcsbimp.com blog
# 
# --------
#
# Usage: quickfact.pl <pos_int>
#
#    pos_int - the integer the user wishes to factor
#
# This Perl script finds a positive integer factor of pos_int,
# finding a non-trivial factor, if possible.
# It uses a method derived from an analytic geometry construction
# based on boundary lines of the integer grid points of f(x,y) =
# x(x+1)+y, using straight lines on the grid thus numbered between
# consecutive perfect squares to create "zone boundaries." It bases
# calculations on the first two elements of the series of remainders
# obtained by finding the Ceiling Square c^2 of pos_int, the least
# perfect square greater than pos_int that is even or odd as
# ( pos_int + 1 ) / 2 is even or odd, and computing c^2 - pos_int
# and (c+1)^2 - pos_int. Pairs of successive perfect squares greater
# than these two remainders lead the algorithm to a solution.
#
# NOTES FOR USE: Integers here are of the standard size 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: quickfact.pl <pos_int>\n",
        "  pos_int = positive integer to factor\n";
  exit( 0 );
}
my $pos_int = $ARGV[0];
if ( $pos_int < 1 ) {
  print "ERROR: $pos_int is less than 1. Quitting.\n";
  exit( 0 );
}
my $pos_ceil = ceil( $pos_int );
if ( $pos_int != $pos_ceil ) {
  print "ERROR: $pos_int is not an integer. Quitting.\n";
  exit( 0 );
}

# Declare variables.

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 ( $csr0, $csr1 ); # Ceilings of sqrts of the remainders

my ( $meo, $ceo ); # Even/odd tests to set Ceiling Root
my ( $root1, $root2 ); # Perfect squares for remainder comparison
my ( $gap1, $gap2 ); # Distances to squares for remainder comp.
my $gapdiff; # Remainder of the difference of the distances
my $num_iters = 0; # The number of iterations of the main loop
my $not_done_yet = 1; # Loop control variable
my $solrow; # When solution found, how far down the squares column
my ( $s, $t ); # Values of s and t such that pos_int = s^2 - t^2
my $debug_lines = 50; # Number of debug remainder lines to print.

# Determine if pos_int is even or odd.

if ( ( $pos_int % 2 ) == 0 ) {
  print "SUCCESS: $pos_int = 2 * ", $pos_int/2, ".\n";
  exit( 0 );
}

# pos_int is an odd positive integer.

# Calculate Ceiling Root of pos_int.

$c = ceil( sqrt( $pos_int ) );
$ceo = $c % 2;
$meo = ( ( $pos_int + 1 ) / 2 ) % 2;
if ( $ceo != $meo ) { # if unequal, make equal
  $c++;               #   by adjusting Ceiling Root
}

# Calculate the first and third terms of the Remainder Series of pos_int.

$r0 = $c * $c - $pos_int;
$r1 = $r0 + 4 * $c + 4;

# Check these remainders for easy Fermat factorization.

$csr0 = ceil( sqrt( $r0 ) );
if ( ( $csr0 * $csr0 ) == $r0 ) { # Easy answer: r0 is a perfect square.
  print "SUCCESS: $pos_int = ", ( $c - $csr0 ), " * ", ( $c + $csr0 );
  print ",\n  found by Fermat factorization on Remainder 0.\n";
  exit( 0 );
}
$csr1 = ceil( sqrt( $r1 ) );
if ( ( $csr1 * $csr1 ) == $r1 ) { # Easy answer: r1 is a perfect square.
  print "SUCCESS: $pos_int = ", ( $c + 2 - $csr1 ), " * ",
        ( $c + 2 + $csr1 );
  print ",\n  found by Fermat factorization on Remainder 1.\n";
  exit( 0 );
}

# Now ready to execute the main loop. Set up initial values.

$root1 = $csr1 - 2;
$root2 = $csr1;

# The Main Loop

while ( $not_done_yet ) {
  $num_iters++;
  $gap1 = $root1 * $root1 - $r0;
  $gap2 = $root2 * $root2 - $r1;
#  if ( $gap1 == $gap2 ) {
#    print "DEBUG: gap1 = $gap1, gap2 = $gap2, iteration number $num_iters.\n";
#    print "DEBUG: root1 = $root1, root2 = $root2.\n";
#  }
  $gapdiff = $gap1 % ( $gap1 - $gap2 );
#  if ( $num_iters < $debug_lines ) {
#    print "DEBUG: gap diff is $gapdiff.\n";
#  }
  if ( $gapdiff == 0 ) { # Solution is here!
    $not_done_yet = 0;
    $solrow = $gap1 / ( $gap1 - $gap2 );
    $t = $root1 + 2 * $solrow;
    $s = sqrt( $t * $t + $pos_int );
    print "SUCCESS: $pos_int = ", ( $s + $t ), " * ", ( $s - $t );
    print " = $s", "^2 - $t", "^2.\n";
    print "  Found solution in $num_iters iterations.\n";
  }
  if ( $not_done_yet ) {
    $root1 ++;
    $root2 ++;
  }
}