同余方程x^2=a(mod p)如何求解

mathematica

初等数论上,只写了判断方程是否有解的二次互反律,
但是如何求解这个方程却没说,
即使判断有解,那么解如何求解呢?

葡萄糖

参看《初等数论Ⅲ》陈景润
这个链接里有某类情况下的通解（模4余1的）
http://kuing.orzweb.net/viewthre ... &extra=page%3D1

.·.·.

大约可以理解成：
$a^{\frac{p}2}=(x^2)^{\frac p2}=x^p=x(mod p)$
剩下的工作就是想尽办法凑p/2了
比如mod 23
$x^2=a(mod 23)$
$a^6=x^{12}=x^{11}x(mod 23)$
$x^{11}=$正负1$(mod 23)$
书上不写怎么凑，是因为4k+3型的素数好凑，而4k+1型的素数又要分情况讨论，反正是一件巨麻烦的事情

mathematica

葡萄糖 发表于 2019-3-13 13:21
参看《初等数论Ⅲ》陈景润
这个链接里有某类情况下的通解（模4余1的）
http://kuing.orzweb.net/viewthre ...

mathematica的PowerMod函数
PowerMod[4,1/2,7]能直接求解!

葡萄糖

mathematica 发表于 2019-3-13 13:34
mathematica的PowerMod函数
PowerMod[4,1/2,7]能直接求解!

你应该说清楚问题，到底是要人工计算，还是找MMa的命令？
PS：这个命令我也用过

mathematica

葡萄糖 发表于 2019-3-13 13:41
你应该说清楚问题，到底是要人工计算，还是找MMa的命令？
PS：这个命令我也用过

我当然要的是原理,
因为我看数论书上没说如何求解方程呀!

mathe

由于$a^{p-1} -= 1(mod p)$
所以a模p的最小次数必然是$p-1$的因数，根据p-1的因子分解结果必然可以找到a的最小次数d,也就是$a^d -= 1(mod p)$
如果这时d是奇数，我们选择$x -= a^{{d+1}/2}(mod p)$即可。不然设$d=2^ht$,其中t为奇数。记$b -= a^t, b^{2^h} -=1(mod p)$
通过随机算法可以找出模p的原根然后可以找出一个元素g使得$g^{2^{h+1}} -=1(mod p)$, 而且$g^{2^h}-= -1(mod p)$
由于$b^{2^h} -= 1(mod p), g^{2^{h+1}} -= 1 (mod p)$,
然后让i从h递降到1，其中假设我们已经有$b^{2^i} -= g_i ^{2^{i+1}} (mod p)$,而且$g_i^{2^{h+1}} -= 1(mod p)$
我们计算$b^{2^{i-1}}$和$g_i^{2^i}$,如果两者相同，那么取$g_{i-1}=g_i$
必然，两者必然互为相反数，于是$b^{2^{i-1}}-= -g_i^{2^i} -= g^{2^h} g_i^{2^i} -= (g^{2^{h-i}}g_i)^{2^i} (mod p)$, 于是我们可以选择$g_{i-1} -= g^{2^{h-i}}g_i(mod p)$, 显然$g_{i-1}$和$g_i$有相同的阶
由此我们计算可以得到$b -= g_0^2 (mod p)$
也就是$a^t -= g_0^2 (mod p)$
现在我们查看$y=a^{{t+1}/2}$,于是$y^2 -= a*g_0^2(mod p)$, 于是选择$x-=y*g_0^{-1} (mod p)$即可

mathematica

mathe 发表于 2019-3-13 14:50
由于$a^{p-1} -= 1(mod p)$
所以a模p的最小次数必然是$p-1$的因数，根据p-1的因子分解结果必然可以找到a的 ...

看算法数论,这本书没提到求原根!

mathematica

https://blog.csdn.net/qq_35649707/article/details/78922508

kastin

见 有限域中的三次方根求解 5#，6#