ASKSAGE: Sage Q&A Forum - RSS feedhttps://ask.sagemath.org/questions/Q&A Forum for SageenCopyright Sage, 2010. Some rights reserved under creative commons license.Thu, 21 Nov 2019 16:43:49 +0100How to solve an equation over finite field?https://ask.sagemath.org/question/48835/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?Thu, 21 Nov 2019 13:41:43 +0100https://ask.sagemath.org/question/48835/how-to-solve-an-equation-over-finite-field/Answer by Emmanuel Charpentier for <p>I would like to solve an equation like</p>
<pre><code>solve( ((k^2)%17)==8,k)
</code></pre>
<p>or</p>
<pre><code>R = GF(17)
solve(R(k)^2==8,k)
</code></pre>
<p>or as math equation: $k^2 \equiv 8 \mod 17$ <br>
This would be true for e.g. $k=5$ <br>
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.</p>
<p>How can I solve such equation?</p>
https://ask.sagemath.org/question/48835/how-to-solve-an-equation-over-finite-field/?answer=48836#post-id-48836Methinks 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]Thu, 21 Nov 2019 13:51:27 +0100https://ask.sagemath.org/question/48835/how-to-solve-an-equation-over-finite-field/?answer=48836#post-id-48836Comment by maan for <p>Methinks it's trivlal:</p>
<pre><code>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]
</code></pre>
<p>Works because:</p>
<pre><code>sage: [u[0].parent() for u in L]
[Finite Field of size 17, Finite Field of size 17]
</code></pre>
https://ask.sagemath.org/question/48835/how-to-solve-an-equation-over-finite-field/?comment=48839#post-id-48839That only works with equations which have only one variable, right? ($k$ in example)Thu, 21 Nov 2019 14:52:50 +0100https://ask.sagemath.org/question/48835/how-to-solve-an-equation-over-finite-field/?comment=48839#post-id-48839Comment by Emmanuel Charpentier for <p>Methinks it's trivlal:</p>
<pre><code>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]
</code></pre>
<p>Works because:</p>
<pre><code>sage: [u[0].parent() for u in L]
[Finite Field of size 17, Finite Field of size 17]
</code></pre>
https://ask.sagemath.org/question/48835/how-to-solve-an-equation-over-finite-field/?comment=48841#post-id-48841Not 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.Thu, 21 Nov 2019 16:43:49 +0100https://ask.sagemath.org/question/48835/how-to-solve-an-equation-over-finite-field/?comment=48841#post-id-48841