Factorization of large numbers

Question

In class we found this programming problem, and currently, we have no idea how to solve it.

The positive integer n is given. It is known that n = p * q, where p and q are primes, p<=q and |q-k*p|<10^5 for some given positive integer k. You must find p and q.

Input:

35 1
121 1
1000730021 9

Output:

5 * 7
11 * 11
10007 * 100003

It's not homework, we are just trying to solve some interesting problems. If you have some ideas, please post them here so we can try something, thanks.

Answer 1

For numbers the size you're talking about here, the fastest factoring method is (probably) to use the Sieve of Eratosthenes to generate primes up to approximately the square root of the number, then use trial division by those to find which one(s) are divisors.

Quite a few factoring methods have been invented for larger numbers. You might want to Google for "Fermat's factoring method", "Pollard Rho", "Brent's method", "Lenstra elliptical curve", "multiple polynomial quadratic sieve", and "general number field sieve". I've listed those in (roughly) ascending order of complexity and ability to factor larger numbers. It's open to question whether I should mention the general number field sieve or not though -- while it's the most efficient method currently known for factoring extremely large numbers, it's only useful on really big machines -- below about 110 digits or so, the MPQS is faster, but to factor the large numbers where the GNFS is faster, you need a lot more memory than a typical desktop or server can support (think of a terabyte of RAM as a minimum starting point, but probably more than that).

Answer 2

I have used the ECM method to factor large integer. It's one of the most efficient algorithms known. If you want to learn how the algorithm works, then you have a lot of reading to do, but if you want to utilize it to do your research, some people have implemented it. For instance you can get these open source packages: GMP-ECM for C/C++ or Pyecm for Python.

$ python
>>> import math
>>> import pyecm
>>> n = 1000730021
>>> list(pyecm.factors(n, False, False, 2 * math.log(math.log(n)), 1.0))
[10007, 100003]