二次剩余課件

第三章二次剩余第三章二次剩余本章內(nèi)容一、二次剩余的概念二、模為奇素數(shù)的平方剩余與平方非剩余三、勒讓德符號四、雅可比符號五、小結(jié)重點：二次同余方程有解的判斷與求解本章內(nèi)容一、二次剩余的概念§3.1二次剩余的概念二次同余式的一般形式是其中m是正整數(shù)，。上式等價于同余式

定義1設(shè)m是正整數(shù)，若同余式有解，則a叫做模m的平方剩余(或二次剩余)，記為QR；否則a叫做模m的平方非剩余(或二次非剩余)，記為NR?！?.1二次剩余的概念二次同余式的一般形式是其中m是正例1分別求出模11，12的二次剩余和二次非剩余。解：模11的二次剩余是：1，3，4，5，9；二次非剩余是：2，6，7，8，10。模12的二次剩余是：1；二次非剩余是：5，7，11。例1分別求出模11，12的二次剩余和二次非剩余。解：模例2求滿足同余式的所有的點。解：模7的二次剩余是：1，2，4；二次非剩余是：3，5，6。對，分別求出對應(yīng)的的值為例2求滿足同余式無解無解無解無解§3.2模為奇素數(shù)的平方剩余

與平方非剩余§3.2模為奇素數(shù)的平方剩余

與平方非剩余二次剩余課件二次剩余課件二次剩余課件二次剩余課件二次剩余課件二次剩余課件可以驗證：∴模11的平方剩余為1，-2，3，4，5；平方非剩余為-1，2，-3，-4，-5.可以驗證：∴模11的平方剩余為1，-2，3，4，5；平方非模11的平方剩余為1，-2，3，4，5.模11的平方剩余為1，-2，3，4，5.例1

利用定理判斷例1利用定理判斷補充模重復(fù)平方計算法補充模重復(fù)平方計算法補充模重復(fù)平方計算法補充模重復(fù)平方計算法二次剩余課件二次剩余課件二次剩余課件二次剩余課件二次剩余課件二次剩余課件二次剩余課件符號表示如下：QR×QR=QRQR×NR=NRNR×NR=QR若用數(shù)字代替符號QR與NR，易見：QR如同+1NR如同-1符號表示如下：

定理2設(shè)p是奇素數(shù)，則模p的簡化剩余系中平方剩余與平方非剩余的個數(shù)各為，且個平方剩余與序列中的一個數(shù)同余，且僅與一個數(shù)同余。模7的平方剩余為1，2，-3；平方非剩余為-1，-2，3.定理2設(shè)p是奇素數(shù)，則模p的簡化剩余系中§3.3

勒讓德符號利用歐拉判別條件雖然可以判定x2

a(modp)

的解的存在性，但對較大的素數(shù)模，實際運用很困難。通過引入勒讓德符號，本節(jié)給出了較方便的判別方法。目的：快速判斷整數(shù)a是否為素數(shù)p的平方剩余。§3.3勒讓德符號利用歐拉判別條件雖然可以判定x2

定義設(shè)p是素數(shù),定義勒讓德Legendre符號如下：如,1與4是模5的平方剩余，2與3是模5的平方非剩余，定義設(shè)p是素數(shù),定義勒讓德Legendre符由此定義，歐拉判別法則可以表示成如下形式：定理2設(shè)p是奇素數(shù)，則對任意整數(shù)a，有定理1由此定義，歐拉判別法則可以表示成如下形式：定理2設(shè)p二次剩余課件

Legendre符號基本性質(zhì)Legendre符號基本性質(zhì)二次剩余課件二次剩余課件二次剩余課件二次剩余課件二次剩余課件二次剩余課件二次剩余課件二次剩余課件二次剩余課件二次剩余課件二次剩余課件由引理的證明由引理的證明2的倍數(shù)2的倍數(shù)二次剩余課件二次剩余課件二次剩余課件二次剩余課件證明：由定理3有二次互反律的證明：證明：二次互反律的證明：二次剩余課件二次剩余課件二次剩余課件二次剩余課件二次剩余課件二次剩余課件例

計算如下勒讓德符號的值。(1)

(2)

