分解小素因子的mathematica程序
原理若整系数多项式\(f(m)=0\pmod n\)
则\(\gcd\)有可能给出n的一个非平凡因子
下面贴出mathematica代码
n = 2^277 - 1; m =RandomInteger[{IntegerPart,IntegerPart}]
s = IntegerDigits;
x =.; f = Table - 1}].Reverse
For;
l = Table, {j, 0, Length - 1}];
t = Total];
q = GCD; If]];
{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的一个因子
从而改进为一个确定性的因子分解方法 10^100 + 2^100 + 3
啥都不说,请先把这个整数分解了再说! 为了更方便地选取m,可令m=a^b, 例如m=7^37,此时k=280325, k的上届 值k<p ,p是得到的 n 的一个因子
可以得到一个结论k-1|p-1 mathematica 发表于 2017-5-17 19:19
10^100 + 2^100 + 3
啥都不说,请先把这个整数分解了再说!
10^100 + 2^100 + 3
分解后的结果是
307 × 23029 × 258127 × 437530 233600 520729 339663 ×
12524057196879170836152656209970942116773628688093184832075773293 $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}
页:
[1]