相关数学基础知识 发表于 2024-03-25 阅读次数： 本文字数： 230 阅读时长 ≈ 1 分钟 Rabin攻击首先引出二次剩余和欧拉准则，欧拉准则的证明又设计涉及费马小定理，下面一一说明。 费马小定理定义若p为素数，gcd(a,p)=1,则$a^{p}$≡a(modp),也可写为$a^{p-1}$≡1(modp). 证明二次剩余定义 若p是素数,a不是p的倍数且与一个平方数模p同余,则称a是模p的二次剩余,记作a∈QR 例如$2^{2}$≡4(mod13) 则称4是模13的二次剩余 同样我们把不等于0也不是模p的二次剩余的数称为非二次剩余,记作a∈NR