My Integer Factorization Study: Tiny Eureka! (or Should I Say “Woof!”?)


I am finally barking up the correct tree, so to speak, and I have found the little squirrel I sought.

From the beginning, with gusto! (By the way, the relationship I am about to describe took a while to hammer out on paper, and a great deal longer to get right in Perl code.)

The task is the factorization of an odd integer m, which is the product of two distinct prime factors p and q (also both odd), and considered in the order such that p < q. Formulaically, m = pq.

Let s be the smallest integer greater than the square root of m. s is positive since p and q are distinct. Let r = s2-m. Now consider the positive integers c1 and c2 which satisfy p = s-c1 and q = s+c2. Let n = c2-c1.

From observing a large amount of data, I determined a relationship between r and the constant n as follows:

Let a = (q-p)2/4, which will always be an integer. Let b = n/2.

r = ab(p+q-b).

I am not at all certain of the likelihood of success, but for now, my approach to the integer factorization problem boils down to using the value of r = m – s2 and the relationship above to speed up the search for p and q. A place to start is to note that:

p+q = b+r/(ab). It may be a trivial relationship, due to the nature of the values of c1 and c2; I have not yet determined whether this is so.

Leave a Reply Cancel reply