整数分解包括大数

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

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

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

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

评分