无心人 发表于 2008-10-29 19:44:51

factor()分解
呵呵

medie2005 发表于 2008-10-30 10:27:50

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 2418-419 page上有描述，但是上界比较大。

无心人 发表于 2008-10-30 10:37:55

那我估计你肯定要失败

无心人 发表于 2008-10-30 10:38:33

N = 1234567891234567
base = 7
你测试下？

medie2005 发表于 2008-10-30 10:49:52

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 编辑 ]

无心人 发表于 2008-10-30 11:18:38

是素的
你要双因子的？

好，马上做一个出来

无心人 发表于 2008-10-30 11:19:36

4295229443

base = 37吧

medie2005 发表于 2008-10-30 11:26:26

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 编辑 ]

无心人 发表于 2008-10-30 11:27:37

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 =
页: 1 2 3 [4]
查看完整版本: 有纯"0"地带的大整数如何分解？