Ask Your Question
1

How to solve a system of three polynomial equations over $GF(2^8)$

asked 2019-01-26 10:58:31 -0600

I would like to solve the following system of three equations of three variables $a0,a1,a2$ over GF(2^8, name='x', modulus=x^8 + x^5 + x^3 + x + 1) :

a0+a1*x+a2*x^2=x^7+x^6+x^5+x^2+x
a0+a1*x^2+a2*x^4=x^7+x^6+x^5+x^2
a0+a1*x^3+a2*x^6=x^7+x^3+x^2+1

How can I do this?

edit retag flag offensive close merge delete

1 answer

Sort by ยป oldest newest most voted
1

answered 2019-01-26 12:25:43 -0600

rburing gravatar image

updated 2019-01-26 12:59:13 -0600

This is a system of linear equations, so you can write it as $A(a_0,a_1,a_2) = b$

var('x')
F.<x> = GF(2^8, modulus=x^8 + x^5 + x^3 + x + 1)
R.<a0,a1,a2> = PolynomialRing(F)
eqns = [a0+a1*x+a2*x^2 - (x^7+x^6+x^5+x^2+x), a0+a1*x^2+a2*x^4 - (x^7+x^6+x^5+x^2), a0+a1*x^3+a2*x^6 - (x^7+x^3+x^2+1)]
A = matrix(F, [[eqn.coefficient(b) for b in R.gens()] for eqn in eqns])
b = vector(F, [-eqn.constant_coefficient() for eqn in eqns])

and then you can solve it:

sage: A.solve_right(b)
(x^7 + x^2 + 1, x^7 + x^2 + 1, x^7 + x^2 + 1)

You can also do the following, because the ideal that these equations define is zero-dimensional:

sage: var('x')
x
sage: F.<x> = GF(2^8, modulus=x^8 + x^5 + x^3 + x + 1)
sage: R.<a0,a1,a2> = PolynomialRing(F)
sage: I = R.ideal([a0+a1*x+a2*x^2 - (x^7+x^6+x^5+x^2+x), a0+a1*x^2+a2*x^4 - (x^7+x^6+x^5+x^2), a0+a1*x^3+a2*x^6 - (x^7+x^3+x^2+1)])
sage: I.dimension()
0
sage: I.variety()
[{a1: x^7 + x^2 + 1, a2: x^7 + x^2 + 1, a0: x^7 + x^2 + 1}]
edit flag offensive delete link more

Comments

@rburing thank you so much for your answer. One more question. If the right side of my given equation generates from a loop like b0,b1,b2, then what will be the code?

math.mks@yandex.com gravatar imagemath.mks@yandex.com ( 2019-01-26 18:28:47 -0600 )edit

You're welcome. Can you show how you generate your equations (or left- and right-hand sides)?

rburing gravatar imagerburing ( 2019-01-27 06:55:09 -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

1 follower

Stats

Asked: 2019-01-26 10:58:31 -0600

Seen: 69 times

Last updated: Jan 26