︠c88a673e-ef9b-4f75-9add-ce85a1b7b2b7︠
# There is three parts to this Programming Exercise. The first two parts consist of an introduction to Python and Sage Maths syntax.
# You can hide each part by using the small v arrow on your left at line 1 of each part.
# When using the Run button, only the code in the part that you are currently editing is executed. Each part is independent from the other.
︡69674fdb-b570-4d07-9ff4-0a4d83333239︡{"done":true}︡
︠ccded4e1-570f-4f15-8219-909d8e503ac7︠
##################################################################
# Python Basics (You can skip this if you're already familiar with the syntax and you can hide this part of the code using the small v arrow on your left at line 1) #
##################################################################
# We will mostly work with lists and functions, so you should be a bit comfortable with them.
######### Basics #########
# In Python, you don't need to declare what type a variable is when assigning it.
myvar = 3
mystring = "Galois"
myvar
mystring
# Basic maths operations on numbers are done as you would expect.
myvar + 5
myvar*7
myvar/2
myvar//2 # Integer division
myvar%2 # Modulo
myvar += 2
myvar
# You can also add strings as you would add numbers.
mystring += " Theory"
print(mystring)
# You can swap the variable names using the syntax "a,b = b,a"
myvar, mystring = mystring, myvar
######### Lists #########
# List are not restricted to elements of one type
mylist = [3, "Hello", 7.5]
# Lists are indexed from 0 to len(mylist)-1
mylist[0]
# mylist[4] # This gives an error
# You can add or remove stuff at the end of your list as you would expect using ".pop()" and ".append()"
mylist.pop() # Note that this returns the element removed, so that you could write "x = mylist.pop()"
mylist.append("World")
mylist.append(130)
mylist.append(178)
# You can extract slices of your list using [i:j] to get [mylist[i], mylist[i+1], ..., mylist[j-1]]. Omitting i means you want to start from 0 and omitting j means you go until the end of the list.
mylist
mylist[1:3]
mylist[1:]
mylist[:2]
# You can check whether an element is in your list using the key word "in".
3 in mylist # => True
"EPFL" in mylist # => False
# If an element is in your list, you can remove its first ocurrence using ".remove()" and get the index of first occurrence using ".index()"
# If the element is not in the list, ".remove()" will return an error.
mylist.index("World")
mylist.remove("World")
mylist
# You can delete the i-th element using "del"
del mylist[1]
mylist
# You can add an element at index i using ".insert()" and you can concatenate two lists using ".extend(other_list)"
mylist.insert(2,"Hello World")
mylist
######### For Loops, While Loops, If-Else statements #########
# You can get the integers in [a,b) using range(a,b).
rangelist = range(5,10)
# You can iterate over the elements of a list (without them being numbers) :
for number in rangelist:
if number in [3, 4]:
# "Break" terminates a for loop without executing the "else" clause.
break
elif number == 8:
print(number)
elif number%2 == 0:
continue # "Continue" starts the next iteration of the loop without executing the rest of the code.
print(number)
else:
pass # Does nothing
i = 0
while i < 3:
print(i)
i = i+1
######### Functions #########
# The syntax of a function is as follows. You can return a value using the key word "return"
def myfunction(var1,var2,var3):
pass
︡afc1c068-32f4-4738-be27-ed46f717fd69︡
︠573f0aac-95f4-4d93-9d18-348df6fae4d8︠
##################################################################
# Sage Math Introduction #
##################################################################
# SageMath Basics Reference : https://doc.sagemath.org/html/fr/tutorial/
# Commands for polynomials : http://doc.sagemath.org/html/en/reference/polynomial_rings/sage/rings/polynomial/polynomial_gf2x.html
# Commands for finite fields : http://doc.sagemath.org/html/en/reference/finite_rings/sage/rings/finite_rings/finite_field_constructor.html
# Our goal wil be to implement the Extended Euclidean Algorithm.
# First, we familiarize with the syntax of rings.
# The polynomial ring QQ[x] is defined as follow :
R. = PolynomialRing(QQ)
R
# Note that we can replace QQ by RR; or CC; or a finite field F with F = GF(p) for a prime p; or a finite field F with F. = GF(q), where q = p^n for a prime p and 'a' is a name for a primitive (p^n-1)-th root of unity; or any other fields that SageMath implements.
# We can define elements of QQ[x] and do basic operations with polynomials in a natural way :
f = x^2 + 1
g = 3*x^3 + 2*x - 5
# We can also define a polynomial using a vector of coefficients [a0, a1, ..., an] :
h = R([0, 1, 1, 0, 8])
h
# We can check in which ring they belong using ".parent()"
f.parent()
f*g
g%f
f/g # This works and gives automatically a rational element in the fraction field "FractionField(R)" of R "=" QQ[x].
(f/g).parent()
f+g
2*f
# You can get the list of coefficients [a0, a1, ..., an] using ".list()"
f.list()
g.list()
# We can check irreducibility using ".is_irreducible()"
f.is_irreducible() # => True
g.is_irreducible() # => False
# You can also use ".degree()", ".gcd(other_polynomial)" in a straightfoward way.
# You can get the factorization of a polynomial into irreducible factors of R using ".factor()" and get the list of factors with multiplicity using "list()"
g.factor()
list(g.factor())
# We can consider an ideal in R generated by some polynomials [f_1, ..., f_k]
I1 = Ideal(R, [f,g])
I1
I2 = Ideal(R, [f])
I2
# And quotient the ring R by this ideal.
S. = R.quotient_ring(I2) # We change the variable to avoid any ambiguity
S
# You can consider a polynomial p as an element of the quotient ring S using "S(p)" or "S([vector of coefficients])"
S(y^3 + 1) == S(-y+1) # => True
︡a784b0e7-93db-413e-a156-c5697b29ac8c︡
︠7af5ced5-8d95-48a3-b975-cd84e7844ca9︠
##################################################################
# Sage Math Exercises #
##################################################################
R. = PolynomialRing(QQ)
##################################################################
# Exercise 1 #
##################################################################
# The goal of this exercise is to implement the standard Euclidean Division for non-zero elements f, g of PolyRing, where PolyRing is a ring of polynomials over some field (for example, PolyRing = R "=" QQ[x] as above)
# The function must return a list [h, r] of polynomials such that f = gh + r, deg(r) < deg(g) (except when g = 0).
# This is the standard recursive algorithm, which follows from the proof (by induction) that h and r do exist.
# Two lines are missing. The exercise is to fill them.
def euclideanDivision(f,g, PolyRing):
degree_f = f.degree()
degree_g = g.degree()
f_coef = f.list()
f_lead_coef = f_coef[degree_f]
g_coef = g.list()
g_lead_coef = g_coef[degree_g]
if g == PolyRing([0]):
return (PolyRing([0]), f)
if degree_g > degree_f:
pass # return .... # MISSING
elif degree_g == degree_f:
h = g_lead_coef^(-1)*f_lead_coef
return (PolyRing([h]), f-g*h)
else:
pass # h1 = ... # MISSING
f_ = f - g*h1
h2, r = euclideanDivision(f_,g,PolyRing)
return [h1+h2,r]
# Test your function on a few examples.
##################################################################
# Exercise 2 #
##################################################################
# The goal of this exercise is to implement the Extended Euclidean Algorithm for non-zero elements f, g of PolyRing, where PolyRing is a ring of polynomials over some field (for example, PolyRing = R "=" QQ[x] as above).
# The function must return a triple [h, a, b], such that af + bg = h = gcd(f, g).
# Three lines are missing. The exercise is to fill them.
def extEuclidean(f,g, PolyRing):
r0, s0, t0 = f, 1, 0 # Multiple assignments
r1, s1, t1 = g, 0, 1
while r1 != PolyRing([0]):
pass # q = ... # MISSING
tmp_r, tmp_s, tmp_t = r1, s1, t1
pass # r1 = ... # MISSING
s1 = s0 - q*s1
t1 = t0 - q*t1
r0,s0,t0 = tmp_r, tmp_s, tmp_t
pass # return ... # MISSING
# Compare the output of "extEuclidean(f,g,R)" with the output of "f.xgcd(g)". What's the difference between both ?
range(10)
[x if x%2 == 0 else 1 for x in range(1,11)]
[[(x,y) if x%2 == 0 and y%2 == 0 else (1,1) for x in range(1,11)] for y in range(1,11)]
[1,2]+[3,4]
t = [1,2]
t.append(3)
2 in t
︡bc618b7b-e8fa-4128-a98c-7bcc5f6d0b5f︡
︠f033b086-c149-46d0-b33b-18d56b132458︠