# Alfonso Cevallos. May 5 2015.
# Please report any mistakes.
# This week we work with Python numbers, and built-in elementary operations.
# Therefore the algorithms will NOT be as fast as in our analysis.
# The goal here is simply to understand the higher level idea of these algorithms.
import math
import os
import random
import time
def trim(A): #removes any leading zeros
while A[len(A)-1] == 0: A.pop()
return
def exgcd(a,b): #computes (g,x,y) such that gcd(a,b) = g = xa + yb
if a deg
while n <= deg: n = n*2
A = A + [0]*(n-len(A))
B = B + [0]*(n-len(B)) #here we correct the lengths of A and B
BB = 0 # this is the bound on the absolute value of the coefficients of f and g
for a in A:
if BB < abs(a): BB = abs(a)
for b in B:
if BB theRange
M = 2**L + 1
w = 2**(L/K) #this is a primitive n-th root of unity, as we proved in exercise 2
C = MultMod(A,B,w,M) #we use the modular multiplication
for i in range(n): # finally we map C back to Z[x]:
if 2*C[i]>M: C[i]=C[i]-M #large coefficients are mapped to negative values.
trim(C) #and we remove unnecessary zeros
return C
def Tests(): #we test with the polynomials given in exercise 4
A = [3,-4,3,5,0,0,0,0]
B = [-2,7,-5,2,0,0,0,0]
C = MultMod(A,B,2,17)
CC = Mult(A,B)
print "For the polynomials A = ", A
print "and B = ", B
print "The product in Z_17[x] is ", C
print "And the product in Z[x] is ", CC
Tests()