mathematica 发表于 2008-11-30 19:00:10

推荐pari

pari是一个很不错的数论计算软件,可以判定一个整数到底是不是素数,
其函数有isprime ,ispseudoprime。还有分解功能,其函数是factor。
是一个免费开源的软件,当然还有很多功能,我只说了对大多数来说,
最感兴趣的功能

mathematica 发表于 2008-11-30 19:00:58

下载地址

http://pari.math.u-bordeaux.fr/

mathematica 发表于 2008-11-30 19:06:32

isprime函数介绍

isprime可以判定一个整数到底是不是素数。
不过判定的时间花费比较长,如果判定一个
1000位的整数,几个小时之内是能搞定的!
但是一般情况下是没有人那么做的。判定百位
的大奇数也是很快的,一分钟这样吧。大家可以
去体验体验。判定的结果是确定的,如果返回结果
是1,那么一定是素数,如果判定结果是0,一定不是
素数。

mathematica 发表于 2008-11-30 19:15:01

ispseudoprime函数介绍

ispseudoprime(n)使用bpsw迅速判定n是不是素数,
使用的是bpsw算法,如果返回结果是0,那么一定不是
素数,如果返回结果是1,那么是素数的可能性很高。
实例体验ispseudoprime(10^200+267)

ispseudoprime(n,k)如果对ispseudoprime(n)返回结
果是1不自信时,可以使用这样的判别方式。
ispseudoprime(n,k)可以对n使用k次miller rabin测试
但是返回结果是1时,并不代表一定是素数,k越大是
素数的可能性越高。
实例体验ispseudoprime(10^200+267,20)

ispseudoprime比isprime快多了,应该说pari的设计思想
是很好的,既有确定性的判定,又有高速的判定,虽然得到
的结果并不一定是正确的,至少我们能够在很大程度上相信
最后的返回结果是正确的,只要你对miller rabin测试有所了解!

mathematica 发表于 2008-11-30 19:31:02

factor函数介绍

factor是分解整数的函数,当然也可以分解多项式。
一般情况下分解的速度是要超过mathematica6.0的,
这是本人的体验!
实例:factor(10^60+1)
结果是






计算时间766ms,不到一秒钟!!!!!!!

结果就不用我解释了吧?前面的代表素数因子,后面的代表个数。
但是返回的结果都是bpsw pseudoprime。可以使用
isprime(%),计算时间16ms,只要第一列都是1,
那么代表分解结果是正确的,第二列不用管它!

应该说软件的设计是很合理的!至少我是很满意的!
就介绍这么多!

mathe 发表于 2008-11-30 19:41:47

原帖由 mathematica 于 2008-11-30 19:06 发表 http://bbs.emath.ac.cn/images/common/back.gif
isprime可以判定一个整数到底是不是素数。
不过判定的时间花费比较长,如果判定一个
1000位的整数,几个小时之内是能搞定的!
但是一般情况下是没有人那么做的。判定百位
的大奇数也是很快的,一分钟这样吧。大家 ...
Are you sure? 1000 bits or 1000 digits?

mathematica 发表于 2008-11-30 19:59:08

我比较确定!!!!

http://pari.math.u-bordeaux.fr/cgi-bin/bugreport.cgi?bug=697&archive=yes
你看一下最下端就可以知道了,下面有一个反馈结果。
我也曾经在网上找到类似的反馈结果,但是现在找不到那个网页了。
一般精神正常的人是不会使用isprime花费几个小时去判定一个千位整数到底
是不是素数。当n是一个很大的整数的时候,我一般先使用ispseudoprime(n),
然后再使用ispseudoprime(n,k)作为补充计算!其中k是miller rabin的测试
次数,你应该对miller rabin出错的概率有所了解吧。我一般会取k为100.
返回的结果是高度可信的!绝对要比hugecalc的好使用,当然我并不是否定
hugecalc!你自己去体验一下吧。由于现在人们能分解的整数也就是百位这样。
所以可以使用isprime验算最后的分解结果,所花费的时间是很少的。因此也是
值得的!

mathematica 发表于 2008-11-30 20:05:34

http://pari.math.u-bordeaux.fr/cgi-bin/bugreport.cgi?bug=697&archive=yes
Fixed in CVS.

(09:07) gp > isprime((6^2176+1)/(6^128+1))      
time = 16h, 10mn, 21,640 ms.
%1 = 1

Thanks for your report,
看到这个结果没有?
(6^2176+1)/(6^128+1)是个1594位整数。我曾经看到一个一千位
的整数判定,使用了4个小时左右的时间,你去网上搜索吧。
用hugecalc8.0的判定时间是10m。
isprime使用的判别方法比较复杂,你可以去看帮助文件。

mathematica 发表于 2008-11-30 20:11:02

我错了!!!!!!!!!!!!!

isprime(10^100+267)的判定时间不到一秒钟!!!!!

无心人 发表于 2008-11-30 20:20:04

这个软件我早推荐过了
而且在论坛我还推荐过几个分解数字的软件
和比PARI素性判定更专业的PRIMO

另外
怀疑你说的isPrime函数是确定性算法
确定性算法目前就三个
分圆域一个,雅克比和一个,椭圆函数一个
目前椭圆函数是最快的
页: [1] 2 3
查看完整版本: 推荐pari