数学研发网设为首页收藏本站

数学研发论坛

 找回密码
 欢迎注册
查看: 223|回复: 1

[原创] 分解小素因子的mathematica程序

[复制链接]
发表于 2017-5-17 00:32:01 | 显示全部楼层 |阅读模式

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

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

x
原理

若整系数多项式\(f(m)=0  \pmod n\)


则\(\gcd[f(m^k),n]\)有可能给出n的一个非平凡因子

下面贴出mathematica代码



  1. n = 2^277 - 1; m =  RandomInteger[{IntegerPart[n^(1/15)],  IntegerPart[n^(1/14)]}]
  2. s = IntegerDigits[n, m];
  3. x =.; f = Table[x^i, {i, 0, Length[s] - 1}].Reverse[s]
  4. For[i = 2, i < 8*50000, i++, x = PowerMod[m, i, n];
  5.   l = Table[PowerMod[x, j, n], {j, 0, Length[s] - 1}];
  6.   t = Total[l*Reverse[s]];
  7.   q = GCD[t, n]; If[q != 1, Break[]]];
  8. {q, i}
复制代码


选用的多项式及结果

$m=745148$

$258267 + 678023 x + 110760 x^2 + 157218 x^3 + 604452 x^4 +
151973 x^5 + 88005 x^6 + 385865 x^7 + 654011 x^8 + 399170 x^9 +
384355 x^10 + 12486 x^11 + 493400 x^12 + 689233 x^13 + 14 x^14$


${1121297, 70082}$


问题

目前该因子分解法还是概率性的,为了得到所想要的结果,多项式的选取有什么优选法,有无方法判定某个多项式为一有效多项式,即可以给出 n的一个因子

从而改进为一个确定性的因子分解方法
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2017-5-17 19:19:38 | 显示全部楼层
10^100 + 2^100 + 3
啥都不说,请先把这个整数分解了再说!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2017-9-23 10:04 , Processed in 0.331084 second(s), 19 queries .

Powered by Discuz! X3.2

© 2001-2013 Comsenz Inc.

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