From 2490844ed0b6e8fb64af0b8a18cc2bdfd87690f5 Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Sun, 13 Nov 2022 11:45:59 +0400
Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D0=B0?=
 =?UTF-8?q?=20=D1=80=D0=B5=D0=B0=D0=BB=D0=B8=D0=B7=D0=B0=D1=86=D0=B8=D1=8F?=
 =?UTF-8?q?=20=D1=87=D0=B5=D1=82=D0=B2=D1=91=D1=80=D1=82=D0=BE=D0=B9=20?=
 =?UTF-8?q?=D0=BB=D0=B0=D0=B1=D1=8B?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 .gitignore            |  3 +++
 lab4/lab4.py          | 52 +++++++++++++++++++++++++++++++++++++++++++++++++++
 lab4/requirements.txt |  2 ++
 3 files changed, 57 insertions(+)
 create mode 100644 lab4/lab4.py
 create mode 100644 lab4/requirements.txt

diff --git a/.gitignore b/.gitignore
index 8aa37f4..3162b2c 100644
--- a/.gitignore
+++ b/.gitignore
@@ -3,6 +3,9 @@
 # Rust
 target
 
+# Python
+venv
+
 # LaTeX
 *.aux
 *.fls
diff --git a/lab4/lab4.py b/lab4/lab4.py
new file mode 100644
index 0000000..3f2ffa4
--- /dev/null
+++ b/lab4/lab4.py
@@ -0,0 +1,52 @@
+from sympy.polys.galoistools import gf_from_int_poly, gf_berlekamp
+from sympy.polys.domains import ZZ
+
+
+def poly_string(polynom):
+    tmp = []
+    for power, coeff in enumerate(polynom):
+        if coeff == 0:
+            continue
+        s = str(coeff) if coeff != 1 and power > 0 or power == 0 else ""
+        if power >= 1:
+            s += "x"
+        if power >= 2:
+            s += f"^{power}"
+        tmp.append(s)
+    return "(" + " + ".join(tmp) + ")"
+
+
+def is_prime(x):
+    for i in range(2, int(x ** 0.5) + 1):
+        if x % i == 0:
+            return False
+    return True
+
+
+def main():
+    p = input("Порядок p поля Z_p: ")
+    try:
+        p = int(p)
+    except ValueError:
+        print("Не удалось считать число")
+        return
+
+    if not is_prime(p):
+        print("Число p должно быть простым")
+        return
+
+    print("Введите коэффициенты многочлена [c_0 + c_1 * x + c_2 * x^2 + ...]:")
+    try:
+        c = map(int, input().split())
+    except ValueError:
+        print("Коэффициенты должны состоять только из цифр")
+        return
+
+    f = gf_from_int_poly(c, p)
+    print(f"Введённый многочлен над полем Z_{p}[x]: {poly_string(f)}")
+    factors = gf_berlekamp(f, p, ZZ)
+    print(" * ".join(map(poly_string, factors)))
+
+
+if __name__ == "__main__":
+    main()
diff --git a/lab4/requirements.txt b/lab4/requirements.txt
new file mode 100644
index 0000000..c8a04f6
--- /dev/null
+++ b/lab4/requirements.txt
@@ -0,0 +1,2 @@
+mpmath==1.2.1
+sympy==1.11.1
-- 
cgit v1.2.3