primo question

[fivemack]

On a K8/2200, it takes gp 3h15m, and around 600M of memory, to prove the primality of 10^2000-9297.

On a Core2/2400, it takes more than ten hours (it might be 1/3 finished), and between 4G and 5G of memory to prove 10^3000+1027

I have no Windows system so I can't test primo; how long does primo need for these two numbers?

[CRGreathouse]

What system are you using? I'm building a Linux box now (actually I'm having a lot of trouble with my motherboard) and I'm actually looking for good primality proving software.

I'm trying your number with Primo 3.0.2 under Windows Vista Business on one core of a Pentium D @ 2.8 GHz. Memory use is currently very low.

[fivemack]

This is the pari-gp distributed with ubuntu 8.04 (ie 'apt-get install pari-gp')

It took 21h, 42mn, 35,897 ms to do the 3k-digit number, and a peak of 6.1GB memory use.

[CRGreathouse]

That's Pari's isprime()? I'm not actually sure if that proves primality -- documentation suggests at one point that it just does 10 rounds of Miller-Rabin. Let me glance at the source.

What version of Pari do you have? I'm running 2.4.2:

         GP/PARI CALCULATOR Version 2.4.2 (development CHANGES-1.1971)
           i686 running cygwin (ix86/GMP-4.2.1 kernel) 32-bit version
 compiled: Dec 23 2007, gcc-3.4.4 (cygming special, gdc 0.12, using dmd 0.125)
                 (readline v5.2 enabled, extended help enabled)

                     Copyright (C) 2000-2006 The PARI Group

[CRGreathouse]

Huh. The current code works like this:

Numbers below 1: not prime.
Numbers below 103: linear search on a list of the first 26 primes.
Numbers below 10427:* trial division by primes 2 <= p <= 101 with two (64-bit) or four (32-bit) gcd operations and a bitwise AND.
Numbers below 1016801: trial division plus a 2-strong pseudoprime test and a linear search of 26 known 2-pseudoprimes coprime to 101#.
Numbers below 2^32 (32-bit) or 2^64 (64-bit): trial division, a 2-strong pseudoprime test, and a Lucas test.
Numbers below 10^15 (32-bit):** trial division, 2-strong pseudoprime test, Lucas test.
Larger numbers: trial division, 2-strong pseudoprime test, Lucas test, and either Pocklington-Lehmer p-1 (for smooth or half-smooth n-1) or APRCL (otherwise).

So yes, isprime() does prove primality. I wonder why the function list says otherwise... I guess that's a change since 2.1.4.

Edit: heh, I could have saved some time if I'd just read the current documentation:

[U]se 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.

* Why this constant is chosen rather than 10609 is beyond me.
** This seems a little odd: if LONG_IS_64BIT, then trial division + 2-strong pseudoprime + Lucas is sufficient up to 2^64 ~= 1.8e19, but if not then it's sufficient only up to 10^15.

[ATH]

Primo 3.0.6 32bit on 1 core of Q9450 2.66Ghz (Windows XP 64bit):

10^2000-9297: 5h59m38s
First 30min it used 18Mb ram, after that I didn't check.

[ET_]

Originally Posted by ATH

Primo 3.0.6 32bit on 1 core of Q9450 2.66Ghz (Windows XP 64bit):

10^2000-9297: 5h59m38s
First 30min it used 18Mb ram, after that I didn't check.

Are you saying that Primo is twice as slow as Pari-GP?

Luigi

[Joshua2]

Well, it is a different processor, and I have heard amd are better at sieving and primo, but still...

[ET_]

Originally Posted by Joshua2

Well, it is a different processor, and I have heard amd are better at sieving and primo, but still...

Well, Primo uses ECPP while Pari a mixture of factorization, lucas tests and APRCL, so we're basically comparing apples to oranges, but still...

Luigi

[CRGreathouse]

Originally Posted by ET_

Well, Primo uses ECPP while Pari a mixture of factorization, lucas tests and APRCL, so we're basically comparing apples to oranges, but still...

Primo uses ECPP (and also performs a 2-strong pseudoprime test). Pari* uses APRCL (and also performs a 2-strong pesudoprime test and Lucas). The pseuoprime tests don't add anything relevant to the runtime -- milliseconds out of hours.

* recent versions, when factoring numbers n > 10^15 where n-1 is not particularly smooth.

[philmoore]

I'm not real knowledgeable in this area, but based on comments I have seen of others, I wouldn't be surprised to learn that APRCL is more efficient than ECPP for numbers in this range. For larger numbers, ECPP is faster.