Integer Factorization: The Ascent Is Just How Far Up You Go


It occurred to me to articulate a simple relationship between odd composite integer m=ab, where a and b are odd positive integers, its Ceiling Square and Ceiling Root, and its Ascent, which is the least number n, always even, that one must add to the Ceiling Root c so that (c+n)2-m is a perfect square.

Recall my definitions of Ceiling Square and Ceiling Root: They are the least perfect square c2 and its root c that are greater than m and are even or odd as (m+1)/2 is even or odd. Also recall that the properties of Fermat factorization and of the integers modulo 4 lead easily, as I have shown elsewhere, to the observation that all Fermat factorizations of m based on its expression m=s2-t2 have a value of s that is also even or odd as (m+1)/2 is even or odd. Note here that (m+1)/2 is, in fact, the value of s for the Fermat factorization of m as m times 1.

When odd positive m is congruent to 1 modulo 4, s in the above will be odd and t will be even. When m is congruent to 3 modulo 4, s will be even and t will be odd. Good factorization algorithms can and do use this information to cut the set of candidate factors or expressions in half.

The other simple fact, the main one I wrote this post intending to articulate, is that the Ascent of m corresponding to its factorization m=ab will simply be (a+b)/2-c where c is m’s Ceiling Root. In this case, (a+b)/2 is s in the Fermat factorization expression in the previous paragraph, and is even or odd as both (m+1)/2 and c are even or odd. This shows the Ascent will always be even, being the difference of two values that are congruent modulo 2.

Elementary, right? But I still felt it necessary to post it here, as a point of clarification.

Leave a ReplyCancel reply