数论算法讲义 4章(二次同余式与平方剩余)

《数论算法讲义 4章(二次同余式与平方剩余)》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、41第四章二次同余式与平方剩余第4章二次同余式与平方剩余（一）内容：l二次同余方程，平方剩余l模为奇素数的平方剩余l勒让德符号、雅可比符号l二次同余方程的求解（二）重点：二次同余方程有解的判断与求解4.1一般二次同余式(一)二次同余式a＋bx＋c≡0modm，（a≠0modm）（1）(二)化简设模数m可分解为m＝，则方程（1）等价于同余方程问题归结为讨论同余方程a＋bx＋c≡0mod，（p┝a）（2）(三)化为标准形式方程（2）两边同乘以4a，4＋4abx＋4ac≡0mod≡－4acmod41数论算法41第四章二次同余式与平方剩余变量代换，y＝2ax＋b（3）有≡

2、－4acmod（4）当p为奇素数时，（4）与方程（2）是等价的。也就是说，两者同时有解或无解；有解时，对（4）的每个解，通过式（3）（这时是x的一次同余方程，，所以解数为1）给出（2）的一个解，由（4）的不同的解给出（2）的不同的解，且反过来也对，此外两者解数相同。由以上讨论知，只要讨论形如≡amod（5）的同余方程。【例】化简方程7x2＋5x－2≡0（mod9）为标准形式。（解）方程两边同乘以28，得196x2＋140x－56≡0（mod9）即(14x＋5)2－25－56≡0（mod9）亦即y2≡81（mod9）(一)二次剩余【定义1】设m是正整数，a是整数，m

3、┞a。若同余方程≡amodm（6）有解，则称a是模m的平方剩余（或二次剩余）；若无解，则称a是模m的二次非剩余。【定义1】问题：（1）正整数a模p的平方剩余与实数中的平方根有何区别？（2）如何判断方程（6）有解？41数论算法41第四章二次同余式与平方剩余（1）如何求方程（6）的解？(一)例【例1】1是模4平方剩余，－1是模4平方非剩余。【例1】【例2】1、2、4是模7平方剩余，3、5、6是模7平方非剩余。【例2】【例3】直接计算12，22，…，142得模15的平方剩余为（实际上只要计算（12，22，…，82）1，4，9，10，6平方非剩余为2，3，5，7，8，11

4、，12，13，14【例4】求满足方程E：≡＋x＋1mod7的所有点。【例4】（解）对x＝0，1，2，3，4，5，6分别解出y：＝0，≡1mod7，y≡1，6mod7＝1，≡3mod7，无解＝2，≡4mod7，y≡2，5mod7＝3，≡3mod7，无解＝4，≡6mod7，无解＝5，≡5mod7，无解＝6，≡6mod7，无解说明：方程E：≡＋x＋1的图形称为椭圆曲线。4.2模为奇素数的平方剩余与平方非剩余模为素数的二次方程≡amodp,(a,p)＝1（1）41数论算法41第四章二次同余式与平方剩余因为＝，故方程（1）要么无解，要么有两个解。(一)平方剩余的判断条件【定

5、理1】（欧拉判别条件）设p是奇素数，(a,p)＝1，则（i）a是模p的平方剩余的充要条件是（2）（ii）a是模p的平方非剩余的充要条件是（3）并且当a是模p的平方剩余时，，同余方程（1）恰有两个解。（证）首先证明对任一整数a，若p┞a，则式（2）或（3）有且仅有一个成立。由费马定理知故知（4）即p│＝但＝1或2且素数p>2。所以，p能整除，但p不能同时整除和（否则，p能整除它们的最大公因子1或2）所以，由式（4）立即推出式（2）或式（3）有且仅有一式成立。（i）必要性。若a是模p的二次剩余，则必有使得≡a（modp），因而有≡（modp）。即（modp）。41数论

6、算法41第四章二次同余式与平方剩余由于p┞a，所以p┞，因此由欧拉定理知≡1（modp）。由以上两式就推出式（2）成立。充分性。设式（2）成立，这时必有p┞a。故一次同余方程≡a（modp）,(1≤b≤p－1)（5）有唯一解，对简化剩余系－(p－1)/2，…，－1，1，…，(p－1)/2（6）由式（6）给出的模p的既约剩余系中的每个j，当b＝j时，必有唯一的属于简化剩余系（6），使得式（5）成立。若a不是模p的二次剩余，则必有。这样，既约剩余系（6）中的p－1个数就可按j、xj作为一对，两两分完。（b1≠b2，则相应的解x1≠x2，且除了±1之外，每个数的逆不是它

7、本身）因此有由威尔逊定理知但这与式（2）矛盾。所以必有某一，使，由此及式（5）知，a是模p的二次剩余。（ii）由已经证明的这两部分结论，立即推出第（ii）条成立。其次，若≠0（modp）是方程（1）的解，则－也是其解，且必有≠－（modp）。故当(a,p)＝1时，方程（1）要么无解，要么同时有两个解。（说明：本定理只是一个理论结果，当p>>1时，它并不是一个实用的判断方法）小结：对于任何整数a，方程（1）的解数可能为T(x2－a；p)＝0,1,241数论算法41第四章二次同余式与平方剩余【例1】判断137是否为模227的平方剩余。【例1】（解）首先，227是素数。

8、其次，计算