有纯"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]