ASKSAGE: Sage Q&A Forum - Individual question feedhttp://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Sun, 22 Jul 2018 21:08:41 -0500Algorithm of factor()http://ask.sagemath.org/question/23774/algorithm-of-factor/ 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!
ThomasThu, 14 Aug 2014 05:12:50 -0500http://ask.sagemath.org/question/23774/algorithm-of-factor/Answer by tmonteil for <p>Hi,</p>
<p>is there any documentation about how the Sage factor()-function works? </p>
<p>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.</p>
<p>Thanks!</p>
<p>Thomas</p>
http://ask.sagemath.org/question/23774/algorithm-of-factor/?answer=23775#post-id-23775To 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](http://ask.sagemath.org/upfiles/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](http://www.sagemath.org/doc/reference/interfaces/sage/interfaces/ecm.html), ``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``.
Thu, 14 Aug 2014 06:06:18 -0500http://ask.sagemath.org/question/23774/algorithm-of-factor/?answer=23775#post-id-23775Comment by mathcadd for <p>To access to the source code to some function or method, just use <code>??</code>:</p>
<pre><code>sage: factor??
</code></pre>
<p>So, you can see that this function transforms the entry into a Sage integer and calls the <code>factor</code> method, which can be inspected as follows:</p>
<pre><code>sage: a = ZZ(2)
sage: a.factor??
</code></pre>
<p>You can see that Sage does a few sanity checks and then calls some optimized library. The default one is <code>pari</code>, but it is possible to use the <code>algorithm</code> option to select another library, e.g. <code>ecm</code> or <code>qsieve</code>.</p>
<p>So, if you want to see the details of the algorithm that is used by default in Sage, you need to look at the <code>pari</code> source code.</p>
<p>That said, a quick and dirty benchmark (using a few <code>%timeit</code> on random integers) seems to prove than <code>pari</code> is not slower than <code>ecm</code>, the following code:</p>
<pre><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))
</code></pre>
<p>leads to the following picture:</p>
<p><img alt="pari-ecm.png" src="http://ask.sagemath.org/upfiles/pari-ecm.png"/></p>
<p>As you can see, <code>pari</code> and <code>ecm</code> behave identically for integers up to 40 bits, then, apart for some integers, <code>pari</code> is faster that <code>ecm</code>. As explained in <a href="http://www.sagemath.org/doc/reference/interfaces/sage/interfaces/ecm.html">the doc</a>, <code>ecm</code> 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 <code>ecm</code> than <code>pari</code>.</p>
http://ask.sagemath.org/question/23774/algorithm-of-factor/?comment=43117#post-id-43117As 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.pdfSun, 22 Jul 2018 21:08:41 -0500http://ask.sagemath.org/question/23774/algorithm-of-factor/?comment=43117#post-id-43117Comment by mathcadd for <p>To access to the source code to some function or method, just use <code>??</code>:</p>
<pre><code>sage: factor??
</code></pre>
<p>So, you can see that this function transforms the entry into a Sage integer and calls the <code>factor</code> method, which can be inspected as follows:</p>
<pre><code>sage: a = ZZ(2)
sage: a.factor??
</code></pre>
<p>You can see that Sage does a few sanity checks and then calls some optimized library. The default one is <code>pari</code>, but it is possible to use the <code>algorithm</code> option to select another library, e.g. <code>ecm</code> or <code>qsieve</code>.</p>
<p>So, if you want to see the details of the algorithm that is used by default in Sage, you need to look at the <code>pari</code> source code.</p>
<p>That said, a quick and dirty benchmark (using a few <code>%timeit</code> on random integers) seems to prove than <code>pari</code> is not slower than <code>ecm</code>, the following code:</p>
<pre><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))
</code></pre>
<p>leads to the following picture:</p>
<p><img alt="pari-ecm.png" src="http://ask.sagemath.org/upfiles/pari-ecm.png"/></p>
<p>As you can see, <code>pari</code> and <code>ecm</code> behave identically for integers up to 40 bits, then, apart for some integers, <code>pari</code> is faster that <code>ecm</code>. As explained in <a href="http://www.sagemath.org/doc/reference/interfaces/sage/interfaces/ecm.html">the doc</a>, <code>ecm</code> 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 <code>ecm</code> than <code>pari</code>.</p>
http://ask.sagemath.org/question/23774/algorithm-of-factor/?comment=43116#post-id-43116Looking 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."Sun, 22 Jul 2018 21:08:28 -0500http://ask.sagemath.org/question/23774/algorithm-of-factor/?comment=43116#post-id-43116Comment by mathcadd for <p>To access to the source code to some function or method, just use <code>??</code>:</p>
<pre><code>sage: factor??
</code></pre>
<p>So, you can see that this function transforms the entry into a Sage integer and calls the <code>factor</code> method, which can be inspected as follows:</p>
<pre><code>sage: a = ZZ(2)
sage: a.factor??
</code></pre>
<p>You can see that Sage does a few sanity checks and then calls some optimized library. The default one is <code>pari</code>, but it is possible to use the <code>algorithm</code> option to select another library, e.g. <code>ecm</code> or <code>qsieve</code>.</p>
<p>So, if you want to see the details of the algorithm that is used by default in Sage, you need to look at the <code>pari</code> source code.</p>
<p>That said, a quick and dirty benchmark (using a few <code>%timeit</code> on random integers) seems to prove than <code>pari</code> is not slower than <code>ecm</code>, the following code:</p>
<pre><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))
</code></pre>
<p>leads to the following picture:</p>
<p><img alt="pari-ecm.png" src="http://ask.sagemath.org/upfiles/pari-ecm.png"/></p>
<p>As you can see, <code>pari</code> and <code>ecm</code> behave identically for integers up to 40 bits, then, apart for some integers, <code>pari</code> is faster that <code>ecm</code>. As explained in <a href="http://www.sagemath.org/doc/reference/interfaces/sage/interfaces/ecm.html">the doc</a>, <code>ecm</code> 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 <code>ecm</code> than <code>pari</code>.</p>
http://ask.sagemath.org/question/23774/algorithm-of-factor/?comment=43115#post-id-43115Continuing where tmotell left off, we can find more documentation at the following page:
https://pari.math.u-bordeaux.fr/dochtml/html/Arithmetic_functions.html
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."Sun, 22 Jul 2018 21:08:02 -0500http://ask.sagemath.org/question/23774/algorithm-of-factor/?comment=43115#post-id-43115