二次剩余及欧拉准则

 

前置知识

阶(次数):e_p(a):使得a^e≡1(mod p)的最小指数e（e≥1),称为a模p的阶（次数）。原根:具有最高次数e_p(g)≡p-1(mod p)的数g（g>1）成为模p的原根。原根定理:每个素数都有且恰有φ(p-1)个原根。指标:原根的幂g,g²,g³,g⁴,......中与a mod p恰好一个同余的数,相应的指数I称为以g为底的a模p的指标。指标的乘法定理:I(ab)=I(a)+I(b)(mod p-1)

---

 

               二次剩余

定义：与一个平方数模p同余的非零数成为模p的二次剩余，不与任何一个平方数模p同余的数称为模p的非二次剩余。 

                 二次剩余表示为QR，二次非剩余表示为NR。

      勒让德符号：$\left ( \frac{a}{p} \right )$={                   1(a为模p的二次剩余）

                                                          -1(a为模p的非二次剩余）           }

 

---

 

  定理1：设p是一个奇素数，则恰有 $\frac{p-1}{2}$个模p的二次剩余，且恰有$\frac{p-1}{2}$个模p的二次非剩余。

 反证法证明：   根据二次剩余定义：

                          二次剩余是这样一些数：1²，2²，3²，......,(p-1)²(mod p)

                          又∵ (p-b)²=p²+2pb+b^2≡b²(mod p)

                        ∴1²，2²，3²，......,$\left ( \frac{p-1}{2} \right )$²与$\left ( \frac{p+1}{2} \right )$²,$\left ( \frac{p+3}{2} \right )$²,$\left ( \frac{p+5}{2} \right )$²,......,(p-1)²（mod p）在数值上相等

                          设1≤a,b≤ $\frac{p-1}{2}$,且a²≡b²(mod p)，且a≠b

                          则（a-b)(a+b)≡0(mod p)

                          但∵2≤a+b≤p-1，2≤a-b≤p-1，a≠b

                           ∴（a-b)(a+b)≡0(mod p)不成立

                           故1²，2²，3²，......,$\left ( \frac{p-1}{2} \right )$²（mod p）各不相同

                           又∵1-p有p-1个数

                          ∴恰有 $\frac{p-1}{2}$个模p的二次剩余，且恰有$\frac{p-1}{2}$个模p的二次非剩余。

                Q.E.D. 

---

 定理2：设g为模p的原根，g,g²,g³,......,g^p-1给出了模p所有的非零剩余。

                                  根据原根定义：g>1

                                 又∵g的偶次幂g^2k都可以表示为g^k*2

                                 ∴g的偶次幂都是平方数且各不相同

                                 又∵个数恰是$\frac{p-1}{2}$个

                                  ∴ g的偶次幂表示出了模p的所有二次剩余

                                  又∵g^k与g^2*k 对应不同

                                   ∴g的奇次幂表示模p的所有的二次非剩余

 Q.E.D.

---

 

二次剩余乘法法则：QR*QR=QR，NR*QR=NR，NR*NR=NR.

                根据定理2可以得出：指标为偶数（mod p)的数是模p的二次剩余，指标为奇数（mod p)的数是模p的二次非剩余。

                  又∵指标的乘法定理

                 ∴QR*QR=QR，NR*QR=NR，NR*NR=NR.

                                    Q.E.D.

 

---

 

 

欧拉准则

a^(p-1)/2≡ $\left ( \frac{a}{p} \right )$(mod p)

                分类讨论：①若a是模p的二次剩余

                                 则a的指标是偶数

                                 a≡g^2k(mod p)

         a^（p-1)/2≡g^k*(p-1)≡1^k≡1(mod p)

                               ②若a是模p的二次非剩余

                                 则a的指标是奇数

                                 a≡g^2k+1(mod p)

                                 a^（p-1)/2≡g^{k*(p-1)+(p-1)/2}≡g^(p-1)/2(mod p)

                               ∵g是模p的原根

                               ∴g^(p-1)/2≡-1（mod p)

Q.E.D.

 

---

参考资料：《数论概论》（Joseph H .silverman著 第三版）

转载于:https://www.cnblogs.com/3200Pheathon/p/10800065.html

相关资源：各显卡算力对照表！