Ask Your Question
1

Algorithm of factor()

asked 2014-08-14 12:12:50 +0100

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 13:06:18 +0100

tmonteil gravatar image

updated 2014-08-14 22:56:00 +0100

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

Comments

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."

mathcadd gravatar imagemathcadd ( 2018-07-23 04:08:02 +0100 )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."

mathcadd gravatar imagemathcadd ( 2018-07-23 04:08:28 +0100 )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/...)

mathcadd gravatar imagemathcadd ( 2018-07-23 04:08:41 +0100 )edit

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 12:12:50 +0100

Seen: 2,405 times

Last updated: Aug 14 '14