05.模运算基础

title: 05. 模运算基础 tags: zk basic modular arithmetic congruence WTF zk教程第5讲：模运算基础 这一讲，我们将探讨模运算（Modular Arithmetic），我们在密码学领域会经常用到。 取模运算 取模运算（modulo）是一种整数运算，它通过对一个整数进行欧几里得除法获得余数，将结果限定在一个固定的范围内。 我们通常使用符号 $\text{mod}$ 来表示取模/取余，例如 $a \mod n$ 表示整数 $a$ 对 $n$ 进行取模运算，也就是 $a$ 除以 $n$ 的余数。这里 $n$ 被称为模数（modulus）。 先举几个简单的例子： $17 \mod 5 \equiv 2$ $25 \mod 7 \equiv 4$ $69 \mod 23 \equiv 0$ 我们可以用python实现取模运算： 我们使用的24小时计时法也是取模运算的应用。比如当前是12点，20小时过后是不是32点，而是 $32 \mod 24 \equiv 8$ 点。大家可以算一下，再过69小时是几点呢？ 同余 同余是一种关系，在密码学中...