## DISCLAIMER: The factorization method described here is not complete. This algorithm sets up a quadratic polynomial which produces points for a later comparison step. I will describe the comparison yet to be done, but it is not yet part of the existing algorithm I have written.

I have decided to formulate, and will later write, test, and provide in Perl code, a new algorithm to begin a process of integer factorization of a positive integer m, based on what I call the Ceiling Square of m, which is the square of the integer ceiling of the square root of m, and the Ceiling Square of the remainder when m is subtracted from its Ceiling Square.

I have based the approach I am using here on the fact that if c^{2} is the least perfect square greater than m, any factorization of m, including the trivial factorization m equals one times m, corresponds to an expression:

m=s^{2}-t^{2}=(s+t)(s-t)

for some pair of positive integers s and t, and that s in this case will be greater than c, the Ceiling Root of m. My intention is eventually to arrive at a formulaic determination of s, and therefore t, based on the known values m, c, and r in the expression of m in terms of its Ceiling Square and remainder: m=c^{2}-r. I use in my approach a method I call “raising the ceiling,” which is simply using further remainders after subtracting m from (c+1)^{2} and (c+2)^{2} – thus raising the ceiling, so to speak. These further remainders help me determine a characteristic polynomial for where the series of “raised ceiling” remainders fall between certain values of differences of perfect squares. I construct these differences starting with values of c^{2}-d^{2} and c^{2}-(d-1)^{2} which bound m, and then, when I raise the ceiling, I modify the ranges in a linearly-progressing fashion. I have done this as an attempt to get rid of, or at least to tame, some of the jumpy randomness of how I have observed remainders modulo ceiling squares to behave for consecutive values of m.

Steps I have not yet completed then follow: I use the characteristic polynomial thus obtained, along with the linearly-changing distribution of differences of perfect squares corresponding to values of (c-n)^{2} for n = 0, 1, 2, …, to determine the value of n at which the characteristic polynomial will place its value directly onto a (c-n)^{2}-d^{2} value, which, if I have conceived this correctly, will lead to a non-trivial factorization of m, if such exists. It is in these all-important subsequent steps that I hope to increase algorithmic efficiency compared to known methods. However, I freely admit that is work yet to be done, and I do not guarantee my own success in that regard.

Here are the algorithmic steps for what I have done so far.

- Input positive integer m.
- If m is even, divide out factors of 2 and exit. Alternately, if further and/or complete factorization is what we want, divide out by 2, keep track of the power of 2 thus obtained as a factor, set m to the odd value >1 that remains, if any, and continue if that is the case.
- Set c
_{0}to the integer ceiling of the square root of m. - Assign r
_{0}=c_{0}^{2}-m. - Set d
_{0}to the integer ceiling of the square root of r_{0}. - If r
_{0}=d_{0}^{2}exactly, output factorization of m as (c_{0}+sqrt(r_{0})) times (c_{0}-sqrt(r_{0})) and exit. - Set a
_{0}=c_{0}^{2}-d_{0}^{2}. - Set v
_{0}= a_{0}-m. This will be the value at x=0 of the characteristic polynomial, a quadratic polynomial produced in a later step. - Set c
_{1}=c_{0}+1. - Assign r
_{1}=c_{1}^{2}-m. - Set d
_{1}to the integer ceiling of the square root of r_{1}, and if r_{1}=d_{1}^{2}exactly, proceed in a manner corresponding to that in Step 6 and exit. - Set a
_{1}=c_{1}^{2}-d_{1}^{2}. - Set v
_{1}= a_{1}-m. This will be the value at x=1 of the characteristic polynomial. - Set c
_{2}=c_{1}+1. - Set d
_{2}=d_{1}+(d_{1}-d_{0}). This is different from the d_{0}and d_{1}calculations and provides a linear progression for the terms in the calculation of a_{2}in the next step. - Set a
_{2}=c_{2}^{2}-d_{2}^{2}. - Set v
_{2}=a_{2}-m. This will be the value at x=2 of the characteristic polynomial. - Set f
_{2}, the coefficient of the x^{2}term of the characteristic polynomial, to (v_{0}+v_{2})/2-v_{1}. - Set f
_{1}, the coefficient of the x term of the characteristic polynomial, to 2v_{1}-(3v_{0}+v_{2})/2. - Set the constant term of the characteristic polynomial to v
_{0}.

This produced a characteristic polynomial of the form F(x)=f_{2}x^{2}+f_{1}x+v_{0} which will correspond to the distance between c_{n}^{2}-d_{n}^{2} for successive values of the “raised ceiling”. Since distances between values which are differences between the raised ceiling squares perfect squares and the next greater perfect squares increase linearly, it is my hope that this approach may eventually produce a formulaic shortcut to find which value of n produces the correct “raised ceiling” square that leads to factorization.

At the worst, this could be no slower than previous factorization algorithms I have shared which calculate n (I in the past have called this value the Ascent above the Ceiling Root). Frankly, it could be improbable that this leads to anything better. I am still exploring its properties, of course, to obtain a better idea of whether or not that is the case.

## Leave a ReplyCancel reply