CODEWITHSUNDEEP
pythonalgorithmfactorization
Titter
Titter

Reputation: 21

General number field sieve; factorizing 200 digit number

I'm fairly new in programming, and not really looking into the specifications of how things work. All I need is an efficient way of factorizing a 200 digit number. I've heard that General number field sieve is the best algorithm for that. Is there any code in python written that would implement this idea? Or are there any other alternatives? Any help would be appreciated

Upvotes: 2

Views: 5745

Answers (1)

btilly
btilly

Reputation: 46497

What are you factoring? General 200 digit numbers? In that case, use http://pari.math.u-bordeaux.fr/dochtml/gpman.html or some Python interface to it. (There are several, I know that http://www.sagemath.org/ can do it, and https://pypi.org/project/cypari/ gives you the interface without the rest.)

Those will usually be quick because they use a variety of approaches that are likely to find factors. Trial division for very small factors, Rabin-Miller to check for primality, elliptic curves for reasonably small factors, and so on.

On the other hand if you're looking to factor 200 digit numbers which show up in cryptography, you've got more work. They deliberately make their numbers unable to be factored by any of the fast things that you can try. As https://en.wikinews.org/wiki/Two_hundred_digit_number_factored indicates, this literally requires years of CPU time, so you would use highly optimized implementations (ie not written in Python), and distribute the majority of the work across multiple machines.

To actually perform such a factorization, I would suggest starting with https://en.wikipedia.org/wiki/General_number_field_sieve#Implementations and going from there.

If your goal is to understand how the factorization works, you're going to have a long path through a bunch of number theory literature. I'd recommend first trying to learn the quadratic sieve because it is both related and much simpler. (Therefore it is a shorter journey to understand, and will provide motivation as you tackle the harder one.) That sieve not as good as the general number theory sieve for 200 digit numbers, but it is better for 100 digit ones, so it is still pretty cool.

Upvotes: 2

Related Questions