For my cryptography course, in context of RSA encryption, I was given a number $$N=189620700613125325959116839007395234454467716598457179234021$$

To calculate a private exponent in the encryption algorithm, I need to find the Euler Phi function of this number, and therefore I need to know its factorization, which most likely consists of 2 large numbers, as usually the case in RSA. We were allowed to use online tools or python, but none of them could handle a number this large. This makes me think I need to use some tricks to make the factorization process easier.

In a security course I took a while back, I had to factor a large number too, but there were about 5 other numbers you could use; if you had a gcd of 2 large numbers that wasn't equal to 1, you could use that information for the factoring. However, I don't see what tricks I can use in this case, and any help would be greatly appreciated.

  • 3
    $\begingroup$ $$282174 488599 599500 573849 980909 * 671998 030559 713968 361666 935769$$ $\endgroup$ – Moo Mar 2 '19 at 13:21
  • $\begingroup$ @Moo Thank you for your answer. May I ask what you used to factor this? What tools, what algorithms, and how long it took? $\endgroup$ – Marc Mar 2 '19 at 13:23
  • 2
    $\begingroup$ Factorization using the Elliptic Curve Method/ it took a few seconds. $\endgroup$ – Moo Mar 2 '19 at 13:25

The factorization was already found in the comments. This handy online tool takes 4.6 seconds to find the factorization $$N=282174 488599 599500 573849 980909\times 671998 030559 713968 361666 935769.$$


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.