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.Wed, 01 Mar 2017 12:45:26 -0600Roots in a polynomial over $GF(2^8)$?http://ask.sagemath.org/question/10355/roots-in-a-polynomial-over-gf28/Hi,
I have a polynomial $x^8+x^7+x^5+x^3+1$ and I want to find the roots of this polynomial over $GF(2^8)$?
In the paper of Patrick Ekdahl and Thomas Johansson about a new version of SNOW they used this roots ($\beta^{23}, \beta^{48}, \beta^{239}$ and $\beta^{245}$, but I want all roots for this polynomial.
Thanks Tue, 16 Jul 2013 05:50:49 -0500http://ask.sagemath.org/question/10355/roots-in-a-polynomial-over-gf28/Answer by dan_fulea for <p>Hi,
I have a polynomial $x^8+x^7+x^5+x^3+1$ and I want to find the roots of this polynomial over $GF(2^8)$?
In the paper of Patrick Ekdahl and Thomas Johansson about a new version of SNOW they used this roots ($\beta^{23}, \beta^{48}, \beta^{239}$ and $\beta^{245}$, but I want all roots for this polynomial.</p>
<p>Thanks </p>
http://ask.sagemath.org/question/10355/roots-in-a-polynomial-over-gf28/?answer=36778#post-id-36778
If $b$ is a root (in some field of characteristic two) of a polynomial
defined over the prime field GF(2), then $b$, $b^2 = F(b)$, $b^4=F^2(b), b^8=F^3(b)$, and so on
are also roots. Here, $F$ is the Frobenius map.
So if $\beta^{23}$ is in the list, then $F(\beta^{23})=(\beta^{23})^2=\beta^{46}$ should be also on the list.
So i suspected some typo first. At some point, i decided to look for the cited data. The net gave me
an article with the following data:
<<<
To be more precise, the feedback polynomial of SNOW 2.0 is given by
$$\pi(x) = \alpha x^{16}+x^{14} + \alpha^{-1} x^5 +1\in F_{2^{32}}[x]\ ,$$
where $\alpha$ is a root of $x^4 + \beta^{23}x^3 + \beta^{245}x^2 +\beta^{48} x +\beta^{239}\in F_{2^8}[x]$,
and $\beta$ is a root of $x^8 + x^7 + x^5 + x^3 + 1\in\mathbb{F}_{2}[x]$ .>>>
In the wish from the post we do not have the information, that $\beta$ is a root of $P$.
But we have the other information, that $\beta^{23}, \beta^{245},\beta^{48},\beta^{239}$
are roots of $P$.
This is false, since with $\beta$ we have the other roots $\beta^n$ for n among
sage: print [ 23*2^k % 255 for k in [0..7] ]
[23, 46, 92, 184, 113, 226, 197, 139]
And we miss 245, 48, 239.Wed, 01 Mar 2017 12:45:26 -0600http://ask.sagemath.org/question/10355/roots-in-a-polynomial-over-gf28/?answer=36778#post-id-36778Answer by Gustavo Banegas for <p>Hi,
I have a polynomial $x^8+x^7+x^5+x^3+1$ and I want to find the roots of this polynomial over $GF(2^8)$?
In the paper of Patrick Ekdahl and Thomas Johansson about a new version of SNOW they used this roots ($\beta^{23}, \beta^{48}, \beta^{239}$ and $\beta^{245}$, but I want all roots for this polynomial.</p>
<p>Thanks </p>
http://ask.sagemath.org/question/10355/roots-in-a-polynomial-over-gf28/?answer=15245#post-id-15245Thanks, I need for this and for others polynomials.
But Can the sage asnwer like $\beta^n$ ? Tue, 16 Jul 2013 14:01:57 -0500http://ask.sagemath.org/question/10355/roots-in-a-polynomial-over-gf28/?answer=15245#post-id-15245Comment by Volker Braun for <p>Thanks, I need for this and for others polynomials.
But Can the sage asnwer like $\beta^n$ ? </p>
http://ask.sagemath.org/question/10355/roots-in-a-polynomial-over-gf28/?comment=17273#post-id-17273Whats beta? A multiplicative unit? That is not unique, and Sage doesn't know your choice. You can solve the discrete log with beta.log(a^5 + a + 1), say.Tue, 16 Jul 2013 16:09:46 -0500http://ask.sagemath.org/question/10355/roots-in-a-polynomial-over-gf28/?comment=17273#post-id-17273Comment by Gustavo Banegas for <p>Thanks, I need for this and for others polynomials.
But Can the sage asnwer like $\beta^n$ ? </p>
http://ask.sagemath.org/question/10355/roots-in-a-polynomial-over-gf28/?comment=17269#post-id-17269Thanks, I will be this and see what is the result.Wed, 17 Jul 2013 04:08:16 -0500http://ask.sagemath.org/question/10355/roots-in-a-polynomial-over-gf28/?comment=17269#post-id-17269Comment by Gustavo Banegas for <p>Thanks, I need for this and for others polynomials.
But Can the sage asnwer like $\beta^n$ ? </p>
http://ask.sagemath.org/question/10355/roots-in-a-polynomial-over-gf28/?comment=17268#post-id-17268Hi, the beta is the exponential form of the root over $GF(2^8)$, Sage print the exponential form? Wed, 17 Jul 2013 10:02:14 -0500http://ask.sagemath.org/question/10355/roots-in-a-polynomial-over-gf28/?comment=17268#post-id-17268Answer by Luca for <p>Hi,
I have a polynomial $x^8+x^7+x^5+x^3+1$ and I want to find the roots of this polynomial over $GF(2^8)$?
In the paper of Patrick Ekdahl and Thomas Johansson about a new version of SNOW they used this roots ($\beta^{23}, \beta^{48}, \beta^{239}$ and $\beta^{245}$, but I want all roots for this polynomial.</p>
<p>Thanks </p>
http://ask.sagemath.org/question/10355/roots-in-a-polynomial-over-gf28/?answer=15244#post-id-15244 sage: _.<x> = GF(2^8, 'a')[]
sage: P = x^8 + x^7 + x^5 + x^3 + 1
sage: P.roots()
[(a^5 + a + 1, 1),
(a^6 + a^5 + a^4 + 1, 1),
(a^6 + a^5 + a^4 + a^2 + a, 1),
(a^6 + a^5 + a^4 + a^3 + a, 1),
(a^7 + a^5 + a^2 + 1, 1),
(a^7 + a^5 + a^3 + a, 1),
(a^7 + a^5 + a^4, 1),
(a^7 + a^6 + a^5, 1)]
Tue, 16 Jul 2013 12:54:41 -0500http://ask.sagemath.org/question/10355/roots-in-a-polynomial-over-gf28/?answer=15244#post-id-15244Answer by Volker Braun for <p>Hi,
I have a polynomial $x^8+x^7+x^5+x^3+1$ and I want to find the roots of this polynomial over $GF(2^8)$?
In the paper of Patrick Ekdahl and Thomas Johansson about a new version of SNOW they used this roots ($\beta^{23}, \beta^{48}, \beta^{239}$ and $\beta^{245}$, but I want all roots for this polynomial.</p>
<p>Thanks </p>
http://ask.sagemath.org/question/10355/roots-in-a-polynomial-over-gf28/?answer=15242#post-id-15242 sage: AA.<x> = AffineSpace(GF(2^8, 'a'), 1)
sage: S = AA.subscheme(x^8 + x^7 + x^5 + x^3 + 1)
sage: S.rational_points()
[(a^5 + a + 1),
(a^6 + a^5 + a^4 + 1),
(a^6 + a^5 + a^4 + a^2 + a),
(a^6 + a^5 + a^4 + a^3 + a),
(a^7 + a^5 + a^2 + 1),
(a^7 + a^5 + a^3 + a),
(a^7 + a^5 + a^4),
(a^7 + a^6 + a^5)]
Tue, 16 Jul 2013 09:54:52 -0500http://ask.sagemath.org/question/10355/roots-in-a-polynomial-over-gf28/?answer=15242#post-id-15242