有纯"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)<p_i$ 且$p_(i+1)$与2,3,5,7互质，计算$m= x % p_(i+1)$,如果m=0, 则分别检测 $p_(i+1)$ 和$ x/p_(i+1)$的是否为素数，如果是则分解完成。
  4. 重复步骤3，由于这个题目p和x/p的差很小，用不了几步，就分解掉了。

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

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

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

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