数学研发论坛

 找回密码
 欢迎注册
查看: 223|回复: 27

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

[复制链接]
发表于 2019-3-13 12:27:29 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有帐号?欢迎注册

x
初等数论上,只写了判断方程是否有解的二次互反律,
但是如何求解这个方程却没说,
即使判断有解,那么解如何求解呢?
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-3-13 13:21:13 | 显示全部楼层
参看《初等数论Ⅲ》陈景润
这个链接里有某类情况下的通解(模4余1的)
http://kuing.orzweb.net/viewthre ... &extra=page%3D1

点评

我在后面实现了那个算法,但是不知道为什么那么运行是正确的  发表于 2019-3-15 12:52
我最近也在看数论书,但是我只看初等数论书,太难了我会看不懂的  发表于 2019-3-13 13:27
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-3-13 13:23:32 | 显示全部楼层
本帖最后由 .·.·. 于 2019-3-13 13:24 编辑

大约可以理解成:
$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型的素数又要分情况讨论,反正是一件巨麻烦的事情

点评

作死选密码学的时候着重讲过这个公式的……  发表于 2019-3-14 20:47
科大少年懂得真多  发表于 2019-3-13 13:27
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-3-13 13:34:35 | 显示全部楼层
葡萄糖 发表于 2019-3-13 13:21
参看《初等数论Ⅲ》陈景润
这个链接里有某类情况下的通解(模4余1的)
http://kuing.orzweb.net/viewthre ...

mathematica的PowerMod函数
PowerMod[4,1/2,7]能直接求解!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-3-13 13:41:23 | 显示全部楼层
本帖最后由 葡萄糖 于 2019-3-13 13:43 编辑
mathematica 发表于 2019-3-13 13:34
mathematica的PowerMod函数
PowerMod[4,1/2,7]能直接求解!


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

点评

有电子版的吗?上传上来吧  发表于 2019-3-13 14:04
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-3-13 13:47:39 | 显示全部楼层
葡萄糖 发表于 2019-3-13 13:41
你应该说清楚问题,到底是要人工计算,还是找MMa的命令?
PS:这个命令我也用过

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

点评

你看陈景润的那一本《初等数论Ⅲ》就可以学会了~  发表于 2019-3-13 13:54
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-3-13 14:50:49 | 显示全部楼层
由于$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)$即可
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-3-13 15:13:45 | 显示全部楼层
mathe 发表于 2019-3-13 14:50
由于$a^{p-1} -= 1(mod p)$
所以a模p的最小次数必然是$p-1$的因数,根据p-1的因子分解结果必然可以找到a的 ...

看算法数论,这本书没提到求原根!
QQ截图20190313151255.png

点评

s=0就不执行这个循环,$b=a^{\frac{t+1}{2}}=a^{\frac{p+1}{4}}$  发表于 2019-3-14 20:51
代码里的$\beta$相当于我说的g,只是这里通过随机算法寻找,而我是先找原根。的确这样效率更高一些。  发表于 2019-3-13 15:49
但是我感觉这个结果似乎不对,对于4k+3素数,似乎没用,因为循环不起来  发表于 2019-3-13 15:20
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2019-3-13 15:16:01 | 显示全部楼层
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-3-13 15:42:41 | 显示全部楼层

点评

链接中6楼也说明了,5楼给的方法是一般的,没有特别为二次三次优化。  发表于 2019-3-13 17:06
有限域开平方或开三次方是有多项式时间算法的,5#,6#的算法都是指数时间复杂度的,对于较大的p不是特别适合。  发表于 2019-3-13 16:01
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2019-3-25 20:34 , Processed in 0.167589 second(s), 20 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

快速回复 返回顶部 返回列表