10.欧拉定理

title: 10. 欧拉定理 tags: zk basic euler's theorem WTF zk教程第10讲：欧拉定理 欧拉定理是数论中的基本定理，表明在模运算中，对于任意整数与模数互质的情况下，该整数的欧拉函数次幂与模数同余于1，为RSA等加密算法提供了数学基础。这一讲，我们将介绍离散对数问题，单元阶，以及欧拉定理。 离散对数问题 离散数学问题（Discrete Logarithm Problem）是数学和密码学中的一个经典难题，其实就是说模运算求对数非常难。 给定素数 $p$，以及整数 $g, h \in \mathbb{Z}n^$，要求找到整数 $x$，使得: $$ g^x \equiv h \pmod{p} $$ 举个例子，对于 $(p, g, h) = (7, 3, 6)$，求满足等式 $3^x \equiv 6 \pmod{7}$ 的 $x$。我们尝试用穷举法来解决它： $$ 3^1 \equiv 3 \pmod{7} $$ $$ 3^2 \equiv 2 \pmod{7} $$ $$ 3^3 \equiv 6 \pmod{7} $$ 因此， $x = 3$ 满足...