# Algorithm of factor()

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 close merge delete

Sort by » oldest newest most voted

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))


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.

more

Continuing where tmotell left off, we can find more documentation at the following page: https://pari.math.u-bordeaux.fr/dochtml/html/Arithmetic_functions.html (https://pari.math.u-bordeaux.fr/docht...)

In particular, if you go to the the definition of factor(), you are sent (for integerts) to the definition of factorint() which gives in part:

"Factors the integer n into a product of pseudoprimes (see ispseudoprime), using a combination of the Shanks SQUFOF and Pollard Rho method,... Lenstra's ECM,... and MPQS,... as well as a search for pure powers."

( 2018-07-22 21:08:02 -0500 )edit

Looking down at the definition of ispseudoprime() we get:

"Checks whether x has no small prime divisors (up to 101 included) and is a Baillie-Pomerance-Selfridge-Wagstaff pseudo prime. Such a pseudo prime passes a Rabin-Miller test for base 2, followed by a Lucas test for the sequence (P,1), where P ≥ 3 is the smallest odd integer such that P^2 - 4 is not a square mod x."

This entry ends with the interesting statement:

"There are no known composite numbers passing the above test, although it is expected that infinitely many such numbers exist."

( 2018-07-22 21:08:28 -0500 )edit

As you can see, it's all quite complicated. I would suggest (and have suggested to myself) to look at one or two modern factorization algorithms if we are to show something of interest to our students. This appears to be a good rundown of a few relevant algorithms:

http://www.cs.columbia.edu/~rjaiswal/factoring-survey.pdf (http://www.cs.columbia.edu/~rjaiswal/...)

( 2018-07-22 21:08:41 -0500 )edit