20090128, 10:48  #1 
(loop (#_fork))
Feb 2006
Cambridge, England
6323_{10} Posts 
primo question
On a K8/2200, it takes gp 3h15m, and around 600M of memory, to prove the primality of 10^20009297.
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? 
20090128, 15:11  #2 
Aug 2006
2·2,969 Posts 
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. 
20090128, 22:18  #3 
(loop (#_fork))
Feb 2006
Cambridge, England
6,323 Posts 
This is the parigp distributed with ubuntu 8.04 (ie 'aptget install parigp')
It took 21h, 42mn, 35,897 ms to do the 3kdigit number, and a peak of 6.1GB memory use. 
20090129, 00:11  #4 
Aug 2006
2×2,969 Posts 
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 MillerRabin. Let me glance at the source.
What version of Pari do you have? I'm running 2.4.2: Code:
GP/PARI CALCULATOR Version 2.4.2 (development CHANGES1.1971) i686 running cygwin (ix86/GMP4.2.1 kernel) 32bit version compiled: Dec 23 2007, gcc3.4.4 (cygming special, gdc 0.12, using dmd 0.125) (readline v5.2 enabled, extended help enabled) Copyright (C) 20002006 The PARI Group 
20090129, 01:08  #5  
Aug 2006
1732_{16} Posts 
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 (64bit) or four (32bit) gcd operations and a bitwise AND. Numbers below 1016801: trial division plus a 2strong pseudoprime test and a linear search of 26 known 2pseudoprimes coprime to 101#. Numbers below 2^32 (32bit) or 2^64 (64bit): trial division, a 2strong pseudoprime test, and a Lucas test. Numbers below 10^15 (32bit):** trial division, 2strong pseudoprime test, Lucas test. Larger numbers: trial division, 2strong pseudoprime test, Lucas test, and either PocklingtonLehmer p1 (for smooth or halfsmooth n1) 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: Quote:
** This seems a little odd: if LONG_IS_64BIT, then trial division + 2strong pseudoprime + Lucas is sufficient up to 2^64 ~= 1.8e19, but if not then it's sufficient only up to 10^15. Last fiddled with by CRGreathouse on 20090129 at 01:27 Reason: RTM 

20090129, 08:23  #6 
Einyen
Dec 2003
Denmark
3^{2}·331 Posts 
Primo 3.0.6 32bit on 1 core of Q9450 2.66Ghz (Windows XP 64bit):
10^20009297: 5h59m38s First 30min it used 18Mb ram, after that I didn't check. 
20090129, 10:24  #7 
Banned
"Luigi"
Aug 2002
Team Italia
13·367 Posts 

20090129, 16:25  #8 
Sep 2004
13·41 Posts 
Well, it is a different processor, and I have heard amd are better at sieving and primo, but still...

20090129, 16:35  #9 
Banned
"Luigi"
Aug 2002
Team Italia
13×367 Posts 

20090129, 17:02  #10  
Aug 2006
2·2,969 Posts 
Quote:
* recent versions, when factoring numbers n > 10^15 where n1 is not particularly smooth. 

20090129, 20:01  #11 
"Phil"
Sep 2002
Tracktown, U.S.A.
10001011100_{2} Posts 
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.

Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Primo  ET_  FactorDB  126  20200206 17:31 
Primo Interrupted Runs  a1call  Information & Answers  32  20161211 10:48 
Primo Browser?  PawnProver44  Information & Answers  14  20160409 05:49 
Primo Verifier...  WraithX  Software  15  20130910 07:24 
PRIMO 3.0.7  Cybertronic  Five or Bust  The Dual Sierpinski Problem  17  20090813 20:42 