Программа реализована на языке программирования Python

# -*- coding: utf-8 -*-

# создаёт кортеж (a,b) из чисел a и b

def zero(a,b):

if a is None: a=0

if b is None: b=0

return (a,b)

# суммирует списки почленно

def sum(a,b):

res = []

for x,y in map(zero,a,b):

res.append((x+y)%2)

return res

# разность многочленов

def dif(a,b):

res = []

for x,y in map(zero,a,b):

res.append(x-y)

return res

# произведение

def mul(a,b):

res = []

for i in range(0,len(b)):

temp = [0 for j in range(0,i)]

for r in a:

temp.append(r*b[i]%2)

res.append(temp)

return reduce(sum,res)

# деление (осторожно, рекурсия:-))

def dev(a,b):

while len(a)>0 and a[-1]==0:

del a[-1]

if len(a)<len(b):

return [a]

k = a[-1]/b[-1]

difference = len(a)-len(b)

for i in range(difference,len(a)):

a[i] = (a[i] - b[i-difference]*k)%2

while len(a)>0 and a[-1]==0:

del a[-1]

res = [(k, difference)] + dev(a,b) # recursion

return res

def devide(a,b):

res = dev(a,b) # деление рекурсивной функцией dev

# преобразование результата из функции dev в многочлен (список)

rem = res[-1] # остаток

polynom = []

if len(res)>1:

res = res[0:-1]

polynom = [0 for i in range(0,res[0][1]+1)] # res[0][1] - это степень старшего монома

for a,x in reversed(res):

polynom[x] = a

return (polynom, rem)

# НОД

def GCD(a,b):

res = devide(a,b)

r = res[-1]

while r!=[]:

a = b

b = r

res = devide(a,b)

r = res[-1]

return b

# многочлены для тестов

a = [1,1,1,1,1,0,1,1,0,0,1]

b = [1,0,1]

print devide(a[:],b[:]) # деление

print GCD(a[:],b[:]) # НОД