Integer Factorization: The Remaining Puzzle in Its Newest Form


Here is what I have established now, and have used in forming the algorithm I shared this past week:

I have chosen to repeat a small set of definitions and concepts I have established in other posts and papers, for clarity.

Let m be an odd positive integer we wish to factor. Let c be the integer ceiling of the square root of m, and call it the Ceiling Root of m. c2 is thus the least perfect square greater than m; define it as the Ceiling Square of m.

Now define a remainder r0 as being the difference between the Ceiling Square of m and m itself: r0=c2-m. Now we can express m as c2-r0, and can take note of the special cases where m is a perfect square, and so r0=0, or where r0 is a perfect square, and the principle (used by Pierre de Fermat) that a2-b2=(a+b)(a-b) makes factorization immediate.

But what do we do if r0 is not a perfect square? I came up with the idea of “raising the ceiling,” i.e., of increasing c by 1, 2, and so on, and looking at the remainders that result. What I know is that the factorization m=1*m gives an expression of m=a2-b2 where a=(m+1)/2 and b=(m-1)/2. I call it the “trivial factorization” of m. But any x, y pair of integers, with x<y, that factor m will also give an expression of m=a2-b2 by letting a=(x+y)/2 and b=(y-x)/2. Since we specify m to be odd, x and y will also be odd, and either a will be odd and b even, or vice versa. There are other interesting properties of this I have found and discussed elsewhere, but do not need to include here.

Consider the expression m=c2-r0 when r0 is not a perfect square. Now create a new remainder r1 by “raising the ceiling” from c to c+1 and calculating r1=(c+1)2-m. Since we have gone to the trouble of calculating this second remainder (it was necessary for steps which follow, though now I am going to start waving my hands a bit, i.e., presenting information without much explanation), we can check whether r1 is a perfect square, thus yielding a simple Fermat factorization as before. But let us assume that is not the case.

Notice that r0 and r1 each have their own Ceiling Squares. Let us call them d0 and d1. Now we have it that (unless either of these are the special case allowing Fermat factorization already described):

m is between c2-d02 and c2-(d0-1)2; let a0=c2-d02; let v0=m-a0;

m is between (c+1)2-d12 and (c+1)2-(d1-1)2; let a1=(c+1)2-d12; let v1=m-a1.

My next step is to produce a third range, and thus a third pair of values a2 and v2, by stepping linearly: raising the ceiling to (c+2)2 but setting d2=2d1-d0. When I was exploring this, it seemed a peculiar choice because it usually seemed to violate the “betweenness” I had established: m would no longer lie within the range of values thus built.

But what happens when I make this choice is that the sequence of v0, v1, v2 thus generated satisfy a quadratic polynomial, one that I have been calling the characteristic function associated with m, and denote as F(x). Those three values of v I take to be the x=0, 1, 2 values of F(x).

(Now I really am “hand-waving” because this is the part of the approach I am still figuring out.) Notice also that, due to my choices, the difference of the successive pairs of perfect squares in the ranges in which m falls, increases linearly. Also, the distance from the greater difference of squares to the *next* difference of squares in each of the ranges starts decreasing by 2, as we move from dn2 to (dn-1)2 to (dn-2)2, and so on. In other words, where the “perfect square points” fall differs linearly, both as we keep raising the ceiling linearly, and as we move from left to right on the number line examining the differences of the “raised ceiling” squares and successive perfect squares.

I realize I did not explain that very well, but it will take some effort – which I hope to make someday if this approach is successful – to explain it better.

And what I noticed is that, once I construct F(x) using v0, v1, v2 to set the quadratic coefficients, whenever I get to a value of F(x) that gives me the equivalent of the value of vn which is exactly the value of an integral point on a once-again-easy-to-construct “row polynomial” for the value of n, this will indicate that the difference between (c+n)2 and m is a perfect square, allowing the Fermat method of factorization.

This at its core is practically no farther than I have figured out anything before. In fact, my first attempt at a program using this feature was much, much slower than my previous factorization routine. But the mathematical simplicity of finding these quadratic polynomials that characterize both where m falls in the ranges designed as above, and the “row polynomials” which are also quadratic and even simpler to derive … this leads me to believe that I could still be on the verge of a process that simplifies integer factorization greatly.

To use an earlier metaphor, I am not yet convinced this is a tree up which iit is worthless for me to bark.

I shall carry on.

Leave a ReplyCancel reply