LiBreOJ #175. 模立方根
题目描述
$T$组输入，每组给出$a,p$，求同余方程$x^3 \equiv a \pmod{p}$的任一可行解，若无解则返回
0。数据范围
$T=10^5$，$p$为奇素数，$p<2^{30},a \in \mathbb{F}_p\setminus \{0\}$
分析
题目显然是让我们求，若$a$在$p$的3次剩余系中，求出原数。
- 设$k\mid p-1,p-1=kq$，则$a$是模奇素数$p$的一个$k$次剩余的充分必要条件
$$a^q\equiv 1\pmod{p}$$
$\textrm{Proof:}$
必要性：若$a$是$p$的一个$k$次剩余，则存在整数$x$，$(x,p)=1$，满足$x^k\equiv a \pmod{p}$，则$a^q \equiv x^{kq}=x^{p-1} \equiv 1 \pmod{p}$。
充分性：若$a^q\equiv 1\pmod{p}$，$g$是$p$的一个原根，则有$q,ind_{g}a\equiv 0 \pmod{p-1}$，即有$ind_{g}a\equiv0\pmod{\frac{p-1}{q}}$，得到$k\mid ind_ga$，即$a$是模$p$的一个$k$次剩余。
对素数形式的分析
$p$为$3n+2$形式的素数：
由费马小定理：$a^{p}\equiv a\pmod{p}$，即$a^{3n+2}\equiv a\pmod{p}$；同时也有$a^{p-1}\equiv 1\pmod{p}$，即$a^{3n+1}\equiv 1\pmod{p}$。两者相乘得到${(a^{2n+1})}^{3} \equiv a \pmod{p}$。
$p$为$3n+1$形式的素数时，解的存在性上面已经讨论了。若有解，我们虽然没有上述那么漂亮的解的形式，但这里有一个绝妙的算法可以解决该问题。
Peralta Method Extension
The Peralta method is a fast way of computing square roots for a prime of form $p=2^eq+1$ $(q \not\equiv0\mod 2)$ for large $e$.
考虑这样一个环： $$R=\frac{\mathbb{Z}_p[x]}{x^3-a}=\{ \alpha+\beta Y+\gamma Y^2 | \alpha,\beta,\gamma\in\mathbb{Z}_p,Y^3=a\}$$
对于$z\in R$，即$z=\alpha+\beta Y+\gamma Y^2$，有$z^{p-1}\equiv 1\pmod{p}$
如果$z^{\frac{p-1}{3}}=\beta_0 Y$，则有$(\beta_0 Y)^3\equiv\beta_0^3a\equiv1\pmod{p}$，即$\sqrt[3]{a}\equiv\beta_0^{-1}\pmod{p}$
算法流程1
For a prime $p\equiv 1 \mod 3$:
- Choose $z\in R^*$ at random.
- Compute $z^(\frac{p-1}{s})=\alpha + \beta Y + \gamma Y^2$.
- If $\alpha=\gamma=0$, then write($\beta^{-1}\mod p$) otherwise go to Step 1.
随机结果符合条件的概率为$\frac{1}{9}$，所以这个算法的时间复杂度全在快速幂上了。
Code
| |
51Nod - 1039
问题一致，但需要求得所有可行解。
- 如果$p \bmod 3 = 2$，则有唯一解。
- 反之，若有解则必定有三个不同值。
上面的代码可求得其中之一，不妨令其为$s$。那么，如何求出其他值呢？对于一般的3次方程$x^3=a$，如果已知一个可行解$s$，那么剩余的解可以用$s$分别乘以单位复根的一次和平方得到。
单位根为$\frac{-1+\sqrt{-3}}{2}$，在模意义下，需要用二次剩余去求解$x^2\equiv-3\pmod{p}$，在下面的代码中，使用了$\text{Tonelli Shanks}$算法计算二次剩余。
| |