gracias 发表于 2013-4-3 00:38:28

如何求解 x^15 + 1 = 0 mod p

如何求解 x^15 + 1 = 0 mod p，越快越好
我只知道从1到p这样一个一个的试,但是这样太慢了.需要快一些的方法

gxqcn 发表于 2013-4-3 07:49:01

那先试试解 x^3 + 1 = 0 mod p 及 x^5 + 1 = 0 mod p，怎样？

无心人 发表于 2013-4-3 08:03:28

相当于
x^30 = 1 (mod p)啊

hujunhua 发表于 2013-4-3 09:06:52

可以先解x^15=1(mod p), 然后取负。好处在于解集对乘法构成群。至于试解，可以仿2#郭老板的建议，试x^3=1(mod p)或者x^5=1(mod p)

zgg___ 发表于 2013-4-3 11:01:25

这个相当于把x^15+1在有限域Fp中分解。
可以尝试下面的指令：p = Prime
Factor
Factor由于x^15 + 1在有理数域Q中可以分解，成4个因式，所以可以分别在Fp中分解。
在有限域Fp中分解因式有快速的方法（对于比较小的p是lz提到的尝试的方法是最快的），比如可以将x^p-1和待分解的式子辗转相除，求公因子。此外对于很大的p还有一些优化的方法。

gracias 发表于 2013-4-3 12:37:15

谢谢各位的回复，不过我基础太差,还是无法从各位的回复中得出怎么快一些解这个问题
我本来是想对10^8以内的每个素数p,都求解一次 x^15 + 1 = 0 mod p .但是我那种逐个验证的方法实在太慢不行.

litaoye 发表于 2013-4-6 00:19:49

2楼的方法挺好的，先分解15，最后可以用组合来弄。利用高次剩余，求x^3 mod p 以及 x^5 mod p，不考虑大数的话，都有k*log(n)^2的解法，这里k = 3和5。所以还过的去。也可以直接利用bsgs算法求解x^15 mod p，大概是sqrt(n)的复杂度。

计算10^8以内所有的，有不少P的解都可以直接通过费马小定理来构造，那样的话只需要解一个模方程，是log(n)级的。

以上方法都是用来求1个解的，求全解的话效率瓶颈可能在解的数量上。

如何求解 x^15 + 1 = 0 mod p，越快越好
我只知道从1到p这样一个一个的试,但是这样太慢了.需要快一些的方法
gracias 发表于 2013-4-3 00:38 http://bbs.emath.ac.cn/images/common/back.gif
页: [1]
查看完整版本: 如何求解 x^15 + 1 = 0 mod p