Integer Factorization: Describing My New Approach


Enough teasing and tantalizing. I’m at the stage now where it would do me good to describe the new integer factorization algoritm idea a little bit better, so that I will have a clear conception of it in my own mind as I move from designing it to programming it.

As we take the Ceiling Square of an odd positive integer m we wish to factor, and start increasing the Ceiling Root, the square root of that perfect square, by 1 at a time, the difference between (c+n)2 and m will grow quadratically. This difference thus forms what I call the remainder series for m. Each remainder in the series is either a perfect square or an integer somewhere between two consecutive perfect squares.

One can arrange the non-negative integers in rows offset by varying amounts (the amounts vary by shifting in quadratically-increasing amounts) so that the perfect squares fall along straight lines at various angles: a family of straight lines fairly easily categorized. I’ve charted a rectangular portion of this arrangement with the perfect squares in red:

If you were to take the remainder series created by incrementing the Ceiling Square and subtracting m from the result as above, with the n I wrote in the expression starting at 0 and increasing by 1, and mark the n=0 remainder value in the bottom row, the n=1 value in the next row up, and so on, you would see that the remainder values also fall on a straight line of their own.

Now, the remainder values satisfy a quadratic function based on the Ceiling Square c2 and the initial remainder value r when m=c2-r. Take c, the Ceiling Root, and produce the quadratic equation f(x)=x2+2cx+r, and this function will produce values that equal the remainder series when x=0,1,2,… .

It is my intention to calculate where the straight line on the above number chart produced by the remainder series intersects some of the lines passing through the perfect squares, determining the values one at a time until the remainder line intersects a perfect square “zone line,” as I am calling them, at an integer point. At this point, the algorithm will have found what I call the Ascent, the amount to add to the Ceiling Root to produce a value of (c+n)2 that differs from m by a perfect square amount, enabling “Fermat factorization” of m.

I suspect this *might* be a quicker algorithm than any I have so far produced since I began investigating this problem in earnest. How it would compare with the best integer factorization algorithms out there, I am not quite mathematically qualified to say. But I am ready to share my work with the wider mathematical community, and have already been tagging the American Mathematical Society with links to my blog posts all along.

It’s getting close. I am working on moving my effort from sketching out ideas to writing Perl code, getting ready to try these “jumps” between the perfect square “zone” boundary lines. I’m about to see how fast they get me somewhere.

Leave a ReplyCancel reply