-
Notifications
You must be signed in to change notification settings - Fork 0
/
prime.py
119 lines (94 loc) · 2.98 KB
/
prime.py
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
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
import random
import operator
import functools
from math import gcd
SMALL_PRIMES = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29] # длина - 33 бита
SMALL_PRIMES_PRODUCT = functools.reduce(operator.mul, SMALL_PRIMES)
MR_TESTS = 25
def check_len(q, desired_size):
return len(bin(q)) - 2 == desired_size
def isprime(prime):
"""
источник: Маховенко. "Теоретическая криптография", стр. 166, алгоритм 7.7.1
:param prime: проверяемое на простоту число
:return: True - p простое, False - p составное
"""
if prime & 1 == 0:
return False
q = prime - 1
m = 0
while q & 1 == 0:
m += 1
q //= 2
s = q
r = 0
while r < MR_TESTS:
a = random.randint(2, prime - 2)
while gcd(a, prime) > 1:
a = random.randint(2, prime - 2)
b = pow(a, s, prime)
if b == 1:
continue
elif b == prime - 1:
r += 1
continue
for l in range(1, m):
c = pow(a, s * pow(2, l), prime)
if c == prime - 1:
r += 1
break
else:
return False
return True
def gen_odd(size):
q = random.randint(2 ** (size - 1), 2 ** size - 1)
if q & 1 == 0:
q += 1
return q
def gen_relatively_prime(size):
q = gen_odd(size)
while gcd(q, SMALL_PRIMES_PRODUCT) > 1 or q % 4 != 3:
q += 2
if not check_len(q, size):
q = gen_odd(size)
return q
def gen_big_prime(size):
"""
источник: https://pdfs.semanticscholar.org/873c/de422f7bc7903bfbaa3ff3e5477be92aa64a.pdf
авторы: Marc Joye, Pascal Paillier, Serge Vaudenay
'Efficient Generation of Prime Numbers'
3.2 Classical Generation Algorithms
функция генерирует простое число длины l бит с единичным старшим двоичным разрядом
:param size: количество бит
:return: простое l-битное число
"""
q = gen_relatively_prime(size)
while not isprime(q) or q % 4 != 1:
q += SMALL_PRIMES_PRODUCT
if not check_len(q, size):
q = gen_relatively_prime(size)
return q
def gen_small_prime(size):
q = gen_odd(size)
while not isprime(q) or q % 4 != 1:
q += 2
if not check_len(q, size):
q = gen_odd(size)
return q
def gen_prime(size):
return gen_small_prime(size) if size < 150 else gen_big_prime(size)
def factorize(n, func, *args):
divisors = {}
p = func(n, *args)
while not isprime(n) and p != -1:
# noinspection PyUnresolvedReferences
divisors[p] = divisors.get(p, 0) + 1
n //= p
p = func(n, *args)
if n > 1:
divisors[n] = divisors.get(n, 0) + 1
return divisors
if __name__ == '__main__':
from sys import argv
_size = int(argv[1])
print(gen_prime(_size))