Revision history [back]

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, it could be interesting to understand why the integers you are studying are much faster factorized by ecm than pari.

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:

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.

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:

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.

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:

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.