分解大整数的方法?

pointer · 发表于 2005-12-29 15:03:10

那位能详细说点这些方面的知识吗?

比如分解(数字是十进制的):
1983790504952981984129719415602093760957

soloforce · 发表于 2005-12-29 15:59:29

这个还真不容易！

arxor · 发表于 2005-12-29 18:31:26

关键就是后面的"数值计算"部分...
只写过简单的pollard rho分解, 那个对64bit的数来说大概是够了, 但是楼主的数......寒...
还有很多对于特殊类型数的分解
mathworld.wolfram.com上应该有很多你想找的东西

PS:曾用过个工具叫factor.exe, 分解数的范围让人很吃惊...而且速度很快, (不知道有没有linux版:p)

pointer · 发表于 2005-12-29 19:51:33

我的才41位啊
不过这个是m=pq的型的, 且p,q为比较安全的素数

arxor · 发表于 2005-12-29 22:44:53

嗯....我指的是64个二进制位....
更大的没试过....64bit的处理溢出就很麻烦了, 彻底分解还要用miller-rabin判质
你的例子大概要更高级的方法才行, 抱歉没学过...-_-b

Post by pointer
我的才41位啊
不过这个是m=pq的型的, 且p,q为比较安全的素数

likesq · 发表于 2009-3-29 13:27:15

1983 790504 952981 984129 719415 602093 760957 = 305696 545250 908717 x 6489
410939 612458 528721 用ecm分解

remote fish · 发表于 2009-3-29 14:56:47

莫非楼主是在做RSA加密？可以参考openssl或者gnu gmp中的相关算法。如果只是单纯的想做分解，maxima之类的工具很不错

		自动登录	找回密码
密码			注册