# 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 # 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
################################################################## # 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() 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 ?