有限域中的三次方根求解（三次剩余）
求解\( x^3 \equiv 2 \pmod{2^{31}-1}\)
\(2^{31}-1\) 是梅森素数，\(2\) 是 \(2^{31}-1\) 的三次剩余 穷举，先找到了一个解：
$x = 2147483647k + 2097152$
理论上还有其它解 貌似$2097152=2^21$ 三个解： $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=
v = ]
? 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) 找出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
抱歉 这边没有看懂什么意思，能稍微扩展说下么 这是什么定理，没看懂呀
页:
[1]
2