《数论算法》教案 4章(二次同余方程与平方剩余)

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

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

2、）有≡－4ac（mod）（4）当p为奇素数时，方程（4）与（2）等价。即l两者同时有解或无解；有解时，对（4）的每个解，通过式（3）（x的一次同余方程，且（p,2a）＝1，所以解数为1）给出（2）的一个解，由（4）的不同的解给出（2）的不同的解；反之亦然。l两者解数相同。结论：只须讨论以下同余方程≡a（mod）（5）【例】化简方程7x2＋5x－2≡0（mod9）为标准形式。（解）方程两边同乘以4a＝4×7＝28，得196x2＋140x－56≡0（mod9）配方(14x＋5)2－25－56≡0（mod9）移项(14x＋5)2≡81（mod9）变量代换y＝14x＋5得y2≡0（mod

3、9）（解之得y＝0,±3，从而原方程的解为x≡(y－5)≡(y－5)≡2(y－5)≡2y－10≡2y－1≡－7,－1,5≡－4,－1,2（mod9））49/49《数论算法》第四章二次同余方程与平方剩余(一)二次剩余【定义4.1.1】设m是正整数，a是整数，ma。若同余方程≡a（modm）（6）有解，则称a是模m的平方剩余（或二次剩余）；若无解，则称a是模m的平方非剩余（或二次非剩余）。问题：（1）设正整数a是模p的平方剩余，若记方程（6）中的解为x≡（modm），那么此处的平方根（modm）与通常的代数方程＝a的解有何区别？（2）如何判断方程（6）有解？（3）如何求方程（6）的解

4、？(二)例【例1】1是模4平方剩余，－1是模4平方非剩余。【例2】1、2、4是模7平方剩余，3、5、6是模7平方非剩余。【例3】直接计算12，22，…，142得模15的平方剩余（实际上只要计算（12，22，…，72）1，4，9，10，6平方非剩余：2，3，5，7，8，11，12，13，14【例4】求满足方程E：≡＋x＋1（mod7）的所有点。（解）对x＝0，1，2，3，4，5，6分别解出y：＝0，≡1（mod7），y≡1，6（mod7）＝1，≡3（mod7），无解49/49《数论算法》第四章二次同余方程与平方剩余＝2，≡4（mod7），y≡2，5（mod7）＝3，≡3（mod7）

5、，无解＝4，≡6（mod7），无解＝5，≡5（mod7），无解＝6，≡6（mod7），无解所以，满足方程的点为（0,1），（0,6），（2,2），（2,5）。说明：方程E：≡＋x＋1的图形称为椭圆曲线。4.1模为奇素数的平方剩余与平方非剩余模为素数的二次方程≡a（modp）,(a,p)＝1（1）因为＝，故方程（1）要么无解，要么有两个解。(一)平方剩余的判断条件【定理4.2.1】（欧拉判别条件）设p是奇素数，(a,p)＝1，则（i）a是模p的平方剩余的充要条件是≡1（modp）（2）（ii）a是模p的平方非剩余的充要条件是≡－1（modp）（3）并且当a是模p的平方剩余时，同余方

6、程（1）恰有两个解。（证）先证pa时，式（2）或（3）有且仅有一个成立。由费马定理≡1（modp）－1≡0（modp）49/49《数论算法》第四章二次同余方程与平方剩余≡0（modp）（4）即＝但＝1或2且素数p>2。所以，p能整除，但p不能同时整除和（否则，p能整除它们的最大公因子1或2）所以，由式（4）立即推出式（2）或式（3）有且仅有一式成立。（i）必要性。若a是模p的二次剩余，则必有使得≡a（modp），因而有≡（modp）。即（modp）。由于pa，所以p，因此由欧拉定理知≡1（modp）。即（2）式成立。充分性。已知≡1（modp），这时必有pa。故一次同余方程≡a（

7、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作为一对，两两分完。49/49《数论算法》第四章二次同余方程与平方剩余（b1≠b2，则相应的解x1≠x2，且除了±1之外，每个数的逆不是它本身）因此有由威尔逊定理知与式（2）矛盾。所