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

medie2005 · 发表于 2008-10-28 21:35:33

分解多项式算法的复杂度最好可为多少?

liangbch · 发表于 2008-10-28 21:47:36

我想，好地方用的是试除法，不过不是从最小的素数开始试除的，而是从$sqrt(x)$向下，依次找素数试除的。

medie2005 · 发表于 2008-10-28 21:52:44

分解是很简单,用Fermat方法就很快可以得到解了,因为p-q太小了. 素性判定还是比较花时间,ARCL算法据说可以在1分钟内判定100位的数的素性.

无心人 · 发表于 2008-10-29 07:56:08

如果是P - Q，且是RSA加密的话我想P - Q应该不是太小了而是至少应该是P / 4大小的所以并不比直接试除简单否则RSA也忒容易了吧

无心人 · 发表于 2008-10-29 08:11:24

RSA安全素数定义： a) p,q 长度较接近。 b) p-1,q-1有大素数因子 c) (p-1,q-1)很小。如果我选512位加密我会选P是255位，Q是257位

medie2005 · 发表于 2008-10-29 08:50:17

呵呵，我现在想用分解多项式的方法来分解RSA。呵呵，发现还是不行。多项式乘法无进位，整数相乘有进位。

无心人 · 发表于 2008-10-29 09:48:02

分解多项式的方法只能对付特殊的整数的

好地方 · 发表于 2008-10-29 12:16:28

原帖由 liangbch 于 2008-10-28 21:47 发表我想，好地方用的是试除法，不过不是从最小的素数开始试除的，而是从$sqrt(x)$向下，依次找素数试除的。

你不是在开玩笑吧？

liangbch · 发表于 2008-10-29 13:11:30

不是开玩笑，楼主给出的数有点特殊，利用HugeCalc用这样的方法解题确实可行，不过如果p 与 q (p*q=x) 相差很大的话，这个方法就不行了。下面是详细步骤。 1. p0= $\sqrt(x)$ 2. 从P0开始找一个<=p0的数P1,且使得P1与2,3,5,7互质1,计算m= x % p1,如果m=0, 则分别检测 p1 和 x/p1的是否为素数，如果是，则分解完成。 3. 找一个 $p_(i+1)$，使得$p_(i+1)

medie2005 · 发表于 2008-10-29 15:00:23

无心人，如何用pari/Gp判断多项式的本原性？语句是什么？

账号		自动登录	找回密码
密码			欢迎注册

[原创] 有纯"0"地带的大整数如何分解？