Integer Factorization: Something Interesting (Tuesday, Feb. 7, 2023)


As phenomena of factorization go, this one is fascinating to me, though actually only a minor insight:

Consider the discrete semiprimes (i.e., square-free composite numbers with only two prime factors) within the odd positive integers, and the prime factors of each one of them, p and q, ordered so that p<q.

Last year, I began compiling a table of these discrete semiprimes, listing for each such number m=pq its factors, the value of (m+1)/2, the Ceiling Root c (the ceiling of the square root of m, with one added if necessary to make it odd or even as (m+1)/2 is odd or even), the Remainder r (difference c2-m so that m=c2-r), and the Ascent: the difference between (p+q)/2 and c, always even, which is the least positive integer a to be added to c so that (c+a)2-m is a perfect square, giving m the form m=(c+a)2-t2 for some t, and thus enabling factorization via the identity x2-y2=(x+y)(x-y). I placed the discrete semiprimes in order in the table of ascending q as the primary sort key, and ascending p less than q for each q as the secondary key: so I started with p=3, q=5; then p=3, q=7 followed by p=5, q=7; then p=3, q=11 and so on.

It seemed a sensible way to arrange the table to look at properties. For each value of q, the Ascent descends in value as p ascends. Bumpiness in this distribution seemed at least partially attributable to bumpiness in the distribution of prime numbers – including composite numbers other than discrete semiprimes would have smoothed out some of these bumps. Also, I confined my attention after a while to discrete semiprimes with positive, i.e. non-zero, ascents, since the factorization method I have developed and am refining treats perfect-square differences with the square of the Ceiling Root as a special, easily factored, case where nothing need be added to that value to permit it.

During the last couple of days, I have been wondering how to reverse-engineer, so to speak, relationships and patterns between Ceiling Roots/Ceiling Squares and their Remainders on the one end, and the Ascent values needed to bring about this “Fermat factorization” on the other end. And, to that end, I started looking at these table entries in order, and at the Remainder values I would get for c+a-2, the values right before factorization breaks, so to speak.

This is new information to me that I am conveying, and I apologize for any lack of eloquence in expressing it.

I saw a rather straightforward distribution of differences between these “next-to-last” remainders and the ones that gave factorization. Now, after some thought, I see that though they are smooth, they are perhaps less exciting than I thought them to be earlier today, but still worth recording as a minor finding. Here are my text editor notes. You will see that the first several entries provide difference values that increase linearly by four. But the step in the table from 11*29 to 3*31 breaks that smoothly-increasing streak. Still, this is some smoothness worth studying.

51 = 10^2-7^2 = 3*17
   =  8^2-13 (rem diff 36).

57 = 11^2-8^2 = 3*19
   =  9^2-24 (rem diff 40).

95 = 12^2-7^2 = 5*19
   = 10^2-5 (rem diff 44).

69 = 13^2-10^2 = 3*23
   = 11^2-52 (rem diff 48) = 9^2-12 (rem diff 88).

115 = 14^2-9^2 = 5*23
    = 12^2-29 (rem diff 52).

161 = 15^2-8^2 = 7*23
    = 13^2-8 (rem diff 56).

87 = 16^2-13^2 = 3*29
   = 14^2-109 (rem diff 60) = 10^2-13 (rem diff 156).

145 = 17^2-12^2 = 5*29
    = 15^2-80 (rem diff 64) = 13^2-24 (rem diff 120).

203 = 18^2-11^2 = 7*29
    = 16^2-53 (rem diff 68).

[261 = 19^2-10^2 = 9*29
     = 17^2-28 (rem diff 72).]

319 = 20^2-9^2 = 11*29
    = 18^2-5 (rem diff 76).

93 = 17^2-14^2 = 3*31
   = 15^2-132 (rem diff 64) = 11^2-28 (rem diff 168).

155 = 18^2-13^2 = 5*31
    = 16^2-101 (rem diff 68) = 14^2-41 (rem diff 128).

Leave a ReplyCancel reply