Let m=pq, where p and q are unknown odd prime numbers, be an integer we wish to factor.

Let c=ceil(sqrt(m)) be the integer ceiling of the square root of m.

Evaluate r_{1}=c^{2}-m. Evaluate r_{2}=(c+1)^{2}-m.

If either r_{1} or r_{2} are perfect squares, this leads to a quick factorization due to c^{2}-n^{2} being equal to (c+n)(c-n) for all c, n, and we can exit the process. Otherwise, keep going.

Now determine values of positive integers a and b such that x^{2}+ax+b will equal r_{1} when x=0, and will equal r_{2} when x=1. b will equal r_{1} and a will equal r_{2}-(r_{1}+1).

With a and b thus determined, the least positive value of x that makes x^{2}+ax+b a perfect square will be the value of x such that (c+x)^{2}-m will also be a perfect square, from which m=(c+x)^{2}-n^{2} will give a simple factorization of m.

I suspect this might not be a simpler problem than factorization by known methods – it might be equivalent to trial of different values of x; i.e., using simple trial-candidates-based implementation of Fermat’s difference-of-squares method. But I do not yet know that for sure. Someone may have an algorithm to determine straightforwardly the values of x for which x^{2}+ax+b is a perfect square, given a and b.

## Leave a ReplyCancel reply