32 lines
848 B
Python
32 lines
848 B
Python
# Алгоритм Гельфонда-Шенкса дискретного логарифмирования (baby-step giant-step algoritm)
|
|
|
|
def order(a, p):
|
|
"""Возвращает порядок числа a по модулю числа p"""
|
|
i, x = 1, 0
|
|
while x != 1:
|
|
x, i = pow(a, i, p), i + 1
|
|
return i - 1
|
|
|
|
def gelfond(a, b, p, q=None):
|
|
if q == None: q = order(a, p)
|
|
s = (int)(q**.5) + 1
|
|
d = pow(a, p - 1 - s, p)
|
|
|
|
#print(f"q = {q}, s = {s}, d = {d}")
|
|
|
|
base = []
|
|
for i in range(0, s):
|
|
base.append(b % p * pow(d, i , p) % p)
|
|
|
|
#print(base)
|
|
|
|
for i in range(0, s):
|
|
try:
|
|
x = s*base.index(pow(a, i, p))+i
|
|
#print(f"x≡{x}mod({q})")
|
|
return x
|
|
except:
|
|
pass
|
|
|
|
if __name__ == "__main__":
|
|
print(gelfond(2, 7123, 1123)) |