找回密码
 欢迎注册
查看: 12286|回复: 4

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

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

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

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

×
原理

若整系数多项式\(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
啥都不说,请先把这个整数分解了再说!
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2019-6-30 18:52:01 | 显示全部楼层
为了更方便地选取m,可令m=a^b, 例如m=7^37,此时k=280325, k的上届 值  k<p ,p是得到的 n 的一个因子

可以得到一个结论  k-1|p-1
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
发表于 2020-3-4 10:32:11 | 显示全部楼层
mathematica 发表于 2017-5-17 19:19
10^100 + 2^100 + 3
啥都不说,请先把这个整数分解了再说!

10^100 + 2^100 + 3
分解后的结果是
307 × 23029 × 258127 × 437530 233600 520729 339663 ×
12524057196879170836152656209970942116773628688093184832075773293
毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
 楼主| 发表于 2020-7-25 21:07:42 | 显示全部楼层
$2^512+1$

随机选取m=82967672929

用到的多项式
$62522934038 + 48363746086 x + 78023589455 x^2 + 3884965730 x^3 +
7106054232 x^4 + 3539919872 x^5 + 4373040016 x^6 + 22453589451 x^7 +
38908372580 x^8 + 47625682315 x^9 + 63256371120 x^10 +
69548755266 x^11 + 49774371959 x^12 + 25526578391 x^13 + 18 x^14$

结果

{2424833, 10357}


毋因群疑而阻独见  毋任己意而废人言
毋私小惠而伤大体  毋借公论以快私情
您需要登录后才可以回帖 登录 | 欢迎注册

本版积分规则

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

GMT+8, 2024-3-29 22:26 , Processed in 0.044651 second(s), 16 queries .

Powered by Discuz! X3.5

© 2001-2024 Discuz! Team.

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