找回密码
 欢迎注册
查看: 7692|回复: 6

[提问] 如何求解 x^15 + 1 = 0 mod p

[复制链接]
发表于 2013-4-3 00:38:28 | 显示全部楼层 |阅读模式

马上注册,结交更多好友,享用更多功能,让你轻松玩转社区。

您需要 登录 才可以下载或查看,没有账号?欢迎注册

×
如何求解 x^15 + 1 = 0 mod p,越快越好
我只知道从1到p这样一个一个的试,但是这样太慢了.需要快一些的方法
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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)啊
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-4-3 09:06:52 | 显示全部楼层
可以先解x^15=1(mod p), 然后取负。好处在于解集对乘法构成群。至于试解,可以仿2#郭老板的建议,试x^3=1(mod p)或者x^5=1(mod p)
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2013-4-3 11:01:25 | 显示全部楼层
这个相当于把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还有一些优化的方法。
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2013-4-3 12:37:15 | 显示全部楼层
谢谢各位的回复,不过我基础太差,还是无法从各位的回复中得出怎么快一些解这个问题
我本来是想对10^8以内的每个素数p,都求解一次 x^15 + 1 = 0 mod p .但是我那种逐个验证的方法实在太慢不行.
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 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
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

小黑屋|手机版|数学研发网 ( 苏ICP备07505100号 )

GMT+8, 2024-3-19 14:48 , Processed in 0.081545 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

快速回复 返回顶部 返回列表