Integer Factorization: A New Preliminary Algorithm Based on “Ceiling Squares”

Advertisements

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 c2 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=s2-t2=(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=c2-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 c2-d2 and c2-(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-d2 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.

  1. Input positive integer m.
  2. 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.
  3. Set c0 to the integer ceiling of the square root of m.
  4. Assign r0=c02-m.
  5. Set d0 to the integer ceiling of the square root of r0.
  6. If r0=d02 exactly, output factorization of m as (c0+sqrt(r0)) times (c0-sqrt(r0)) and exit.
  7. Set a0=c02-d02.
  8. Set v0= a0-m. This will be the value at x=0 of the characteristic polynomial, a quadratic polynomial produced in a later step.
  9. Set c1=c0+1.
  10. Assign r1=c12-m.
  11. Set d1 to the integer ceiling of the square root of r1, and if r1=d12 exactly, proceed in a manner corresponding to that in Step 6 and exit.
  12. Set a1=c12-d12.
  13. Set v1= a1-m. This will be the value at x=1 of the characteristic polynomial.
  14. Set c2=c1+1.
  15. Set d2=d1+(d1-d0). This is different from the d0 and d1 calculations and provides a linear progression for the terms in the calculation of a2 in the next step.
  16. Set a2=c22-d22.
  17. Set v2=a2-m. This will be the value at x=2 of the characteristic polynomial.
  18. Set f2, the coefficient of the x2 term of the characteristic polynomial, to (v0+v2)/2-v1.
  19. Set f1, the coefficient of the x term of the characteristic polynomial, to 2v1-(3v0+v2)/2.
  20. Set the constant term of the characteristic polynomial to v0.

This produced a characteristic polynomial of the form F(x)=f2x2+f1x+v0 which will correspond to the distance between cn2-dn2 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