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

gracias

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

gxqcn

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

无心人

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

hujunhua

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

zgg___

这个相当于把x^15+1在有限域Fp中分解。 可以尝试下面的指令：

1. p = Prime[10^6]
2. Factor[x^15 + 1, Modulus -> p]
3. Factor[x^15 + 1]

复制代码

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

gracias

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

litaoye

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