整数分解包括大数

Mgccl · 发表于 2008-7-23 10:02:31

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

您需要登录才可以下载或查看，没有账号？欢迎注册

×

这个擂台我写不出程序的...不过希望众位高手试试. 我看了整个论坛,没有发现任何人发过大数分解的擂台... HugeCalc demo 的PrimeNumber程序对数字大小有限制... 不知有没有人想试试写出最快的整数分解程序? 我没有见过什么对比的程序,所以并不知道Mathematica里面的整数分解是否已经是领先水平... 我每天的乐趣就是看到一个数字...记录下来...回到家里...分解掉... 第二天到那里,贴个纸条,写个被分解的模式.

无心人 · 发表于 2008-7-23 10:13:53

你就知道数学软件包里的分解程序都不行就可以了我在这论坛发了个专门帖子里面是大部分的大数分解程序可以分解到100位整数

qianyb · 发表于 2010-2-27 14:55:49

最新的分解程序可以分解到多少位整数了？

郭先抢 · 发表于 2012-12-18 17:36:12

整数的大数分解是非常困难的好不好?

litaoye · 发表于 2013-3-18 13:58:00

我倒是用C#写过MPQS用作大数分解，分解2个15位质数的乘积大概2-3s，可能比Mathematica优化过的方法要慢一些。再大的需要用大数，效率下降的比较多。估计10^30左右的大数分解，用这种方法应该是最快的了。还有种连分数分解以及椭圆分解的方法，我没有试过。据说110位以内的数，MPQS比较有优势，再大就需要用数域筛法了。

无心人 · 发表于 2013-3-18 14:09:07

反正现有方法都不能说谁好谁坏一般经过试除去除小因子的数字，先过椭圆曲线，然后，过MPQS，再过NFS 偶尔也用其他一些随机算法

mathematica · 发表于 2013-3-18 14:55:16

5# litaoye 能共享一下你的代码吗?

litaoye · 发表于 2013-3-18 15:29:47

主要是我代码写的比较烂，不太好读，对于比较小的数可能还有些Bug。另外有几道ACM题都是靠这个算法坑人的，贴出来怕就成为水题了。但MPQS主要就涉及3个算法： 1、求平方剩余。 2、质数筛法。 3、高斯消元。另外在选数的范围上有些细节需要注意，此外就没啥特别的了。写MPQS之前可以先从普通的二次筛法开始写，原理一样。也没有选数的问题，写起来还容易。复杂一点的平方剩余那部分也可以用枚举先凑合实现。如果你对于原理和实现上有啥问题，我知道的一定都不会保留。

5# litaoye 能共享一下你的代码吗? mathematica 发表于 2013-3-18 14:55

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

[擂台] 整数分解包括大数

马上注册，结交更多好友，享用更多功能，让你轻松玩转社区。

评分