Knowing N and a relationship between the 2 prime numbers(p and q) find p and q generated with RSA

Question

Let there be $p$ and $q$, 2 prime numbers for which the following relationship is true: $|p-q| < 2 \cdot N^{1/4}$.

The algorithm first generates the prime number $p$, then it generates $q$ close to $p$.

Knowing $q . p = N$. Find $q$ and $p$ for a given $N$.

I need to find $q$ and $p$ with $N =$10032208350557943814105597845620406371345920597417482932110446913151981999180640918053219164307546244408084705597234965779578614627312470238828230794195121161504453265291029543974898855236458038744675074627598451711003185766090909136298189825840695475328299227300586950455181974651063674776182896917822888950487755744661676679756828257894545108443585364392100199243341946769241912665270871651

Could someone explain the steps needed to be taken in order to solve this problem, or if there is an on-line big number calculator for such a big $N$ ?

The algorithm that this tries to mimic is RSA.

Answer 1

To summarize the factorization method briefly:

1. Substitute $p$ and $q$ with $(a+x)$ and $(a-x)$, where $a = (p+q)/2$.

2. That gives you the formula $N = (a+x)(a-x) = a^2-x^2$.

3. If $x$ is much smaller than $a$, then $N$ is very close to $a^2$, so $\sqrt N = a - \epsilon$ (for some small $\epsilon$)

4. So all you need to do is find the square root of $N$, round it up to the next integer and use this as a starting point from which to test for values of $a$ (i.e. $a_0 = \lceil{\sqrt N}\rceil$, $a_n = a_0 + n$).

5. For each value of $a$, calculate $x = \sqrt{a^2 - N}$. If you get an integer result for $x$, then you know both $a$ and $x$, so you know $p$ and $q$ and you're done.

Here's how I factored your value of $N$ in one minute using bc:

scale=8
n=10032208350557943814105597845620406371345920597417482932110446913151\
98199918064091805321916430754624440808470559723496577957861462731247\
02388282307941951211615044532652910295439748988552364580387446750746\
27598451711003185766090909136298189825840695475328299227300586950455\
18197465106367477618289691782288895048775574466167667975682825789454\
5108443585364392100199243341946769241912665270871651
sqrt(n)
31673661535348172963221610054843350154949051823868180694892016044894\
46429562275302313725942349754966331316600912978830241757407329652020\
786250572524093040703488810989670331501373924060093009031349.9999999\
9
a=31673661535348172963221610054843350154949051823868180694892016044894\
46429562275302313725942349754966331316600912978830241757407329652020\
786250572524093040703488810989670331501373924060093009031349+1
a*a-n
11950849
sqrt(11950849)
3457.00000000
p=a-3457
q=a+3457
p*q
10032208350557943814105597845620406371345920597417482932110446913151\
98199918064091805321916430754624440808470559723496577957861462731247\
02388282307941951211615044532652910295439748988552364580387446750746\
27598451711003185766090909136298189825840695475328299227300586950455\
18197465106367477618289691782288895048775574466167667975682825789454\
5108443585364392100199243341946769241912665270871651
p*q==n
1