相关数学基础知识

发表于 更新于 阅读次数： 本文字数： 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