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 ++;
}
}
```

## Leave a ReplyCancel reply