My Integer Factorization Study: A Slightly Cleaned-Up Result

Advertisements

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 r1=c2-m. Evaluate r2=(c+1)2-m.

If either r1 or r2 are perfect squares, this leads to a quick factorization due to c2-n2 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 x2+ax+b will equal r1 when x=0, and will equal r2 when x=1. b will equal r1 and a will equal r2-(r1+1).

With a and b thus determined, the least positive value of x that makes x2+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-n2 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 x2+ax+b is a perfect square, given a and b.

Leave a ReplyCancel reply