免費論壇 繁體 | 簡體
Sclub交友聊天~加入聊天室當版主
分享
返回列表 发帖

\(4n+1\)型素数模的二次同余方程

本帖最后由 青青子衿 于 2021-12-11 16:06 编辑

针对素数模的二次同余方程(其解被称为模\(\,p\,\)余\(\,a\,\)的平方根)
\[\large\boxed{x^2\equiv a\pmod{p}}\]
当素数\(\,p\,\)为\(\,4n+1\,\)时,作如下讨论
设素数\(\,p=4n+1\,\),\(\,n=2^\lambda\cdot\!s\,\),其中\(\,u\,\)为奇数,\(\lambda\ge0\);
记\(\,a\,\)是模\(\,p\,\)的平方剩余(即存在一个整数\(\,x_0\,\)使得\(\,{x_0}^2\equiv a \pmod{p}\,\));
记\(\,b\,\)是模\(\,p\,\)的平方非剩余(即对任意一个整数\(\,x_{a}\,\)都有\(\,{x_a}^2\not\equiv a \pmod{p}\,\));
故素数\(\,p\,\)可以写为
\[\,p=4\cdot2^\lambda\cdot\!s+1\,\]
1)若有\(\,a^s\equiv1\pmod{p}\,\)或\(\,a^s\equiv-1\pmod{p}\,\)
   那么\(\,x^2\equiv a\pmod{p}\,\)的解为
\[x\equiv\pm a^{\frac{s+1}{2}}\pmod{p}\]
   或
\[x\equiv\pm a^{\frac{s+1}{2}}b^n\pmod{p}\]
2)若有\(\,a^s\not\equiv\pm1\pmod{p}\,\)
   那么在\(\,1,2,\cdots,2^\lambda-1\,\)这些数中,必有一数\(\,h\,\),它能够使得
\[\left(b^{2s}\right)^h\equiv-a^s\pmod{p}\]
   或
\[\left(b^{2s}\right)^h\equiv+a^s\pmod{p}\]
   则\(\,x^2\equiv a\pmod{p}\,\)的解为
\[x\equiv\pm a^{\frac{s+1}{2}}b^{n-hs}\pmod{p}\]
   或
\[x\equiv\pm a^{\frac{s+1}{2}}b^{2n-hs}\pmod{p}\]
\[
\boxed{
\begin{align*}
\text{
引理\(\quad\)当\(\quad a^s\not\equiv\pm1\pmod{p}\quad\)时,则必有一正整数\(\,\mu<\lambda\,\),它能使得\(\qquad\)
}\\
\hspace{5cm}
\left(a^s\right)^{2^\mu}\equiv-1\pmod{p}\hspace{5cm}\\
\text{
\(\,\qquad\)则此时必有一奇数\(\,t\,\)(其中\(\,0\leqslant t\leqslant 2^\mu-1\,\)),使得\(\,\,{\color{brown}{h=2^{\lambda-\mu}\cdot\!t}}\,\,\)能满足\(\quad\)
}\\
\hspace{5cm}
\left(b^{2s}\right)^h\equiv-a^s\pmod{p}\hspace{5cm}\\
\end{align*}
}
\]
参考《数论经典著作系列:初等数论(3)》陈景润
分享到: QQ空间QQ空间 腾讯微博腾讯微博 腾讯朋友腾讯朋友

本帖最后由 青青子衿 于 2019-3-9 23:23 编辑

回复 1# 青青子衿
如下将举例说明:
例5.  试解同余方程
\[x^2\equiv34\pmod{257}\]
解:此方程为模素数\(\,p=257\,\)余\(\,34\,\)的二次同余方程\(\,x^2\equiv a\pmod{p}\,\)
      因为\(\,257\,\)是一个\(\,4n+1\,\)型的素数,我们有
\begin{align*}
&&\left(\frac{a}{p}\right)_{\rm L}
=\left(\frac{34}{257}\right)_{\rm L}&=\left(\frac{2}{257}\right)_{\rm L}\left(\frac{17}{257}\right)_{\rm L}\\
&&&=\left(\frac{17}{257}\right)_{\rm L}&\left(\frac{2}{p}\right)_{\rm L}&=\left(-1\right)^{\frac{p^2-1}{8}}\\
&&&=\left(\frac{257}{17}\right)_{\rm L}&\left(\frac{q}{p}\right)_{\rm L}\left(\frac{p}{q}\right)_{\rm L}&=\left(-1\right)^{\frac{\left(p-1\right)\left(q-1\right)}{4}}\\
&&&=\left(\frac{2}{17}\right)_{\rm L}=1\\
\end{align*}
      故原同余方程一定有解;
      因为\(p=\,257=4\cdot2^\lambda\cdot\!s+1=4\cdot2^6+1\,\),
      所以\(\,n=2^6\,\),\(\,\lambda=6\,\),\(\,s=1\,\),\(\,\dfrac{s+1}{2}=1\,\),\(a^s=a=34\),
      则
