分解小素因子的mathematica程序

wsc810

原理

若整系数多项式\(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的一个因子

从而改进为一个确定性的因子分解方法

mathematica

10^100 + 2^100 + 3
啥都不说,请先把这个整数分解了再说!

kte

为了更方便地选取m,可令m=a^b, 例如m=7^37,此时k=280325, k的上届 值  k<p ,p是得到的 n 的一个因子

可以得到一个结论  k-1|p-1

mathematica

mathematica 发表于 2017-5-17 19:19
10^100 + 2^100 + 3
啥都不说,请先把这个整数分解了再说!

10^100 + 2^100 + 3
分解后的结果是
307 × 23029 × 258127 × 437530 233600 520729 339663 ×
12524057196879170836152656209970942116773628688093184832075773293

wsc810

$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}