Ask Your Question
0

Roots in a polynomial over $GF(2^8)$?

asked 2013-07-16 05:50:49 -0600

updated 2015-01-13 11:17:06 -0600

FrédéricC gravatar image

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

edit retag flag offensive close merge delete

3 answers

Sort by » oldest newest most voted
2

answered 2013-07-16 12:54:41 -0600

Luca gravatar image
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)]
edit flag offensive delete link more
1

answered 2013-07-16 09:54:52 -0600

Volker Braun gravatar image
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)]
edit flag offensive delete link more
0

answered 2013-07-16 14:01:57 -0600

updated 2013-07-16 14:12:29 -0600

Thanks, I need for this and for others polynomials. But Can the sage asnwer like $\beta^n$ ?

edit flag offensive delete link more

Comments

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

Volker Braun gravatar imageVolker Braun ( 2013-07-16 16:09:46 -0600 )edit

Thanks, I will be this and see what is the result.

Gustavo Banegas gravatar imageGustavo Banegas ( 2013-07-17 04:08:16 -0600 )edit

Hi, the beta is the exponential form of the root over $GF(2^8)$, Sage print the exponential form?

Gustavo Banegas gravatar imageGustavo Banegas ( 2013-07-17 10:02:14 -0600 )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: 2013-07-16 05:50:49 -0600

Seen: 178 times

Last updated: Jul 16 '13