Integer Factorization: The Two Currently Apparent Best Leads


First off, here are references to two earlier articles I have posted on the subjects that follow, by way of explanation rather than going over it all again:

Integer Factorization: The Adjusted Ceiling Square, and Newly Deriving an Old Characteristic Polynomial

A Method of Construction and a Theorem for Integer Factorization

I have a couple of tacks I’m taking in trying to discover a general formula, yet unknown, for deriving the Ascent one must add to the Ceiling Square of the positive odd integer m to render the resultant sum as another perfect square and thus produce a Fermat factorization of m.

The first lead I will mention is right now the least promising in my mind, because it’s not opening up the kinds of new vistas I thought it would: namely, the Zone Grid and its boundaries, as explained in the “Method of Construction” blog post above, do not simplify matters or speed up an algorithm very much, despite their exciting promise. The “Jumping” metaphor for traveling from Zone to Zone was indeed thrilling, evocative as it was of sci-fi spaceship travel that is based on some kind of “jump.” But the proof is in the formula, and it has not yet made one evident. There is not yet the equivalent of the Spore Drive for getting to the elusive Ascent from a known c, r pair.

The second lead, while not yet guiding me to anyting formulaic, except perhaps in the algorithmic sense, has to do with m’s Characteristic Polynomial, f(x) = x2+2cx+r = (x+c)2-m, and the series of values it produces for x=0,1,2,… given any particular m. The least nonnegative x producing an f(x) value that is a perfect square also leads to the Fermat factorization of m. It is, in fact, the Ascent to which I’ve referred during this whole study. What I have found as a great help, and one that I shall explore further and try to incorporate in factorization software, is that when one examines the values f(x) for a particular m, one finds the values that can possibly be perfect squares, based on their last four hexadecimal digits, to be both in the minority and somewhat evenly spaced.

The screenshots below are of rectangular arrangements of some of the values of f(x), starting at x = 0, when m = 5305, 7909, and 82975273. (Forgive my including a discrete semiprime that exhibits a ridiculous ease of “finding by eyeball” its least prime factor; i.e., a multiple of 5. I seek a general formula that will be much faster in the general case, regardless of whether eyeballing a particular case might bring an immediate answer.)

Some of the chart for m=5305
… for m=7909
… and for m=82975273.

Arranging the values of f(x) in rows sixteen long works for my purposes because of how the values modulo 65536 appear to arrange themselves, due to the properties of the quadratic function and of integers modulo powers of 2: namely, how values for x compare to values of x+2n for some n (here, n=4, 5, and 6 for different arrays of f(x) values.

These appear (without proof, though I suspect one might not be difficult) to be periodic properties, and thus useful for an iterative algorithm.

Leave a ReplyCancel reply