3
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ $$282174 488599 599500 573849 980909 * 671998 030559 713968 361666 935769$$ $\endgroup$
    – Moo
    Commented Mar 2, 2019 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
    Commented Mar 2, 2019 at 13:23
  • 2
    $\begingroup$ Factorization using the Elliptic Curve Method/ it took a few seconds. $\endgroup$
    – Moo
    Commented Mar 2, 2019 at 13:25

1 Answer 1

Reset to default
1
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .