找回密码
 欢迎注册
查看: 6422|回复: 24

[提问] 有限域中的三次方根求解(三次剩余)

[复制链接]
发表于 2022-10-5 20:44:24 | 显示全部楼层 |阅读模式

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

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

×
求解
\( x^3 \equiv 2 \pmod{2^{31}-1}\)
\(2^{31}-1\) 是梅森素数,\(2\) 是 \(2^{31}-1\) 的三次剩余

评分

参与人数 1金币 +20 收起 理由
gxqcn + 20 首帖奖励,欢迎常来。

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-10-5 22:00:48 | 显示全部楼层
穷举,先找到了一个解:

$x = 2147483647k + 2097152$

理论上还有其它解
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-10-5 22:15:32 | 显示全部楼层
貌似$2097152=2^21$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-10-5 23:21:43 | 显示全部楼层
三个解: $2097152, 854160010, 1291226485$
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-10-6 06:58:18 | 显示全部楼层
wayne 发表于 2022-10-5 23:21
三个解: $2097152, 854160010, 1291226485$

想知道求解过程,用程序编写代码应该很快能得出对应的三个解
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-10-6 07:00:55 | 显示全部楼层

这应该是其中一个解,用程序编码应该很快能得出。但希望能从数学给出求这道题的过程~
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-10-6 08:26:32 | 显示全部楼层
Pari/GP

? p=2^31-1
p=2147483647
? v=[p-1, factor(p-1)]
v = [2147483646, [2, 1; 3, 2; 7, 1; 11, 1; 31, 1; 151, 1; 331, 1]]
? g=znprimroot(p)
g=Mod(7,2147483647)
原根是7
? y=znlog(2, g, v)/3
y = 161638554
(这里如果znlog结果不能整除3,表示无解)
即 g^(3y) = 2 mod p

因此:
x^3=g^(3y) mod p
x = g^y mod p = 1291226485

另两个解:
? z=g^((p-1)/3)
z = Mod(1513477735, 2147483647)
z相当于1的三次根
? x*z
%61 = Mod(854160010, 2147483647)
? x*z*z
%62 = Mod(2097152, 2147483647)

当然其实有内置函数计算这个
? sqrtn(Mod(2,p),3)
%65 = Mod(2097152, 2147483647)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-10-6 11:04:33 | 显示全部楼层
找出7是$p=2^31-1$的一个原根后,由于$2^31 -= 1(mod p)$,
而$7^{(p-1)/31} -=512 (mod p)$,
然后穷举计算可以得到$512^7 -= 2 (mod p)$
由此得到$7^{7(p-1)/31} -= 2 (mod p)$
于是$7^{7(p-1)/(31*3)} -= 7^161638554 -= 1291226485 (mod p)$
$1291226485^3 -= 2 (mod p)$

点评

通常离散对数问题复杂度比较高。这里比较特殊的是2的次数不高,所以可以有技巧  发表于 2022-10-6 14:03
遇到离散对数问题了,我那个计算其实也是~~~~  发表于 2022-10-6 11:21

评分

参与人数 1威望 +8 金币 +8 贡献 +8 经验 +8 鲜花 +8 收起 理由
northwolves + 8 + 8 + 8 + 8 + 8 赞一个!

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2022-10-6 15:47:36 | 显示全部楼层

y=znlog(2, g, v)/3
y = 161638554
抱歉 这边没有看懂什么意思,能稍微扩展说下么

点评

就是在模p环下求对数$\log_g 2$ 或者求满足 $g^x = 2$ 的 $x$  发表于 2022-10-9 19:26
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2022-10-8 08:39:33 | 显示全部楼层
这是什么定理,没看懂呀

评分

参与人数 1金币 +20 收起 理由
gxqcn + 20 首帖奖励,欢迎常来。

查看全部评分

毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-6-17 05:31 , Processed in 0.065645 second(s), 24 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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