1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
|
def poly_print(f):
n, f_c = f
n = len(f_c) - 1
poly_str = ""
for i in range(len(f_c)):
cur_cf = f_c[i]
if not cur_cf:
continue
if cur_cf > 0:
sign = "+"
else:
cur_cf = -cur_cf
sign = "-"
poly_str += f"{sign} {cur_cf}x^{n - i} "
poly_str = poly_str[:len(poly_str) - 4]
if poly_str[0] == "+":
poly_str = poly_str[2:]
return poly_str
def poly_reduction(f):
n, f_c = f
i = 0
while i < len(f_c) and f_c[i] == 0:
n -= 1
i += 1
return n, f_c[i:]
def inverse(n, field):
x = 0
for _ in range(field):
if (n * x) % field != 1:
x += 1
else:
break
return x
def pdf(f, g, field):
m, f_c = f
n, g_c = g
f_c.reverse()
g_c.reverse()
q_c = [0] * (m + 1)
r_c = f_c
for k in range(m - n, -1, -1):
q_c[k] = (f_c[n + k] * inverse(g_c[n], field)) % field
for j in range(n + k - 1, k - 1, -1):
r_c[j] = (r_c[j] - q_c[k] * g_c[j - k]) % field
q_c.reverse()
r_c.reverse()
return (m, q_c), (n, r_c)
if __name__ == "__main__":
print("Введите коэффициенты первого многочлена:")
cf = list(map(int, input().split()))
f = poly_reduction((len(cf) - 1, cf))
print("Введите коэффициенты второго многочлена:")
cf = list(map(int, input().split()))
g = poly_reduction((len(cf) - 1, cf))
f_size = int(input("Введите размерность поля: "))
q, r = pdf(f, g, f_size)
print("Результат деления:", poly_print(q))
if r is not None:
print("Остаток от деления:", poly_print(r))
else:
print("Остатка нет")
|
