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.Wed, 14 Nov 2018 22:41:29 +0100Computing the inverse in GF(p^k) using the extended euclides algorithmhttps://ask.sagemath.org/question/44283/computing-the-inverse-in-gfpk-using-the-extended-euclides-algorithm/For didactic purposes, I am trying to write my own function to compute the inverse in a finite field.
So far my code is like this:
# Extended Euclides Algorithm
def extended_euclides(a,b,quo=lambda a,b:a//b):
r0 = a; r1 = b
s0 = 1; s1 = 0
t0 = 0; t1 = 1
while r1 != 0:
q = quo(r0, r1)
r0, r1 = r1, r0 - q * r1
s0, s1 = s1, s0 - q * s1
t0, t1 = t1, t0 - q * t1
return r0, s0, t0
# Inverse in finite fields
def GF_inverse(elem):
"""
INPUT: element a from a finite field F_q
OUTPUT: inverse of the element
"""
GF = elem.parent()
f = GF.modulus() # defining polynomial of the field
ZpX = f.parent()
elem_bar = ZpX(elem) # representant of x in Zp[x]
r, inv_bar, _ = extended_euclides(elem_bar, f)
print(r)
assert(r == 1) # since Fq is a field, all elements are units
inv = GF(inv_bar) # elevate sbar
return inv
# EXAMPLE
GF9.<a> = GF(3^2)
elem = GF9(2*a+1)
inv = GF_inverse(elem)
print("The inverse of {} is {}".format(elem, inv))
assert(elem*inv == 1)
The idea why this should work is that $GF(p^k) = Zp[x] / (f)$ for $f\in Zp[x]$ an irreducible polynomial of degree $k$.
Therefore $elem$ is represented by $\bar{elem} + c*f$ for any $c\in Zp[x]$
So $inv * elem = 1 \implies \bar{inv} * \bar{elem} + c*f = 1 = gcd(\bar{elem}, f)$ (since $f$ is irreducible and $elem \ne 0$). And therefore a representative of the inverse is a bezoit coefficient.
The problem is that my code does not really work. The snippet above produces the following output:
2
The inverse of 2*a + 1 is a
Error in lines 15-15
Traceback (most recent call last):
File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1188, in execute
flags=compile_flags) in namespace, locals
File "", line 1, in <module>
AssertionError
What is going on? Is my understanding of the math wrong or my code?Wed, 14 Nov 2018 19:53:03 +0100https://ask.sagemath.org/question/44283/computing-the-inverse-in-gfpk-using-the-extended-euclides-algorithm/Answer by tmonteil for <p>For didactic purposes, I am trying to write my own function to compute the inverse in a finite field.</p>
<p>So far my code is like this:</p>
<pre><code># Extended Euclides Algorithm
def extended_euclides(a,b,quo=lambda a,b:a//b):
r0 = a; r1 = b
s0 = 1; s1 = 0
t0 = 0; t1 = 1
while r1 != 0:
q = quo(r0, r1)
r0, r1 = r1, r0 - q * r1
s0, s1 = s1, s0 - q * s1
t0, t1 = t1, t0 - q * t1
return r0, s0, t0
# Inverse in finite fields
def GF_inverse(elem):
"""
INPUT: element a from a finite field F_q
OUTPUT: inverse of the element
"""
GF = elem.parent()
f = GF.modulus() # defining polynomial of the field
ZpX = f.parent()
elem_bar = ZpX(elem) # representant of x in Zp[x]
r, inv_bar, _ = extended_euclides(elem_bar, f)
print(r)
assert(r == 1) # since Fq is a field, all elements are units
inv = GF(inv_bar) # elevate sbar
return inv
# EXAMPLE
GF9.<a> = GF(3^2)
elem = GF9(2*a+1)
inv = GF_inverse(elem)
print("The inverse of {} is {}".format(elem, inv))
assert(elem*inv == 1)
</code></pre>
<p>The idea why this should work is that $GF(p^k) = Zp[x] / (f)$ for $f\in Zp[x]$ an irreducible polynomial of degree $k$.</p>
<p>Therefore $elem$ is represented by $\bar{elem} + c*f$ for any $c\in Zp[x]$</p>
<p>So $inv * elem = 1 \implies \bar{inv} * \bar{elem} + c*f = 1 = gcd(\bar{elem}, f)$ (since $f$ is irreducible and $elem \ne 0$). And therefore a representative of the inverse is a bezoit coefficient.</p>
<p>The problem is that my code does not really work. The snippet above produces the following output:</p>
<pre><code>2
The inverse of 2*a + 1 is a
Error in lines 15-15
Traceback (most recent call last):
File "/cocalc/lib/python2.7/site-packages/smc_sagews/sage_server.py", line 1188, in execute
flags=compile_flags) in namespace, locals
File "", line 1, in <module>
AssertionError
</code></pre>
<p>What is going on? Is my understanding of the math wrong or my code?</p>
https://ask.sagemath.org/question/44283/computing-the-inverse-in-gfpk-using-the-extended-euclides-algorithm/?answer=44285#post-id-44285Apparently, though `r` is a unit in the polynomial ring, it is not necessarilly equal to `1`, but it is a polynomial of degree 0, so you can assert instead `r.is_unit()` and replace `inv = GF(inv_bar)` with `inv = GF(inv_bar)/GF(r)` or `inv = GF(inv_bar/GF.base_ring()(r))` if you do not want to rely on division in `GF` to redefine it.Wed, 14 Nov 2018 22:41:29 +0100https://ask.sagemath.org/question/44283/computing-the-inverse-in-gfpk-using-the-extended-euclides-algorithm/?answer=44285#post-id-44285