blob: 5a7eae98d6ba9445153a160bd16c5e9f87ce7aef (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
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()
|
