Factorization of large numbers

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, pleas开发者_JAVA百科e post them here so we can try something, thanks.

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).

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]

n = p * q 
|q-k*p|<10^5

with n and k is given as input. Therefore

q-k*p=a 

with

-10^5<=a<=10^5

Multiplying q-k*p=a by q and substituting p*q by n gives

q^2-a*q-k*n=0

Solve this quadratic equation for each a with

-10^5<=a<=10^5` 

and check if q divides n. Solving a quadratic equation is can be done in polynomial time, and this is true for solving 2*10^5+1 equation. There are better algorithms for small values of n and k and also for large values of n and k of course.

As ypercube mentioned, one has only to check the equations where

a^2+4*k*n

is a square.

n = p * q and |q-k*p|<10^5 with n and k given as input. Therefore q-k*p=a, with -10^5<=a<=10^5 Multiplying q-k*p=a by q ans substituting p*q by n gives q^2-a*q-k*n=0. Solve this quadratic equation for each a with -10^5<=a<=10^5 and check if q divides n. Solving a quadratic equation is can be done in polynomial time, and this is true for solving 2*10^5+1 equation. There are better algorithms for small values of n and k

p is in the intervall

[(sqrt(k*n+2500000000)-50000)/k,(sqrt(k*n+2500000000)+50000)/k]

therefore you must only check 10^5/k values for p. q is in the intervall

[sqrt(k*n+2500000000)-50000,sqrt(k*n+2500000000)+50000]

which contains always about 10^5 inegers

The following C program is able to give you P and Q when you input N : https://github.com/michel-leonard/C-Quadratic-Sieve. The speed is about 170-bit RSA in second, the output is provided as string since numbers may be larger than 64-bit.

You can use the GUI-based version of YAFU from http://qurancode.com to try out larger example. The main benefit of YAFU is its adaptive nature where it switch algorithm automatically while factoring. Really the best and easier with the GUI edition for Windows 7/8/10.

Just click the Yellow PI symbol encircled by the red heart :)