(3)例計算如下勒讓德符號的值。(1)(2)(3)m是否為素數(shù)q=0q=1q=-1q=2out:01停止否是，計算nmodm=q返回為奇數(shù)；為偶數(shù)。m是否為素數(shù)q=0q=1q=-1q=2out:01停止否是，二次剩余課件二次剩余課件二次剩余課件二次剩余課件二次剩余課件二次剩余課件對于奇素數(shù)p，利用計算Legendre符號可以判定方程x2

a(modp)(1)是否有解。對于一般的正整數(shù)m，

如何判定方程是否有解呢？x2

a(modm)(2)

四、雅可比符號對于奇素數(shù)p，利用計算Legendre符號可以判定方程x2對于一般的正整數(shù)m，如果它的標準分解式是那么判定方程x2

a(modm)(2)是否有解，可歸結(jié)為對形如方程x2

a(modp)(1)的可解性判定。

因此，在理論上，利用Legendre符號可以判定方程(2)是否有解。

但是，寫出正整數(shù)的標準分解式常會遇到實際困難，所以利用Legendre符號判定方程(2)的可解性并不容易實現(xiàn)。對于一般的正整數(shù)m，如果它的標準分解式是那么判定方程例如，取m=45=3

3

5，則例如，取m=45=335，則

定義設(shè)是奇素數(shù)的乘積。對任意整數(shù)，定義雅可比(Jacobi)符號為（1

i

k）是Legendre符號。

例如，取m=45=3

3

5，則當(dāng)m為奇素數(shù)時，則上式為勒讓德符號。定義設(shè)

注意：(1)當(dāng)m是奇素數(shù)時，Jacobi符號就是Legendre符號。前者是后者的推廣。(2)雅可比符號為1時，不能判斷a是否為模m的平方剩余。例如

因為，而同余式組的每個同余式都無解，所以3是模119的平方非剩余。注意：(1)當(dāng)m是奇素數(shù)時，Jacobi符號就是Lege

如果，則；設(shè)m是奇數(shù)，則雅可比符號有以下性質(zhì)：

，如果，則；(3)(2)；(1)，(4)(5)設(shè)m,n都是奇數(shù)，則。如果，則二次剩余課件定理1

設(shè)m=p1p2

pk是奇數(shù)，其中p1,p2,pk是素數(shù)，則下面的結(jié)論成立：定理1設(shè)m=p1p2pk是奇數(shù)，其中p1,p2定理2

設(shè)m，n是大于1的奇整數(shù)，則

利用以上定理，我們可以很容易地計算Jacobi符號，特別是Legendre符號的數(shù)值。但是，必須注意，如同在定義的注2中指出的，在判斷方程(2)的可解性時，Legendre符號和Jacobi的作用是不一樣的。

方程(2)有解。對于一般的正奇數(shù)m來說，=1并不能保證定理2設(shè)m，n是大于1的奇整數(shù)，則利用以上例判斷同余式是否有解？解：不用考慮563是否為素數(shù)，直接計算雅可比符號:所以同余式無解。例判斷同余式是否有解？解：不用考慮563是否為素數(shù)，直接當(dāng)n是合數(shù)的時候，若（a/n）=1，則a不一定是模n的二次剩余。定義則有。集合中的數(shù)稱為模n的偽二次剩余。124581011131617192014164116161416411-11-1-11-111-11-1111-11-11-11-1-1-11-111-1-1-1-111-11例：a當(dāng)n是合數(shù)的時候，若（a/n）=1，則a不一例

設(shè)a與b是正奇數(shù)，求的關(guān)系。例設(shè)a與b是正奇數(shù)，求結(jié)論：猜想二次剩余問題的難度與因子分解難度相當(dāng)。定理3.12若n=pq，且n的素因子p和q已知，則整數(shù)a為模n的二次剩余，當(dāng)且僅當(dāng)結(jié)論：猜想二次剩余問題的難度與因子分解難度相當(dāng)。五、小結(jié)1、m是正整數(shù)a是m的二次剩余。2、歐拉判別條件p是奇素數(shù)五、小結(jié)1、m是正整數(shù)a是m的二次剩余。2、歐拉判別條件p是3、勒讓德符號的定義設(shè)p是素數(shù)，定義如下：4、雅可比符號定義對任意奇數(shù)m，定義