My Integer Factorization Study: The Enigma of the Modulus of Four


Relationships, relationships… a progress report, of sorts, although this still might qualify among Results Quite Elementary.

The eventual goal, of course, is when given m, a discrete semiprime we wish to factor, to find p and q.

Because m=pq=c2-r, there will be properties linking the (possibly not yet known) p and q with r. Some of these properties have to do with the fact that odd integers are congruent to either 1 or 3 modulo 4.

Looking at my table of randomly-generated discrete semiprimes that are the products of pairs of five- and six-decimal-digit prime numbers (I’m working with sizes I can handle easily, searching for generalizations that will be true for numbers of any size), here’s what I’m seeing now:

These relationships seem not to care much about whether the Ceiling Root is congruent to 0, 1, 2, or 3 modulo 4. Whenever m=pq is congruent to 1 modulo 4, r is congruent to either 0 or 3 modulo 4. Whenever m=pq is congruent to 3 modulo 4, r is congruent to 1 or 2 modulo 4.

Confirmed: Not earth-shaking, but useful in an algorithm, and worth my noticing it. It cuts down the possibilities by half, but that’s as simple a matter as just looking at m itself.

Back to the search!

Leave a Reply Cancel reply