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

nyy

PowerMod[2, 1/3, 2^31 - 1]
得到
2097152

nyy

1. Clear["Global`*"];
   
2. p=2^31-1(*模*)
   
3. g=PrimitiveRoot[p](*得到原根*)
   
4. m=MultiplicativeOrder[g,p,{2}](*g^m=2(mod p),得到指数m*)
   
5. n=MultiplicativeOrder[g,p,{1}](*g^n=1(mod p),得到原根的指数*)
   
6. root1=PowerMod[g,(m+0*n)/3,p](*得到第1个根*)
   
7. root2=PowerMod[g,(m+1*n)/3,p](*得到第2个根*)
   
8. root3=PowerMod[g,(m+2*n)/3,p](*得到第3个根*)

复制代码

g=7
m=484915662
n=2147483646

gxqcn

1. PowerModList[2, 1/3, 2^31 - 1] // Timing

复制代码

结果为：

1. {0., {2097152, 854160010, 1291226485}}

复制代码

提问能手

提问能手 发表于 2022-10-6 15:47
y=znlog(2, g, v)/3
y = 161638554
抱歉 这边没有看懂什么意思，能稍微扩展说下么

感谢

提问能手

liyqa 发表于 2022-10-8 08:39
这是什么定理，没看懂呀

会用到费马小定理

nyy

提问能手 发表于 2022-10-17 12:11
会用到费马小定理

费马小定理就是个金矿！能产生素数判定算法：费马测试、miller rabin测试、二次域费马小定理，p-1分解质因数，椭圆曲线分解质因数算法！