数学研发论坛

 找回密码
 欢迎注册
查看: 876|回复: 9

[提问] 有限域中的三次方根求解

[复制链接]
发表于 2017-6-15 18:22:49 | 显示全部楼层 |阅读模式

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

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

x
求解\[x^3\equiv a \pmod{p}\]\(p\) 是素数,\(a\) 是 \(p\) 的三次剩余
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-6-16 08:29:58 | 显示全部楼层
穷举法!
万能的穷举法

点评

@gxqcn 给我量子计算机,我穷举给你看  发表于 2017-6-16 13:27
那你用穷举法破解一下 RSA 试试?  发表于 2017-6-16 09:05
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-6-16 20:34:45 来自手机 | 显示全部楼层
设a的最小次数为k,如果k不是3的倍数,那么很简单。比如k模3为2,那么x=a^((k+1)/3)
如果k模3为1,那么x=a^((2k+1)/3)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-6-16 20:40:03 来自手机 | 显示全部楼层
如果a的次数为k=3^d*h,首先我们得通过随机算法找到g的次数为3k,
而且a^(k/3)和g^k相同
下一步比较a^(k/9)和g^(k/3),如果相同,就进入下一步,不然两者相除必然是三次单位根,用ag或a^2g两者之一替换g即可
一直这样下去直到找到g使得a^h=g^(3h)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-6-16 21:44:23 | 显示全部楼层
1. 当 `a=0`,`x` 必含因子 `p`,即解为 `x\equiv0\pmod p`.
2. 当 `a\neq 0`时
    1) 若 `p=2`,`a` 只能 `1`,解为 `x\equiv 1 \pmod 2`。
    2) 若 `p` 为奇素数,此时必有 `(a,p)=1`,设 `p` 的最小原根为 `g`,所以$$a\equiv g^t \pmod p\tag{1}$$可以证明 `t` 在 `[0,\varphi(p)-1]` 内有唯一解(这里的 `\varphi(p)=p-1` 为数论欧拉函数,下同)。
        又因为 `(a,p)=1`,故同时有$$ x\equiv g^s\pmod p \tag{2}$$联立`(1)(2)` 并取数论对数可得$$3s\equiv t\pmod{\varphi(p)}\tag{3}$$该同余式有解的充要条件为`(3,p-1)|t`,由 `(1)` 可通过简单穷举求出 `t`,进而根据 `(3)` 求出 `s`,从而得到解 `(2)`. 上述模运算过程,如果素数模很大,可以考虑使用快速模幂算法。

举两个简单例子:$$x^3\equiv 26 \pmod{41}$$`g=6,\varphi(41)=40\implies t=17,s=19\implies x\equiv 34\pmod{41}`
$$x^3\equiv 1 \pmod{7}$$`g=3,\varphi(7)=6\implies t=0,s=0,2,4\implies x\equiv 1,2,4\pmod{7}`
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-6-17 14:27:57 | 显示全部楼层
上面 `(1)` 式所求的 `t` 即数论中的离散对数,也叫作指标。可记作 `\mathrm{dlog}_{g,~p}\,a` 或 `\mathrm{ind}_{g,~p}\,a`.  离散对数的求解是一个NP问题,所以应用于密码学领域。
对于较小的素数 `p` 直接在 `[0,p-2]` 内穷举搜索可到 `t` (单周期解);对于较大的 `p` 这种方法可采用Shank法来减少计算量。

大致思路如下:
1. 找到 `g` 模 `p` 的乘法阶数 `d`(由原根定义可知 `d=\varphi(p)=p-1`).
2. 令 `m=\lceil \sqrt{d}\rceil`,可设 `t=qm+r\;(0\leqslant q,r \leqslant m-1)`,显然,只要求出 `q,r` 即可。
3. 计算 `G_r\equiv g^r \pmod{p},\;(r=0,1,2,\cdots,m-1)`, 记录 `G_r` 表。
4. 因为 `a \equiv g^t \equiv g^{qm+r}\pmod{p}`,故 `(g^{-m})^q a\equiv a^r \equiv (g^{d-m})^qa \pmod{p}`,于是分别令 `q=0,1,2,\cdots,m-1`,计算 `\lambda_q\equiv (g^{d-m})^qa \pmod{p}`,搜索满足 `G_r=\lambda_q` 的 `r`,一旦命中,那么 `t=qm+r`,停止搜索;否则继续.

5楼的方法是一般的,不仅对于3次剩余有效,而且对于 `n` 次剩余也适用。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-6-19 05:53:37 来自手机 | 显示全部楼层
Tonelli–Shanks algorithm - Wikipedia
修改以下就应该可以有多项式复杂度算法求立方根
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-3-13 16:26:57 | 显示全部楼层
mathe 发表于 2017-6-19 05:53
Tonelli–Shanks algorithm - Wikipedia
修改以下就应该可以有多项式复杂度算法求立方根

你的回答很棒,有时间我仔细研究一下!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2019-3-25 20:10 , Processed in 0.112671 second(s), 17 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc.

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