1
$\begingroup$

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.

$\endgroup$
5
  • $\begingroup$ I think you answer is contained here $\endgroup$ – mikeazo Apr 17 '15 at 17:53
  • $\begingroup$ very much than you , you are indeed right ! $\endgroup$ – Lucian Tarna Apr 17 '15 at 19:04
  • $\begingroup$ do you know any language that can support such big numbers? (Java seems to not have an sqrt method for such a number, ruby same as java) $\endgroup$ – Lucian Tarna Apr 17 '15 at 19:05
  • $\begingroup$ python has native support for big integers, however you'll often find libraries providing big integer operations in any language. (such as Crypto++ for C++, Disclaimer: I contribute to Crypto++) $\endgroup$ – SEJPM Apr 17 '15 at 19:13
  • $\begingroup$ I see, thank you for your tip ! BC suggested by squeamish ossifrage seems to also do the trick nicely :P $\endgroup$ – Lucian Tarna Apr 17 '15 at 19:18
2
$\begingroup$

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
$\endgroup$
3
  • $\begingroup$ bc seems to be nice , i will give it a try , i have 1 more request from you , could you please write also the output of p=a-3457 and q=a+3457. Also could you please tell me if bc comes installed with linux or i must install it(i must do this a couple more times for other N's)? I love you very much btw ! $\endgroup$ – Lucian Tarna Apr 17 '15 at 19:16
  • $\begingroup$ @LucianTarna You could have figured that out yourself with a pencil and paper. If a ends in 31350 and x is 3457, then p and q are the same as a except one ends in 27893 and the other ends in 34807. You should find bc in most Linux systems; I know Debian includes it. $\endgroup$ – r3mainer Apr 17 '15 at 19:31
  • $\begingroup$ too many numbers, yes it was installed i recreated your calculations for all my needs :P . Thank you very much , for the steps you have to take and for suggesting BC to me :) ! $\endgroup$ – Lucian Tarna Apr 17 '15 at 19:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.