My Integer Factorization Study: Boiling It Down


It now seems that the task at hand is this: Given two linear equations with integer coefficients:

y1 = a1x + b1, and y2 = a2x + b2,

find the integer values of x, if any, where y1 is an integer multiple of y2.

y1 = n*y2 when x = (b2n – b1)/(a1 – a2n).

Currently, lacking insight, it seems finding n is no easier than finding x. But I am not yet giving up. For m = pq where p and q are distinct odd primes, p < q, and m = s2 – r where s is the smallest integer greater than the square root of m, factorization of m will reduce to finding integer values of x producing values of pairs of linear equations as above, where a1 = s, a2 = -1, b1 = -r, and b2 = s. If we consider p = s – c1 and q = s + c2 for positive integers c1 and c2, finding positive integer x such that y2 divides y1 will give us c1 = x and c2 = y1/y2 and, through this, the factorization of m.

Leave a Reply Cancel reply