有纯"0"地带的大整数如何分解？

无心人

factor()分解 呵呵

medie2005

$N=p*q$，$p,q$为素数。 base为一素数。 将N写成base进制的形式：$N=\sum_{i=0}^{n}{a_i*base^i}$. 得到多项式：$F_{base}(x)=\sum_{i=0}^{n}{a_i*x^i}$. 若$F_{base}(x)$不是本原多项式，则必可写成两多项式相乘的形式。 令$D=max{a_i}$，$0<=i<=n$. $M=D^{2}*n$,选取大于M的素数$P$,在模$P$下分解多项式$F_{base}(x)$。 M的上界的估计在taocp vol 2 418-419 page上有描述，但是上界比较大。

无心人

那我估计你肯定要失败

无心人

N = 1234567891234567 base = 7 你测试下？

medie2005

6*x^17+4*x^16+5*x^15+6*x^14+4*x^13+6*x^12+2*x^11+6*x^10+1*x^9+5*x^8+2*x^7+2*x^6+5*x^5+4*x^4+0*x^3+0*x^2+1*x^1+6 是不是素多项式？ 并且， 1234567891234567也不是p*q形式的合数。 [ 本帖最后由 medie2005 于 2008-10-30 10:51 编辑 ]

无心人

是素的 你要双因子的？ 好，马上做一个出来

无心人

4295229443 base = 37吧

medie2005

4295229443写成37进制，对应的多项式为： 2*x^6+12*x^5+2*x^4+6*x^3+31*x^2+32*x^1+28 是素多项式。 [ 本帖最后由 medie2005 于 2008-10-30 11:33 编辑 ]

无心人

x^6 + 24*x^5 + 34*x^4 + 30*x^3 + 5*x^2 + 4*x + 9 factor(x^6 + 24*x^5 + 34*x^4 + 30*x^3 + 5*x^2 + 4*x + 9) %42 = [x^6 + 24*x^5 + 34*x^4 + 30*x^3 + 5*x^2 + 4*x + 9 1]