Ask Your Question

How to solve an equation over finite field?

asked 2019-11-21 13:41:43 +0200

maan gravatar image

I would like to solve an equation like

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


R = GF(17)

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

answered 2019-11-21 13:51:27 +0200

Emmanuel Charpentier gravatar image

updated 2019-11-21 13:53:04 +0200

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


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

maan gravatar imagemaan ( 2019-11-21 14:52:50 +0200 )edit

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()
# 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 16:43:49 +0200 )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


Asked: 2019-11-21 13:41:43 +0200

Seen: 3,360 times

Last updated: Nov 21 '19