Cipolla-Lehmer 算法

hly1204 2020-07-31 18:52:42 2020-09-11 0:33:26

关于域的扩张的方法是 EI 在群里告诉我的,非常谢谢 EI

Euler's criterion : 设 p 为奇素数, n 为正整数, a\in \mathbb{F}_{p}\setminus\{0\} ,则 a 是一个模 p 意义下的 n 次剩余当且仅当 a^{(p-1)/\delta}\equiv 1\pmod{p} ,其中 \delta =\gcd(p-1,n)

求方程 x^{3}\equiv c\pmod{p} 的解, 根据上式显然当 p\bmod{3}=2 p=3 时,有 \gcd(p-1,3)=1 (但 p=3 时下式不适用,需特判),此时 c^{p-1}\equiv 1\pmod{p} 恒成立(费马小定理),那么每个数 k\neq 0\in \mathbb{F}_{p} 都是三次剩余,可以发现 x^{2}\equiv x^{p+1}\equiv (x^{(p+1)/3})^{3}\equiv (x^{3})^{(p+1)/3}\equiv c^{(p+1)/3}\pmod{p} ,则 x\equiv c\cdot c^{-(p+1)/3}\equiv c^{(2p-1)/3}\pmod{p}

p\bmod{3}=1 时, Cipolla-Lehmer 算法可以描述为找到一个不可约三次多项式(常数项为 -c f(x)=x^{3}-ax^{2}+bx-c\in \mathbb{F}_{p}[x] ,设 \alpha \in \mathbb{F}_{p^{3}} f(x) 的一个根,有 {\alpha}^{1+p+p^{2}}=c ,所以 x^{(1+p+p^{2})/3}\bmod f(x) 为一个解。

Dickson 的不可约三次多项式测试可以描述为:

  • 输入:三次剩余 c\in \mathbb{F}_{p}
  • 输出:常数项为 -c 的不可约三次多项式 f(x)\in \mathbb{F}_{p}[x]
  1. 随机选择一个 b\in \mathbb{F}_{p} ,令 f(x)\gets x^{3}+bx-c D(f)\gets -(4b^{3}+27c^{2})
  2. 如果 D(f) 0 或一个二次非剩余,则回到第一步,否则令 \alpha \gets \frac{1}{2}(c+3^{-2}\sqrt{-3D(f)}) \alpha 是方程 x^{2}-cx-3^{-3}b^{3}=0 的一个根);
  3. 如果 \alpha\in \mathbb{F}_{p} 是一个三次非剩余,返回 f(x) ,否则回到第一步。

求所有解考虑方程 x^{3}=1\iff (x-1)(x^{2}+x+1)=0 解为 \{1,(-1+\sqrt{-3})/2,(-1-\sqrt{-3})/2\}

共 3 条回复

hly1204

因为我还不会解有限域方程,一定学习下~谢谢指出 >_< 。

lbh_qys

既然有 n^2 log p 的通用的解有限域多项式方程的做法,感觉这种比较麻烦的常数优化就没啥意义

lbh_qys

暴力解方程过了