Ask Your Question
1

Algorithm of factor()

asked 2014-08-14 05:12:50 -0500

this post is marked as community wiki

This post is a wiki. Anyone with karma >750 is welcome to improve it.

Hi,

is there any documentation about how the Sage factor()-function works?

I want to use this with my students, and it would be nice if we could figure out why this function is so mich slower than for example the qsieve()-function or the ecm.factor()-function.

Thanks!

Thomas

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
2

answered 2014-08-14 06:06:18 -0500

tmonteil gravatar image

updated 2014-08-14 15:56:00 -0500

To access to the source code to some function or method, just use ??:

sage: factor??

So, you can see that this function transforms the entry into a Sage integer and calls the factor method, which can be inspected as follows:

sage: a = ZZ(2)
sage: a.factor??

You can see that Sage does a few sanity checks and then calls some optimized library. The default one is pari, but it is possible to use the algorithm option to select another library, e.g. ecm or qsieve.

So, if you want to see the details of the algorithm that is used by default in Sage, you need to look at the pari source code.

That said, a quick and dirty benchmark (using a few %timeit on random integers) seems to prove than pari is not slower than ecm, the following code:

sage: G = Graphics()
sage: for i in range(300):
....:     a = randint(2^i,2^(i+1))
....:     p = %timeit -o factor(a, algorithm='pari')
....:     e = %timeit -o factor(a, algorithm='ecm')
....:     G += point((i, p.best / e.best))

leads to the following picture:

pari-ecm.png

As you can see, pari and ecm behave identically for integers up to 40 bits, then, apart for some integers, pari is faster that ecm. As explained in the doc, ecm is faster for integers whith some small prime factors. So, it could be interesting to understand why the integers you are studying are much faster factorized by ecm than pari.

edit flag offensive delete link more

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

Stats

Asked: 2014-08-14 05:12:50 -0500

Seen: 144 times

Last updated: Aug 14 '14