有限域中的三次方根求解（三次剩余）

提问能手

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

northwolves

穷举，先找到了一个解：

$x = 2147483647k + 2097152$

理论上还有其它解

northwolves

貌似$2097152=2^21$

wayne

三个解： $2097152, 854160010, 1291226485$

提问能手

wayne 发表于 2022-10-5 23:21
三个解： $2097152, 854160010, 1291226485$

想知道求解过程，用程序编写代码应该很快能得出对应的三个解

提问能手

northwolves 发表于 2022-10-5 22:15
貌似$2097152=2^21$

这应该是其中一个解，用程序编码应该很快能得出。但希望能从数学给出求这道题的过程~

无心人

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)

mathe

找出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)$

提问能手

无心人 发表于 2022-10-6 08:26
Pari/GP

? p=2^31-1

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

liyqa

这是什么定理，没看懂呀