本文为人工撰写,仅使用生成式AI校对。
题目:
西小电注意到,第一周的题目中出现了若干神秘数字,并且他还发现这些神秘数字与神秘Flag有关,具体地,xx 是能够满足神秘式子 13x=114514mod 10000000000009913x=114514mod100000000000099 的最小整数,flag内容即为 xx ,你能帮助西小电求出正确的 Flag 吗?
“好奇怪的标题啊,BSGS是什么?北上广深吗?”
注意到BSGS为大步小步算法(baby-step giant-step),是丹尼尔·尚克斯发明的一种中途相遇算法,用于计算离散对数或者有限阿贝尔群的阶。1
代码如下:
import math
mod = 100000000000099
a = 13
b = 114514
n = mod - 1
m = math.isqrt(n) + 1
baby = {}
cur = 1
for j in range(m):
baby[cur] = j
cur = cur * a % mod
f = pow(a, -m, mod)
cur = b
for i in range(m):
if cur in baby:
print(i * m + baby[cur])
break
cur = cur * f % mod
输出:
18272162371285