推荐pari

mathematica

原帖由 无心人 于 2008-11-30 20:20 发表
这个软件我早推荐过了
而且在论坛我还推荐过几个分解数字的软件
和比PARI素性判定更专业的PRIMO

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

你推荐过pari，但是怀疑isPrime函数是确定性算法。
你不觉得矛盾吗？
如果你使用过pari，你能不知道isprime使用的是不是
确定性算法吗？
推荐你去使用一下pari

xiugakei

不知道梅森素数的判定,目前是使用哪种方法？
我有种比较好的方法,不知道是不是已经使用了

无心人

Function: isprime
Section: number_theoretical
C-Name: gisprime
Prototype: GD0,L,
Help: isprime(x,{flag=0}): true(1) if x is a (proven) prime number, false(0)
if not. If flag is 0 or omitted, use a combination of algorithms. If flag is
1, the primality is certified by the Pocklington-Lehmer Test. If flag is 2,
the primality is certified using the APRCL test.
Description:
(int, ?0):bool        isprime(\$1)
(int, 1):bool        plisprime(\$1, 0)
(int, 2):gen        plisprime(\$1, 1)
(gen, ?small):gen        gisprime(\$1, \$2)

mathematica

3.4.35 isprime(x, {flag = 0}): true (1) if x is a prime number, false (0) otherwise. A prime number
is a positive integer having exactly two distinct divisors among the natural numbers, namely 1 and
itself.
This routine proves or disproves rigorously that a number is prime, which can be very slow
when x is indeed prime and has more than 1000 digits, say. Use ispseudoprime to quickly check
for compositeness. See also factor.
If flag = 0, use a combination of Baillie-PSW pseudo primality test (see ispseudoprime),
Selfridge “p − 1” test if x − 1 is smooth enough, and Adleman-Pomerance-Rumely-Cohen-Lenstra
(APRCL) for general x.
If flag = 1, use Selfridge-Pocklington-Lehmer “p − 1” test and output a primality certificate
as follows: return
• 0 if x is composite,
• 1 if x is small enough that passing Baillie-PSW test guarantees its primality (currently
x < 1015),
&#8226; 2 if x is a large prime whose primality could only sensibly be proven (given the algorithms
implemented in PARI) using the APRCL test.
&#8226; Otherwise (x is large and x &#8722; 1 is smooth) output a three column matrix as a primality
certificate. The first column contains prime divisors p of x &#8722; 1 (such that Qpvp(x&#8722;1) > x1/3),
the second the corresponding elements ap as in Proposition 8.3.1 in GTM 138 , and the third the
output of isprime(p,1).
The algorithm fails if one of the pseudo-prime factors is not prime, which is exceedingly unlikely
and well worth a bug report. Note that if you monitor isprime at a high enough debug level, you
may see warnings about untested integers being declared primes. This is normal: we ask for partial
factorisations (sufficient to prove primality if the unfactored part is not too large), and factor
warns us that the cofactor hasn’t been tested. It may or may not be tested later, and may or may
not be prime. This does not affect the validity of the whole isprime procedure.
If flag = 2, use APRCL.
The library syntax is GEN gisprime(GEN x, long flag).

复制后粘贴的结果并不理想，主要是要用数学编辑工具编辑一下，不过我有些懒，同时我也不会
使用，我还是推荐你去读pari的pdf文件！应该能读懂的吧，

无心人

梅森素数的判定是有确定性的特殊方法

无心人

13#是PARI的函数说明

无心人

呵呵
对不起
我只测试小整数的素性
所以并没留意是否确定性
我想，根据你提供的文档确实是确定性的
但我并不推荐用它证明大素数的素性
因为APRCL并不是最快的

PRIMO采用的是先Baillie-PSW后ECPP
比它好
可惜并没有途径获得PRIMO的最新版本
我上载的是一个旧版本

我觉得用PARI作为一个小数字的计算器程序比较合适吧
超过千位并不是你我的机器能处理的范围了

mathematica

如果primo3.0.6是最新版本的，那么我就有最新版本的。
不知道你的是什么版本的。虽然不能访问这个网址
http://www.ellipsa.net/
但是我还是搞到了最新版本的，我想我的版本应该比你的高
吧。
我喜欢先使用ispseudoprime(n),然后再使用
ispseudoprime(n,k)进行k次miller rabin测试，
确定性的算法一般是很慢的，没有太大的意思，所以我
一般都使用ispseudoprime函数，这个函数很双的！！！！

mathematica

我个人觉得素性判定的确定性算法（对于所有的素数，而不是针对类似
梅森数之类的特殊形状的素数！）是不可能在O（logn^3）这个计算量
水平上的！也就是说计算量一定大于概率性的miller rabin测试！
虽然我不能证明，但是我觉得我应该是正确的。我还没有吃晚饭，
我要去吃晚饭了！

无心人

好像ECPP是$O(ln^5 N)$吧
我查了
我上载的是PRIMO 2.01
你能把你的上载么？