Integer Factorization: Assessing Recent Revelations


Once again, the findings, though pretty, are seemingly of little moment, at least in terms of discovering something new.

But wait. Breathe. Think.

Here is what I know now, in the form it has most recently taken:

Let m be an odd positive integer, and c2 be the smallest perfect square greater than m chosen so that it is even or odd as (m+1)/2 is even or odd. c will either be the integer ceiling of the square root of m, or that number plus one. Whenever m can be written as the difference of two perfect squares, s2-t2, s2 will be even or odd just as c2 is even or odd.

If m is a perfect square, it will equal c2 and the task of factorization is done. There are any number of other circumstances that will give evidence of easily found factors, if they are there. But let us assume they are not, and that there is a positive remainder r which is the difference between c2 and m, so that m=c2-r. If r is a perfect squre, we have one of those easy circumstances since it lends itself to the easy factorization of the difference of perfect squares. If it is not, we must keep searching.

Now, go to the Zone Grid as defined here. Position it so that the x axis points straight down and the y axis points to the right. The shifted number lines for fixed x values on the Zone Grid will go in the conventional left-to-right direction. Look at the Zone 0 boundary, the line whose equation is y=-x on the Cartesian Plane, cutting through all those number lines. Find the point on the Zone 0 boundary corresponding to the smallest perfect square greater than r. Move directly to the left until you find the point on this number line in the Zone Grid that corresponds to the integer r. This is the first point of m’s Characteristic Line on the Zone Grid.

This point is, by our construction method, the value f(0) for the quadratic Characteristic Polynomial f(x) = x2+2cx+r corresponding to m=c2-r. This point has an x value equal to ceil(sqrt(r)) on the Zone Grid. Find the value of f(1) on the line corresponding to x=ceil(sqrt(r))+1, and set that as the second point to construct. The straight line passing through the first point and this one will pass subsequently through points corresponding to all values of f(x) for integer x, in subsequent lines. When it intersects with Zone Boundaries at points whose (x,y) pairs are integers, since those boundaries are populated by perfect squares at those integer points, again, possible Fermat factorization for m reveals itself.

So what is the point at which the Characteristic Line will intersect Zone Boundary n, for some n, and when will its x and y coordinates be integers?

The formula is rather simple: The x value where the Characteristic Line with equation y = ax+b, for integers a and b, will intersect Zone Boundary n is x=(n2-b)/(a+1-2n). Finding a factorization of m then becomes equivalent to finding non-negative integers n less than (a+1)/2 such that (n2-b)/(a+1-2n) is an integer. Mind you, when (a+1-2n) is equal to 2, the fraction will always divide out to an integer, since n2-b thus chosen will be even. This corresponds to the trivial factorization m equals m times 1. The Zone Boundary for a non-trivial factorizatin does seem to relate directly to the lesser number t in any Fermat factorization expression s2-t2 we find for m.

I intend to continue pursuing new patterns that will help me figure out when the integer values of (n2-b)/(a+1-2n) will fall out. I suspect they are somewhere to be found, though my pursuits have generally looped me back over the same territories so far. Maybe someday I’ll flip this problem on its head. We’ll see.

Leave a ReplyCancel reply