My Integer Factorization Study: Closer, but No Cigar (Squirrel?) Yet


Last night and this morning, I began looking at the behavior of the remainder r = s2 – m, where m is the product of distinct primes p and q, p < q, and s is the smallest integer greater than the square root of m. I began to build a kind of triangular table of values of r for p and q less than 100, taking care to space the horizontal and vertical values of the primes for the table axes of p and q values according to their relative positions on the number line.

Success, somewhat! I can see, and almost describe, a pattern that relates r to p and q. I currently believe that r is equal to [(q – p )/2]2 modulo some other linear equation in p and q, although I have not determined the coefficients of that linear function yet.

Once I have done so, and can compute r as a function of p and q, my work may not be over, I think. Inverting a function is tricky, especially one with a modulus operator. Different values of p and q can lead to a single value of r, and there will need to be a way to determine algorithmically which p and q to which r’s value leads will be the ones that produce m as their product.

I feel considerably closer to a “Eureka!” moment now, and definitely more confident that such a moment will come.

Or perhaps, since I’ve so far barked up some non-productive trees, my exclamation at that time should be “Woof!”

Leave a Reply Cancel reply