题目信息

技术要点

• 数学中离散对数知识的理解和应用

• 运用python将得到的字符串进行转换得到flag

解题思路

• 打开题目附件，能够得到一个python程序如下：
分析这段代码，可以看到，flag的位置信息其实已经告知，为m的指数位置，此题为经典的解一个DLP(离散对数问题)，因此只要求出最终的m值即可找到对应的flag信息。
发现题中的n = 2 ** 512， 所以phi(n) = 2 ** 511；即本题模数的欧拉函数具有smooth的性质，即其是由很多小素数乘积而来，所以可用Pohlig Hellman 算法来解决这个DLP，sage的discrete_log用的方法就包括Pohlig Hellman算法：
得到结果之后进行数字转字符串即可得到最终的flag信息

Flag

总结

• 经典离散对数问题的定义例如，对于n=7，Z/7Z是由3k构成的循环群，阶数是φ(7)=7−1=6，下面的每步推导都用到了上一步的模等结果，其中3是模7的原根(Primitive root)：

• 欧拉函数φ(n)表示1到n之间和n互素的整数的个数([15.d])，特别是对于素数p来说，φ(p)=p−1。

• 小于n且与n互素的集合是G={1,....,Pφ(n)}，例如当n=7，G={1,2,3,4,5,6}。

• 集合{… , a − 2n, a − n, a, a + n, a + 2n, …}构成了a对n的同余类(Congruence class, [15.c])

• G的元素对n的同余类全体构成了一个新的集合M，把M记做：Z/nZ。

• Z/nZ是一个阿贝尓群，直接从阿贝尓群的四个性质入手证明。

• Z/nZ是一个循环群，当且仅当n=1,2,4,pk或者2pk(k>0)

• p是一个素数,Z/pZ构成了一个循环群，生成元是g。

• 任意取一个整数k，gk属于Z/pZ，计算a=gk(mod p)，容易知道a也属于Z/pZ。

• 反之，已知a，要计算k=log(a)，称之为离散对数问题。

• 计算a=gk是容易的。

• 计算k=log(a)是困难的。

• 计算DLP问题的经典算法

• 纯粹数学，就其本质而言，是逻辑思想的诗篇。 👍💡