## Integer Factorization: New Algorithm and Routine – jumpfactor.pl

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)2 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:
#         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";
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";
``````

### 2 responses to “Integer Factorization: New Algorithm and Routine – jumpfactor.pl”

1. […] I added a usage line, and also programmed the loop to look only at numerators which are even, cutting the number of iterations of the main loop in half. Thus repurposed variable “idx” as the Zone number, and added another variable to serve as the iteration counter. The revised code will be, and will from now on be, in an updated version of the code block in yesterday’s release post. […]

2. […] Earlier Explanatory Posts <— for those interested. […]