推荐pari

/相

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

dingji

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

ifequwu

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

ugetetip

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测试有所了解！

erawaliktevi

factor是分解整数的函数，当然也可以分解多项式。
一般情况下分解的速度是要超过mathematica6.0的，
这是本人的体验！
实例：factor(10^60+1)
结果是
[73,1]
[137,1]
[1676321,1]
[99990001,1]
[5964848081,1]
[100009999999899989999000000010001,1]
计算时间766ms，不到一秒钟！！！！！！！

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

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

edzugxoggixo

原帖由 mathematica 于 2008-11-30 19:06 发表
isprime可以判定一个整数到底是不是素数。
不过判定的时间花费比较长，如果判定一个
1000位的整数，几个小时之内是能搞定的！
但是一般情况下是没有人那么做的。判定百位
的大奇数也是很快的，一分钟这样吧。大家 ...

Are you sure? 1000 bits or 1000 digits?

akomosuse

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

efaugko

http://pari.math.u-bordeaux.fr/c ... 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使用的判别方法比较复杂，你可以去看帮助文件。

xiaobai

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

ebirugerxos

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

另外
怀疑你说的isPrime函数是确定性算法
确定性算法目前就三个
分圆域一个，雅克比和一个，椭圆函数一个
目前椭圆函数是最快的