有限域中的三次方根求解

wsc810

求解\[x^3\equiv a \pmod{p}\]\(p\) 是素数，\(a\) 是 \(p\) 的三次剩余

mathematica

穷举法!
万能的穷举法

mathe

设a的最小次数为k，如果k不是3的倍数，那么很简单。比如k模3为2，那么x=a^((k+1)/3)
如果k模3为1，那么x=a^((2k+1)/3)

mathe

如果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)

kastin

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}`

kastin

上面 `(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` 次剩余也适用。

mathe

Tonelli–Shanks algorithm - Wikipedia
修改以下就应该可以有多项式复杂度算法求立方根

mathematica

mathe 发表于 2017-6-19 05:53
Tonelli–Shanks algorithm - Wikipedia
修改以下就应该可以有多项式复杂度算法求立方根

你的回答很棒,有时间我仔细研究一下!