Integer Factorization: Update for February 9, 2023


Let m be an odd discrete (square-free) semiprime whose prime factors are p and q, with p<q. Determine whether m is congruent to 1 or 3 modulo 4, or, equivalently, whether (m+1)/2 is odd or even, respectively. This must match whether (p+q)/2 is odd or even.

Let the Ceiling Root of m be the least positive integer c such that 1) c2>m and c is even or odd identically to (m+1)/2 (and (p+q)/2) being even or odd. Call the value of c2 thus obtained the Ceiling Square of m.

(In past blog posts, I have referred to c thus determined as the Adjusted Ceiling Square of m. Recently, however, I have discarded the “Adjusted” modifier since it makes total sense only to consider values of c+2n, n=0,1,2,…, when searching for squares that would lead to expressions of m as the difference between two perfect squares.)

It is a simple matter to determine if m is a perfect square, and thus to factor the number. If that is not the case, m=c2-r for some positive integer r. Again, if r is a perfect square, factorization comes simply. Attention then turns to integer values of m=c2-r where r is not a perfect square. The goal of my study is to come up with a general formula or approach for such cases.

My research over the past ten months has led me to discover the already known property that for the two possible factorizations of m, 1 times m and p times q, there correspond two expressions of m as the difference between two perfect squares: m=[(m+1)/2]2-[(m-1)/2]2=[(p+q)/2]2-[(q-p)/2]2. As I’ve indicated above, the greater squared term in both of these expressions has the same even/odd quality as the Ceiling Square and Ceiling Root.

Additionally, in the last day or so, I have been looking at what are probably easily-established relationships between the remainders obtained by looking at c, c+2, c+4, etc., squaring them, and subtracting m from the result. An example follows, and I wish only to add that I have looked at other examples to verify the uniformity of the behavior I am seeing:

4867 = 70^2-33   (33=2433^2-5919456)    (5919456=4728*1252
     = 72^2-317  (317=2433^2-5919172)   (5919172=4724*1253)
     = 94^2-63^2 (63^2=2433^2-5915520)  (5915520=4680*1264)
     = 2430^2-5900033 (5900033=2433^2-19456) (19556=8*2432)
     = 2432^2-5909757 (5909757=2433^2-9732)  (9732=4*2433)
     = 2434^2-2433^2

At the top of the example is the discrete semiprime m=4867 expressed in terms of its Ceiling Square and Remainder. At the bottom is the expression as a difference of squares given by the trivial factorization of 4867 as 1 times 4867. I have placed an intermediate step, with the non-trivial factorization’s perfect squares, in the middle as a tool to lead me in the search for patterns or clues as to some general formula to indicate when that non-trivial breakout will occur. But in every case, also, I have expressed the difference between the remainder and the lesser square in the trivial factorization expression as the product of two integers, the first of which decreases by 4 and the second of which increases by 1, as the greater square from which we compute the difference increases by 2.

I will further examine the properties of this integer product that is the remainder’s difference with [(m-1)/2]2 as my current best hope of promising revelations.

Leave a Reply Cancel reply