From 0be2be0a92f992bf8ee9eff701cb19658a1e7544 Mon Sep 17 00:00:00 2001
From: Andrew Guschin <guschin.drew@gmail.com>
Date: Thu, 29 Dec 2022 15:20:32 +0400
Subject: =?UTF-8?q?=D0=94=D0=BE=D0=B1=D0=B0=D0=B2=D0=BB=D0=B5=D0=BD=D1=8B?=
 =?UTF-8?q?=20=D0=BB=D0=B0=D0=B1=D1=8B=208-15?=
MIME-Version: 1.0
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 8bit

---
 lab8/lab8.py | 141 +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 141 insertions(+)
 create mode 100644 lab8/lab8.py

(limited to 'lab8/lab8.py')

diff --git a/lab8/lab8.py b/lab8/lab8.py
new file mode 100644
index 0000000..522e316
--- /dev/null
+++ b/lab8/lab8.py
@@ -0,0 +1,141 @@
+import math
+
+
+def get_poly_coeffs(a, n):
+    n += 1
+    coeffs = []
+    for j in range(n):
+        coeffs.append(math.factorial(n - 1) // (math.factorial(j) * math.factorial(n - 1 - j)))
+    for i in range(len(coeffs)):
+        coeffs[i] = coeffs[i] * (a ** i)
+    return coeffs
+
+
+def euler_func(value, power=1):
+    if power == 1:
+        return value - 1
+    else:
+        return value ** power - value ** (power - 1)
+
+
+def get_order(n, r):
+    pwr = n
+    cnt = 1
+    while pwr % r != 1:
+        pwr *= n
+        cnt += 1
+    return cnt
+
+
+def check_power(a, n):
+    powered_a = a
+    b = 1
+    while powered_a <= n:
+        if powered_a == n:
+            return True, b
+        powered_a *= a
+        b += 1
+    return False, 0
+
+
+def check_prime(e):
+    for i in range(2, int(math.sqrt(e))):
+        if e % i == 0:
+            return False
+    return True
+
+
+def get_all_divisors_brute(n):
+    for i in range(1, int(n / 2) + 1):
+        if n % i == 0:
+            yield i
+    yield n
+
+
+def get_only_prime_divisors(inp):
+    g = 1
+    prime_divisors = []
+    while g != inp:
+        for i in get_all_divisors_brute(inp):
+            if check_prime(i) and inp % i == 0 and i != 1:
+                inp = inp / i
+                prime_divisors.append(int(i))
+                break
+    return prime_divisors
+
+
+def get_euler(r):
+    p_d = get_only_prime_divisors(r)
+    euler_func_mult = []
+    for el_1 in p_d:
+        el_pw = 0
+        for el_2 in p_d:
+            if el_1 == el_2:
+                el_pw += 1
+        euler_func_mult.append((el_1, el_pw))
+
+    tmp = []
+    for euler_mult in set(euler_func_mult):
+        tmp.append(euler_func(*euler_mult))
+    euler_func_mult = tmp
+
+    phi_value = 1
+    for elem in euler_func_mult:
+        phi_value *= elem
+    return phi_value
+
+
+def check_polinom(a, n):
+    coeffs = get_poly_coeffs(a, n)
+    coeffs.remove(coeffs[0])
+    coeffs[-1] -= a
+    if not(coeffs[-1]):
+        coeffs.remove(coeffs[-1])
+    for cf in coeffs:
+        if cf % n:
+            return False
+    return True
+
+
+def find_smallest_order(n):
+    r = 1
+    while True:
+        r += 1
+        if math.gcd(r, n) != 1:
+            continue
+        o_r = get_order(n, r)
+        if o_r > (math.log2(n)) ** 2:
+            return r
+
+
+def aks_test(n):
+    r = find_smallest_order(n)
+    phi_r = get_euler(r)
+    border = math.floor(math.sqrt(phi_r) * math.log2(n))
+
+    for a in range(2, border):
+        is_powered, b = check_power(a, n)
+
+        if is_powered and b > 1:
+            return False
+
+        if 1 < math.gcd(a, n) < n and a <= r:
+            return False
+
+        if n <= r:
+            return True
+
+        if not check_polinom(a, n):
+            return False
+
+    return True
+
+
+if __name__ == "__main__":
+    print("Введите число n:")
+    n = int(input())
+    result = aks_test(n)
+    if result:
+        print(f"Число {n} является простым")
+    else:
+        print(f"Число не является простым")
-- 
cgit v1.2.3