Processing math: 100%
Ask Your Question
1

How to solve a system of three polynomial equations over GF(28)

asked 6 years ago

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?

Preview: (hide)

1 Answer

Sort by » oldest newest most voted
1

answered 6 years ago

rburing gravatar image

updated 6 years ago

This is a system of linear equations, so you can write it as A(a0,a1,a2)=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}]
Preview: (hide)
link

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?

BSFU gravatar imageBSFU ( 6 years ago )

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

rburing gravatar imagerburing ( 6 years ago )

Your Answer

Please start posting anonymously - your entry will be published after you log in or create a new account.

Add Answer

Question Tools

2 followers

Stats

Asked: 6 years ago

Seen: 457 times

Last updated: Jan 26 '19