Нахождение обратного по модулю def egcd if return else egcd return def

 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
"""
Нахождение обратного по модулю
"""
def egcd(a, b):
if a == 0:
return (b, 0, 1)
else:
g, y, x = egcd(b % a, a)
return (g, x - (b // a) * y, y)
def modinv(a, m):
g, x, y = egcd(a, m)
if g != 1:
raise Exception('modular inverse does not exist')
else:
return x % m
"""
Генерирования сообщение
"""
def id_generator(size=6, chars=string.ascii_lowercase):
return ''.join(random.choice(chars) for _ in range(size))
"""
Конвертирование int <---> bytes
"""
def int_to_bytes(x):
return x.to_bytes((x.bit_length() + 7) // 8, 'big')
def int_from_bytes(xbytes):
return int.from_bytes(xbytes, 'big')
'''
Euclidean algorithm.
Returns x, y, gcd(a, b):
ax + by = gcd(a, b).
'''
def euclidean(a, b):
x, xx, y, yy = 1, 0, 0, 1
while b:
q = a // b
a, b = b, a % b
x, xx = xx, x - xx*q
y, yy = yy, y - yy*q
return (x, y, a)
"""
Вычисление квадратного корня
"""
def isqrt(x):
"""
Вычисляет квадратный корень любого сколь угожно большего целого числа
Функция возвращает кортеж (a, r), где a ** 2 + r = x
a - наибольшее целое такое, что a**2 <= x, а r - это остаток
Если x - идельный квадрат, то остаток равен нулю
"""
N = 0 # Исходные данные на текущей итерации
a = 0 # Решение на текущей итерации
# Число будет обработано начиная с MSB, 2 бита за раз
# MSB - Most significant bit, старший бит, наиболее значимый бит
L = x.bit_length()
L += (L % 2) # Округление до следующего четного
for i in range(L, -1, -1):
# Следующие два бита
n = (x >> (2*i)) & 0b11
# Проверка на то, можем ли мы уменьшить остаток
if ((N - a*a) << 2) + n >= (a << 2) + 1:
b = 1
else:
b = 0
a = (a << 1) | b # Добавляем следующий бит решения
N = (N << 2) | n # Добавляем следующий бит исходных данных
return a, N-a*a