Integer Factorization: Plotting the Bee Line


I came up with an idea late last night (after midnight turned March 3 to March 4) that is a bit exciting, although I know enough from the past months of study to temper my excitement with some realism as to the chance of it translating into an actual algorithmic breakthrough.

So far, the idea is mostly graphic/visual in nature, but it has to do with the remainder difference between odd positive integer m and its Ceiling Square, the smallest perfect square greater than m that is even or odd as (m+1)/2 is even or odd; or, equivalently, is even or odd as m is congruent to 3 or to 1 modulo 4.

It has to do with what I call a characteristic function of m, f(x)=x2+2cx+r0, where c and r0 come from m=c2-r0, the expression of m in terms of its Ceiling Square c and the remainder difference r0. The function’s values for x=0,1,2,… are a remander series r0,1,2,… obtained by starting with r0, the difference between the Ceiling Square and m, increasing the Ceiling Root c by 1, squaring the result, and computing the next remainder difference.

What I had done in the past, and addressed anew this week just past, was to investigate patterns of the perfect squares that immediately bounded each of these remainders. I did this because the answer to factorization lies in finding the least rn that is itself a perfect square, allowing easy “Fermat factorization” of the resultant m=(c+n)2-rn2 using the identity x2-y2=(x+y)(x-y).

What I have come up with is, I think and hope, a way to represent the set of perfect-square boundaries between the values of f(x) as a fixed set of straight lines of known slope, with the set of remainders producing another straight line that intersects those lines, and using the fixed nature of all these lines to calculate – hopefully instantly – where they will intersect on an integer boundary.

As illustration, I am presenting my fixed-width-font text file I used to visualize and develop the concepts in my mind last night.

I call the straight line made by the X characters, which represent the remainders, the “bee line,” based on an earlier visualization I’d developed using asterisks and Xs, that resembled a hive, with the asterisks in that case (but not this one) representing bees in a hive who bounce around erratically but eventually travel in a straight line to get to the door at the bottom.

I will develop this idea algorithmically to accompany my graphical thinking about it. I feel it shows promise, but I also have a healthy dose of realism as to whether I have come up with something that creates a direct, formulaic jump from c2 to the greater perfect square that will permit factorization of m.

Stay tuned!

Leave a ReplyCancel reply