# Algorithm for factoring a 30 decimal digit number

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.

• 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. – Meysam Ghahramani Apr 7 '20 at 7:13
• @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. – rajiv Apr 7 '20 at 8:28
• Use Linux factor command? Also Wolfram alpha can do that for you. – kelalaka Apr 7 '20 at 9:55

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