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:
# 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";
Leave a ReplyCancel reply