07.费马小定理

title: 07. 费马小定理 tags: zk basic chinese remainder theorem WTF zk教程第7讲：费马小定理 之前我们介绍了模运算中的加减乘除，这一讲，我们介绍模幂和小费马定理。 模幂 模幂指对模进行的幂运算，在密码学中很常用： $$ b = a^c \mod{n} $$ 其中 $0 \le b < n$。 举个例子，给定 $(a, c, n) = (7, 5, 13)$，我们可以计算得到 $7^5=16807$，除以 $13$ 余 $11$，因此 $b = 11$。 当然，模幂也可以写为同余的形式： $$ b \equiv a^c \pmod{n} $$ 1.1 优化算法 $a^c$ 是个很大的数，很占计算机的内存，而模运算的结果 $0 \le b < n$，因此，我们可以运用模运算的特性节省计算时的内存。 根据模运算，有： $$ x \cdot y \mod{n} = (x \mod{n}) \cdot (y \mod{n}) \mod{n} $$ 如果 $x$ 和 $y$ 很大的时候，我们可以先进行取模运算，再进行乘法运算，节省内存。而幂...