Integer Factorization: The Adjusted Ceiling Square and Characteristic Polynomial


I’ve got a good bit of housework to get going today, and some necessary but necessarily small amount of shopping to do as well, but I want to get this idea down first.

The Adjusted Ceiling Square of odd positive integer m is the least perfect square greater than m that is odd if m is congruent to 1 modulo 4, and is even if m is congruent to 3 (or -1) modulo 4.

When constructing ranges in the algorithm most recently discussed, then, one would set the greater square for the first range lower bound, c02, to be the Adjusted Ceiling Square of m. Then, for the next two ranges, the greater squares will be (c0+2)2 and (c0+4)2, and the values of where m falls within the three ranges thus generated will be the values of f(x), the characteristic polynomial, at x=0, 2, and 4.

I simply thought it was much more sensible to base the characteristic polynomial on ranges of differences of perfect squares that matched the even/odd polarity of the actual difference-of-squares form of any solutions of m, based on its being congruent to 1 or -1 modulo 4. Why base a characteristic polynomial algorithm on range values that are immediately apparently not candidates for “Fermat factorization”?

I shall give a report of my working through this when I actually do so – much later today!

Leave a Reply Cancel reply