Ask Your Question
0

How to solve an equation over finite field?

asked 2019-11-21 06:41:43 -0600

maan gravatar image

I would like to solve an equation like

solve( ((k^2)%17)==8,k)

or

R = GF(17)
solve(R(k)^2==8,k)

or as math equation: $k^2 \equiv 8 \mod 17$
This would be true for e.g. $k=5$
If I use the solve function above in sagemath I get an empty result $[]$ for first and 'self must be a numeric expression' for second.

How can I solve such equation?

edit retag flag offensive close merge delete

1 answer

Sort by » oldest newest most voted
1

answered 2019-11-21 06:51:27 -0600

Emmanuel Charpentier gravatar image

updated 2019-11-21 06:53:04 -0600

Methinks it's trivlal:

sage: R.<k>=PolynomialRing(GF(17))
sage: L=(k^2-8).roots();L
[(12, 1), (5, 1)]
sage: [u[0]^2 for u in L]
[8, 8]

Works because:

sage: [u[0].parent() for u in L]
[Finite Field of size 17, Finite Field of size 17]
edit flag offensive delete link more

Comments

That only works with equations which have only one variable, right? ($k$ in example)

maan gravatar imagemaan ( 2019-11-21 07:52:50 -0600 )edit
1

Not necessarily. But you have to be a bit more general. Consider:

sage: R.<k,l>=PolynomialRing(GF(17))
sage: Id=Ideal(k^2-8, l+k-3)
# Check for a dimension 0 (i. e. finite) set of solutions.
# This is unnecessary here, since we are working in a finite field.
sage: Id.dimension()
0
# Enumerate this finite set of solutions...
sage: Id.variety()
[{l: 15, k: 5}, {l: 8, k: 12}]

See § 9 of the book I pointed you to earlier (and that you should have read :-), as well as an undergrad-level algebra textbook.

Emmanuel Charpentier gravatar imageEmmanuel Charpentier ( 2019-11-21 09:43:49 -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-11-21 06:41:43 -0600

Seen: 41 times

Last updated: Nov 21