# How to solve an equation over finite field?

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 close merge delete

Sort by » oldest newest most voted

Methinks it's trivlal:

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


Works because:

sage: [u.parent() for u in L]
[Finite Field of size 17, Finite Field of size 17]

more

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

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.