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

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

(limited to 'lab12')

diff --git a/lab12/lab12.py b/lab12/lab12.py
new file mode 100644
index 0000000..5a7eae9
--- /dev/null
+++ b/lab12/lab12.py
@@ -0,0 +1,77 @@
+from math import gcd, sqrt, log, exp
+
+
+def get_only_prime_divisors(n):
+    factors = []
+    if (n % 2 == 0):
+        factors.append(2)
+
+    while (n % 2 == 0):
+        n = n // 2
+
+    for i in range(3, int(sqrt(n)) + 1, 2):
+        if (n % i == 0):
+            factors.append(i)
+
+        while (n % i == 0):
+            n = n // i
+
+    if (n > 2):
+        factors.append(n)
+
+    return factors
+
+
+def erathosphene(n):
+    is_prime = [True] * n
+    p = 2
+    while p * p < n:
+        cur = p * p;
+        while cur < n:
+            is_prime[cur] = False;
+            cur += p;
+        while not is_prime[p + 1]:
+            p += 1;
+        p += 1
+    primes = []
+    for i, p in enumerate(is_prime):
+        if p:
+            primes.append(i)
+    return primes[2:]
+
+
+def get_factor_base(n):
+    m = sqrt(exp(sqrt(log(n) * log(log(n)))))
+    factor_base = erathosphene(int(m))
+    return factor_base
+
+
+def dixon_factorization(n):
+    factor_base = get_factor_base(n)
+    print("Фактор база: ", factor_base)
+    smooth_b = []
+    for b in range(int(sqrt(n)), n):
+        a = b ** 2 % n
+        for fact in factor_base:
+            f = fact ** 2 % n
+            if a == f:
+                smooth_b.append((b, fact))
+
+    factors = []
+    for a, fact in smooth_b:
+        factor = gcd(a - fact, n)
+        if factor != 1:
+            factors.append(factor)
+
+    return list(set(factors))
+
+
+def main():
+    print("Введите нечётное целое число n:")
+    n = int(input())
+    factors = dixon_factorization(n)
+    print(f"Простые множители {n}:", factors)
+
+
+if __name__ == "__main__":
+    main()
-- 
cgit v1.2.3