ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 26 Sep 2019 00:29:01 +0200How sage checks the irreducibility of a polynomial?https://ask.sagemath.org/question/47951/how-sage-checks-the-irreducibility-of-a-polynomial/ Hi, given a polynomial we can check whether its irreducibility via `.is_irreducible()` command. I wonder how sage checks it so fast even though the polynomial has large degree with large coefficients?Wed, 18 Sep 2019 01:19:57 +0200https://ask.sagemath.org/question/47951/how-sage-checks-the-irreducibility-of-a-polynomial/Comment by rburing for <p>Hi, given a polynomial we can check whether its irreducibility via <code>.is_irreducible()</code> command. I wonder how sage checks it so fast even though the polynomial has large degree with large coefficients?</p>
https://ask.sagemath.org/question/47951/how-sage-checks-the-irreducibility-of-a-polynomial/?comment=47954#post-id-47954Polynomial in one variable? Over which ring?Wed, 18 Sep 2019 11:02:51 +0200https://ask.sagemath.org/question/47951/how-sage-checks-the-irreducibility-of-a-polynomial/?comment=47954#post-id-47954Comment by captain for <p>Hi, given a polynomial we can check whether its irreducibility via <code>.is_irreducible()</code> command. I wonder how sage checks it so fast even though the polynomial has large degree with large coefficients?</p>
https://ask.sagemath.org/question/47951/how-sage-checks-the-irreducibility-of-a-polynomial/?comment=47957#post-id-47957A univariate polynomial over the integersWed, 18 Sep 2019 13:59:54 +0200https://ask.sagemath.org/question/47951/how-sage-checks-the-irreducibility-of-a-polynomial/?comment=47957#post-id-47957Comment by tmonteil for <p>Hi, given a polynomial we can check whether its irreducibility via <code>.is_irreducible()</code> command. I wonder how sage checks it so fast even though the polynomial has large degree with large coefficients?</p>
https://ask.sagemath.org/question/47951/how-sage-checks-the-irreducibility-of-a-polynomial/?comment=47970#post-id-47970In this case, a mixture between ntl and pari is used as i explained.Wed, 18 Sep 2019 22:36:05 +0200https://ask.sagemath.org/question/47951/how-sage-checks-the-irreducibility-of-a-polynomial/?comment=47970#post-id-47970Answer by tmonteil for <p>Hi, given a polynomial we can check whether its irreducibility via <code>.is_irreducible()</code> command. I wonder how sage checks it so fast even though the polynomial has large degree with large coefficients?</p>
https://ask.sagemath.org/question/47951/how-sage-checks-the-irreducibility-of-a-polynomial/?answer=47955#post-id-47955When such computation is fast, it depends on some optimized library (note that Sage can be seen as a bundle of optimized libraries behind a uniform Python interface), and that one depends on the type of polynomials. If you do:
sage: R.<x> = QQ[]
sage: P = R.random_element()
sage: P.is_irreducible??
You will see that `flint` is used.
If you do the same by replacing `QQ` with `GF(2)`, you will see that the `gf2x` library is used but for `GF(p)` with p>2, the `nmod_poly_is_irreducible` function is used and that one relies on `flint` as well. If you have polynomials over `ZZ`, then you will see that the `factor` method is used, and there you will see that `pari` is used when the degree of the polyomial is between 30 and 300, and `ntl` is used otherwise, and so on.
So, you have to see the source of the corresponding upstream program to see which algorithm and optimizations they are using.Wed, 18 Sep 2019 11:02:57 +0200https://ask.sagemath.org/question/47951/how-sage-checks-the-irreducibility-of-a-polynomial/?answer=47955#post-id-47955Comment by captain for <p>When such computation is fast, it depends on some optimized library (note that Sage can be seen as a bundle of optimized libraries behind a uniform Python interface), and that one depends on the type of polynomials. If you do:</p>
<pre><code>sage: R.<x> = QQ[]
sage: P = R.random_element()
sage: P.is_irreducible??
</code></pre>
<p>You will see that <code>flint</code> is used.</p>
<p>If you do the same by replacing <code>QQ</code> with <code>GF(2)</code>, you will see that the <code>gf2x</code> library is used but for <code>GF(p)</code> with p>2, the <code>nmod_poly_is_irreducible</code> function is used and that one relies on <code>flint</code> as well. If you have polynomials over <code>ZZ</code>, then you will see that the <code>factor</code> method is used, and there you will see that <code>pari</code> is used when the degree of the polyomial is between 30 and 300, and <code>ntl</code> is used otherwise, and so on.</p>
<p>So, you have to see the source of the corresponding upstream program to see which algorithm and optimizations they are using.</p>
https://ask.sagemath.org/question/47951/how-sage-checks-the-irreducibility-of-a-polynomial/?comment=47967#post-id-47967When I replace QQ with GF(p) I am getting "Object `P.is_irreducible` not found." error. What is the problem?Wed, 18 Sep 2019 21:41:20 +0200https://ask.sagemath.org/question/47951/how-sage-checks-the-irreducibility-of-a-polynomial/?comment=47967#post-id-47967Comment by tmonteil for <p>When such computation is fast, it depends on some optimized library (note that Sage can be seen as a bundle of optimized libraries behind a uniform Python interface), and that one depends on the type of polynomials. If you do:</p>
<pre><code>sage: R.<x> = QQ[]
sage: P = R.random_element()
sage: P.is_irreducible??
</code></pre>
<p>You will see that <code>flint</code> is used.</p>
<p>If you do the same by replacing <code>QQ</code> with <code>GF(2)</code>, you will see that the <code>gf2x</code> library is used but for <code>GF(p)</code> with p>2, the <code>nmod_poly_is_irreducible</code> function is used and that one relies on <code>flint</code> as well. If you have polynomials over <code>ZZ</code>, then you will see that the <code>factor</code> method is used, and there you will see that <code>pari</code> is used when the degree of the polyomial is between 30 and 300, and <code>ntl</code> is used otherwise, and so on.</p>
<p>So, you have to see the source of the corresponding upstream program to see which algorithm and optimizations they are using.</p>
https://ask.sagemath.org/question/47951/how-sage-checks-the-irreducibility-of-a-polynomial/?comment=47969#post-id-47969Could you please provide your exact code, it works for me:
sage: R.<x> = GF(5)[]
sage: P = R.random_element()
sage: P.is_irreducible()
FalseWed, 18 Sep 2019 22:35:24 +0200https://ask.sagemath.org/question/47951/how-sage-checks-the-irreducibility-of-a-polynomial/?comment=47969#post-id-47969Comment by captain for <p>When such computation is fast, it depends on some optimized library (note that Sage can be seen as a bundle of optimized libraries behind a uniform Python interface), and that one depends on the type of polynomials. If you do:</p>
<pre><code>sage: R.<x> = QQ[]
sage: P = R.random_element()
sage: P.is_irreducible??
</code></pre>
<p>You will see that <code>flint</code> is used.</p>
<p>If you do the same by replacing <code>QQ</code> with <code>GF(2)</code>, you will see that the <code>gf2x</code> library is used but for <code>GF(p)</code> with p>2, the <code>nmod_poly_is_irreducible</code> function is used and that one relies on <code>flint</code> as well. If you have polynomials over <code>ZZ</code>, then you will see that the <code>factor</code> method is used, and there you will see that <code>pari</code> is used when the degree of the polyomial is between 30 and 300, and <code>ntl</code> is used otherwise, and so on.</p>
<p>So, you have to see the source of the corresponding upstream program to see which algorithm and optimizations they are using.</p>
https://ask.sagemath.org/question/47951/how-sage-checks-the-irreducibility-of-a-polynomial/?comment=47972#post-id-47972I think I forgot to add " [] " because it works now, my bad.Thu, 19 Sep 2019 09:20:36 +0200https://ask.sagemath.org/question/47951/how-sage-checks-the-irreducibility-of-a-polynomial/?comment=47972#post-id-47972Comment by tmonteil for <p>When such computation is fast, it depends on some optimized library (note that Sage can be seen as a bundle of optimized libraries behind a uniform Python interface), and that one depends on the type of polynomials. If you do:</p>
<pre><code>sage: R.<x> = QQ[]
sage: P = R.random_element()
sage: P.is_irreducible??
</code></pre>
<p>You will see that <code>flint</code> is used.</p>
<p>If you do the same by replacing <code>QQ</code> with <code>GF(2)</code>, you will see that the <code>gf2x</code> library is used but for <code>GF(p)</code> with p>2, the <code>nmod_poly_is_irreducible</code> function is used and that one relies on <code>flint</code> as well. If you have polynomials over <code>ZZ</code>, then you will see that the <code>factor</code> method is used, and there you will see that <code>pari</code> is used when the degree of the polyomial is between 30 and 300, and <code>ntl</code> is used otherwise, and so on.</p>
<p>So, you have to see the source of the corresponding upstream program to see which algorithm and optimizations they are using.</p>
https://ask.sagemath.org/question/47951/how-sage-checks-the-irreducibility-of-a-polynomial/?comment=48069#post-id-48069ok, no pb.Thu, 26 Sep 2019 00:29:01 +0200https://ask.sagemath.org/question/47951/how-sage-checks-the-irreducibility-of-a-polynomial/?comment=48069#post-id-48069