My Integer Factorization Study: A Small Spark of Excitement


I had an insight that might turn into an algorithmic method, after some further development and study.

Given an odd integer m that is the product of two prime numbers, as I have explained previously, we can find the Ceiling Root c as the integer ceiling of the square root of m, so that m=c2-r for some positive integer r. c2 is thus the least perfect square greater than m, and is important in what follows.

If r is itself a perfect square, then by the formula x2-y2=(x+y)(x-y) we have discovered a non-trivial factorization of m. This is not usually the case when the prime factors of m are large.

If we were to find or to know already p and q, the prime factors of m, we could write m = ((p+q)/2)2-((p-q)/2)2, which would lend itself to a non-trivial factorization. Not knowing p and q, however, we can still see that (p+q)/2 is usually greater than c, the Ceiling Root of m. But how much larger, and can we figure out how to get there by studying c and r?

I think we can. When r is not a perfect square, r lies between two perfect squares on the number line. So m=c2-r lies between c2-a2 and c2-(a-1)2.

Now find remainders r1 and r2 by expressing m=(c+1)2-r1 and m=(c+2)2-r2. What I think I am seeing – and I cannot be explicit because I have not yet algorithmically worked it out – is a value of the remainder that seems to increase quadratically while the distance between consecutive Ceiling Squares, as “the Ceiling is raised” by this approach, so to speak, increases linearly.

This is the part I need to work out further, and I am wondering if it might lead to a straightforward algorithm relating r, r2, and r3 by a quadratic polynomial – possibly making adjustments for the remainder crossing bounds between consecutive perfect square values, so as to figure out what value of (c+n)2 makes rn a perfect square. And as I’ve found many times before in this study, what looks interesting and exciting and seems to hold some promise may later turn out to not be a path out of the inscrutable tangles of integer factorization.

In fact, I know that outcome to be probable, but, as with all times before, I’m asking patient readers to stay tuned. As I’ve also said before, the most tantalizing feature of the unknown is that you also don’t know where or how you will come to know it.

Leave a Reply Cancel reply