1
$\begingroup$

My professor has given me an RSA factoring problem as an assignment. The given modulus is 30 decimal digits long. I have been searching a lot about factoring algorithms. But it has been quite a headache to choose one for my given requirements. Which algorithms give the best performance for 30 decimal digit numbers?

Note: So far I have read about Brute force approach and Quadratic Sieve. The latter is complex and the former time consuming.

Improve this question
$\endgroup$
3
  • $\begingroup$ Factoring a 30 digits number is an easy task. As an example, you can type Factorization(10263280077814176196883978050069); at magma.maths.usyd.edu.au/calc and see the result. You can change my number and see the decumentation for details of factorization methods. $\endgroup$
    – Meysam Ghahramani
    Apr 7 '20 at 7:13
  • $\begingroup$ @MeysamGhahramani Thank you for answering it. However in a night's search I have found pollard-rho to be the one that suits my requirement. nevertheless, once again thank you. $\endgroup$
    – DumpDaCode
    Apr 7 '20 at 8:28
  • 1
    $\begingroup$ Use Linux factor command? Also Wolfram alpha can do that for you. $\endgroup$
    – kelalaka
    Apr 7 '20 at 9:55
2
$\begingroup$

Which algorithms give the best performance for 30 decimal digit numbers?

30 decimal digits is 100 binary digits.

  • Trial division will require around $2^{50}$ divisions.
  • Pollard-Rho-Factoring will require around $2^{25}$ checks - this may be a good pick for you if you want to implement it yourself quickly and don't mind having to wait a bit on an optimized execution result.
  • Most decent quadratic sieve implementations will do this number within seconds.
  • Most ECM implementations will do that too. If you need something more optimized than Pollard-Rho, using ECM is probably a good pick. Refer to this database for optimal curve representation choices and the Handbook of Applied Cryptography (Ch14, PDF) for fast scalar multiplication strategies.
Improve this answer
$\endgroup$

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.