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
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.
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."
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."
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/...)
Asked: 2014-08-14 12:12:50 +0100
Seen: 2,505 times
Last updated: Aug 14 '14
Copyright Sage, 2010. Some rights reserved under creative commons license. Content on this site is licensed under a Creative Commons Attribution Share Alike 3.0 license.
