大家好，欢迎来到IT知识分享网。
二次剩余
x 2 ≡ n ( m o d p ) x^2≡n(mod\ p) x2≡n(mod p)
对于这个方程，求出满足的x。
引理1
证明1
假设 ( n p ) = 1 (\frac{n}{p})=1 (pn)=1即n为p的二次剩余时，设解为x
根据费马小定理，我们知道 x p − 1 ≡ 1 ( m o d p ) x^{p-1}≡1(mod\ p) xp−1≡1(mod p)x显然存在
假设 ( n p ) = 1 (\frac{n}{p})=1 (pn)=1即n为p的二次剩余时
此时 x 2 ≡ n ( m o d p ) x^2≡n(mod\ p) x2≡n(mod p)无解
此时插入一个引理
若gcd(i,p)=1,且j为整数，则线性同余方程 i x ≡ j ( m o d p ) ix≡j(mod\ p) ix≡j(mod p)的有模p的唯一解(这里就不证明了，具体百度线性同余方程)
引理2
有了上面的引理，我们来看看如何解这个方程。
首先我们在1~p-1上随机出一个a,然后设 w = a 2 − n w=a^2-n w=a2−n，若w是p的二次非剩余，则解为 x = ( a + w ) p + 1 2 x=(a+\sqrt{w})^{\frac{p+1}{2}} x=(a+w)2p+1
为什么是这样？从末尾出发证明较为简单
证明2
x 2 = ( a + w ) p + 1 = ( a + w ) p ∗ ( a + w ) = ( a p + w p ) ∗ ( a + w ) = ( a − w ) ∗ ( a + w ) = a 2 − w = a 2 − ( a 2 − n ) = n ( m o d p ) \begin{aligned} &x^2\\ &=(a+\sqrt{w})^{p+1}\\ &=(a+\sqrt{w})^p*(a+\sqrt{w})\\ &=(a^p+{\sqrt{w}}^p)*(a+\sqrt{w})\\ &=(a-\sqrt{w})*(a+\sqrt{w})\\ &=a^2-w\\ &=a^2-(a^2-n)\\ &=n(mod\ p)\\ \end{aligned} x2=(a+w)p+1=(a+w)p∗(a+w)=(ap+wp)∗(a+w)=(a−w)∗(a+w)=a2−w=a2−(a2−n)=n(mod p)
上述之中全都是在模p的意义下的运算，有一步骤可能有点蒙，现在我解释一下这一步
= ( a + w ) p ∗ ( a + w ) = ( a p + w p ) ∗ ( a + w ) = ( a − w ) ∗ ( a + w ) \begin{aligned} &=(a+\sqrt{w})^p*(a+\sqrt{w})\\ &=(a^p+{\sqrt{w}}^p)*(a+\sqrt{w})\\ &=(a-\sqrt{w})*(a+\sqrt{w})\\ \end{aligned} =(a+w)p∗(a+w)=(ap+wp)∗(a+w)=(a−w)∗(a+w)
先解释后两个等式，根据费马小定理， a p − 1 ≡ 1 ( m o d p ) a^{p-1}≡1(mod\ p) ap−1≡1(mod p)，所以 a p ≡ a ( m o d p ) a^p≡a(mod\ p) ap≡a(mod p)。
因为w是p的二次非剩余，所以有 w p − 1 2 ≡ − 1 ( m o d p ) w^{\frac{p-1}{2}}≡-1(mod\ p) w2p−1≡−1(mod p),所以 w p 2 ≡ − w ( m o d p ) w^{\frac{p}{2}}≡-\sqrt{w}(mod\ p) w2p≡−w(mod p)
然后解释前两个等式
引理3
( a + b ) p = a p + b p ( m o d p ) (a+b)^p = a^p+b^p(mod\ p) (a+b)p=ap+bp(mod p)
证明3
首先，根据二项式定理展开，除了第一项和最后一项之外，都会有一个组合数 p i \frac{p}{i} ip是无法除掉的，所以对p取模都等于0，因此只剩下最后两项。
证毕
你最愿意做的哪件事，才是你的天赋所在
免责声明：本站所有文章内容,图片，视频等均是来源于用户投稿和互联网及文摘转载整编而成，不代表本站观点，不承担相关法律责任。其著作权各归其原作者或其出版社所有。如发现本站有涉嫌抄袭侵权/违法违规的内容,侵犯到您的权益，请在线联系站长,一经查实,本站将立刻删除。 本文来自网络,若有侵权，请联系删除，如若转载，请注明出处：https://haidsoft.com/124544.html
