1 files changed, 141 insertions, 0 deletions
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"Число не является простым")