\begin{align*}
a^s&\equiv34\pmod{257}\\
&\not\equiv-1\pmod{257}
\end{align*}
\begin{align*}
&\left(a^s\right)^{2}\,\colon&
&\equiv34^2\equiv{\color{blue}{1156}}\equiv128&\pmod{257}\\
&\left(a^s\right)^{2^2}\,\colon&
34^{2^2}\equiv\left(34^2\right)\left(34^2\right)&\equiv128^2\equiv{\color{blue}{16384}}\equiv193\equiv-64&\pmod{257}\\
&\left(a^s\right)^{2^3}\,\colon&
34^{2^3}\equiv\left(34^{2^2}\right)\left(34^{2^2}\right)&\equiv\left(-64\right)^2\equiv{\color{blue}{4096}}\equiv241\equiv-16&\pmod{257}\\
&\left(a^s\right)^{2^4}\,\colon&
34^{2^4}\equiv\left(34^{2^3}\right)\left(34^{2^3}\right)&\equiv\left(-16\right)^2\equiv{\color{blue}{256}}\equiv{\color{brown}{-1}}&\pmod{257}\\
\end{align*}
      故\(\,\mu=4\,\),使得
\[\,\left(a^s\right)^{2^\mu}\equiv34^{2^4}\equiv-1\pmod{257}\,\]
      从而有\(\,\lambda-\mu=6-4=2\,\),则记\(\,h=2^{\lambda-\mu}\cdot\!t=2^2t=4t\,\)(其中\(\,t\,\)为奇数),
      并且有\(\,1\leqslant t\leqslant2^\mu-1=2^4-1=15\,\);
      又因为\(\,257=3\cdot5\cdot17+2\,\),则
\[\left(\frac{b}{p}\right)_{\rm L}=\left(\frac{3}{257}\right)_{\rm L}=\left(\frac{257}{3}\right)_{\rm L}=\left(-1\right)^{\frac{3^2-1}{8}}=-1\]
      故\(\,b=3\,\)是\(\,257\,\)的平方非剩余,从而有
\[\left(b^{2s}\right)^h=\left(3^2\right)^{4t}=\left(3^8\right)^t\]
\begin{align*}   
&\left(b^{2s}\right)^{2^{\lambda-\mu}\cdot1}\,\colon&
3^8\equiv9^4\equiv81^2
&\equiv{\color{blue}{6561}}\equiv136\equiv-121&\pmod{257}\\   
&\left(b^{2s}\right)^{2^{\lambda-\mu}\cdot3}\,\colon&   
\left(3^8\right)^3\equiv\left(-121\right)^3\equiv\left(-121\right)^2\left(-121\right)&\equiv\left(-8\right)\left(-121\right)\\
&&&\equiv{\color{blue}{968}}\equiv197\equiv-60&\pmod{257}\\   
&\left(b^{2s}\right)^{2^{\lambda-\mu}\cdot5}\,\colon&   
\left(3^8\right)^5\equiv\left(-121\right)^5\equiv\left(-121\right)^2\left(-121\right)^3&\equiv\left(-8\right)\left(-60\right)\\
&&&\equiv{\color{blue}{480}}\equiv-34&\pmod{257}\\   
\end{align*}
      所以有奇数\(\,t=5\,\),从而\(\,h=4t=4\cdot5=20\,\),
\[n-hs=2^\lambda\cdot\!s-h=2^6-20=44\]
      因为\(\,3^{40}\equiv\left(3^8\right)^5\equiv-34\pmod{257}\,\),所以
\[\,b^{n-hs}\equiv3^{44}\equiv3^4\cdot3^{40}\equiv81\cdot\left(-34\right)={\color{blue}{-2754}}\equiv\left(-184\right)\equiv73\pmod{257}\,\]
      而
\[a^{\frac{s+1}{2}}b^{n-hs}\equiv34\cdot3^{44}\equiv34\cdot73\equiv{\color{blue}{2482}}\equiv169\equiv-88\pmod{257}\]
      故二次同余方程\(\,x^2\equiv34\pmod{257}\,\)的解为
\[x\equiv\pm88\pmod{257}\]

TOP

返回列表 回复 发帖