Integer Factorization Software: PARI/GP, Mathematica, and SymPy
We take a look at these three computations frameworks and see how they stack up against each other.
Join the DZone community and get the full member experience.
Join For FreeIn my previous post, I showed how changing one bit of a semiprime (i.e. the product of two primes) creates an integer that can be factored much faster. I started writing that post using Python with SymPy, but moved to Mathematica because factoring took too long.
SymPy vs. Mathematica
When I'm working in Python, SymPy lets me stay in Python. I'll often use SymPy for a task that Mathematica could do better just so I can stay in one environment. But sometimes efficiency is a problem.
SymPy is written in pure Python, for better and for worse. When it comes to factoring large integers, it's for worse. I tried factoring a 140-bit integer with SymPy, and killed the process after over an hour. Mathematica factored the same integer in 1/3 of a second.
Mathematica vs. PARI/GP
The previous post factors 200-bit semiprimes. The first example, N = pq where
p = 1078376712338123201911958185123
q = 1126171711601272883728179081277
took 99.94 seconds to factor using Mathematica. A random sample of 13 products of 100-bit primes and they took an average of 99.1 seconds to factor.
Using PARI/GP, factoring the value of N above took 11.4 seconds to factor. I then generated a sample of 10 products of 100-bit primes and on average they took 10.4 seconds to factor using PARI/GP.
So in these examples, Mathematica is several orders of magnitude faster than SymPy, and PARI/GP is one order of magnitude faster than Mathematica.
It could be that the PARI/GP algorithms are relatively better at factoring semiprimes. To compare the efficiency of PARI/GP and Mathematica on non-semiprimes, I repeated the exercise in the previous post, flipping each bit of N one at a time and factoring.
This took 240.3 seconds with PARI/GP. The same code in Mathematica took 994.5 seconds. So in this example, PARI/GP is about 4 times faster where as for semiprimes it was 10 times faster.
Python and PARI
There is a Python interface to PARI called cypari2. It should offer the convenience of working in Python with the efficiency of PARI. Unfortunately, the installation failed on my computer. I think SageMath interfaces Python to PARI but I haven't tried it.
Published at DZone with permission of John Cook, DZone MVB. See the original article here.
Opinions expressed by DZone contributors are their own.
Comments