28.二次剩余

title: 28. 二次剩余 tags: zk abstract algebra field number theory quadratic residue WTF zk 教程第 28 讲：二次剩余 在这一讲中，我们将介绍有限域 $Fp$ 下的二次剩余，涉及一个数的平方和平方根，在密码学和零知识证明中会经常用到。 二次剩余 二次剩余 是与模运算相关的一个概念。给定一个整数 $a$ 和正整数 $n$，如果存在整数 $x$ 使得 $x^2 \equiv a \pmod{n}$，则称 $a$ 是模 $n$ 的二次剩余。如果不存在这样的 $x$，则称 $a$ 是模 $n$ 的二次非剩余。 在本教程，我们仅介绍当模 $n$ 为奇质数 $p$ 的情况。 下面举个例子，以 $n = 7$ 为例，来看一下整数模7乘法群 $Z7^$ 中的二次剩余（不考虑0）： $1^2 \equiv 1 \pmod{7}$ $2^2 \equiv 4 \pmod{7}$ $3^2 \equiv 2 \pmod{7}$ $4^2 \equiv 2 \pmod{7}$ $5^2 \equiv 4 \pmod{7}$ $6...