diff options
| author | Andrew Guschin <guschin.drew@gmail.com> | 2022-12-29 15:20:32 +0400 |
|---|---|---|
| committer | Andrew Guschin <guschin.drew@gmail.com> | 2022-12-29 15:20:32 +0400 |
| commit | 0be2be0a92f992bf8ee9eff701cb19658a1e7544 (patch) | |
| tree | 5d855004fd8cc067a594475c0a666eb01f0ceefa /lab12/lab12.py | |
| parent | 056f59346b727c9367998a423551eaba52854fce (diff) | |
Diffstat (limited to 'lab12/lab12.py')
| -rw-r--r-- | lab12/lab12.py | 77 |
1 files changed, 77 insertions, 0 deletions
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()
|