# 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.



##################################################################
# 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

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
# mylist # 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
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



##################################################################
# 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.<x> = 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.<a> = 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.<y> = 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



##################################################################
# Sage Math Exercises #
##################################################################

R.<x> = 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()

g_coef = g.list()

if g == PolyRing():
return (PolyRing(), f)

if degree_g > degree_f:
pass # return .... # MISSING
elif degree_g == degree_f:
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():
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