mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2009-01-28, 10:48   #1
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

632310 Posts
Default primo question

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?
fivemack is offline   Reply With Quote
Old 2009-01-28, 15:11   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·2,969 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Old 2009-01-28, 22:18   #3
fivemack
(loop (#_fork))
 
fivemack's Avatar
 
Feb 2006
Cambridge, England

6,323 Posts
Default

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.
fivemack is offline   Reply With Quote
Old 2009-01-29, 00:11   #4
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×2,969 Posts
Default

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:
Code:
         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 is offline   Reply With Quote
Old 2009-01-29, 01:08   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

173216 Posts
Default

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:
Quote:
[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.

Last fiddled with by CRGreathouse on 2009-01-29 at 01:27 Reason: RTM
CRGreathouse is offline   Reply With Quote
Old 2009-01-29, 08:23   #6
ATH
Einyen
 
ATH's Avatar
 
Dec 2003
Denmark

32·331 Posts
Default

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.
ATH is offline   Reply With Quote
Old 2009-01-29, 10:24   #7
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

13·367 Posts
Default

Quote:
Originally Posted by ATH View Post
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
ET_ is offline   Reply With Quote
Old 2009-01-29, 16:25   #8
Joshua2
 
Joshua2's Avatar
 
Sep 2004

13·41 Posts
Default

Well, it is a different processor, and I have heard amd are better at sieving and primo, but still...
Joshua2 is offline   Reply With Quote
Old 2009-01-29, 16:35   #9
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

13×367 Posts
Default

Quote:
Originally Posted by Joshua2 View Post
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
ET_ is offline   Reply With Quote
Old 2009-01-29, 17:02   #10
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·2,969 Posts
Default

Quote:
Originally Posted by ET_ View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2009-01-29, 20:01   #11
philmoore
 
philmoore's Avatar
 
"Phil"
Sep 2002
Tracktown, U.S.A.

100010111002 Posts
Default

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.
philmoore is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Primo ET_ FactorDB 126 2020-02-06 17:31
Primo Interrupted Runs a1call Information & Answers 32 2016-12-11 10:48
Primo Browser? PawnProver44 Information & Answers 14 2016-04-09 05:49
Primo Verifier... WraithX Software 15 2013-09-10 07:24
PRIMO 3.0.7 Cybertronic Five or Bust - The Dual Sierpinski Problem 17 2009-08-13 20:42

All times are UTC. The time now is 03:19.

Wed Nov 25 03:19:52 UTC 2020 up 76 days, 30 mins, 4 users, load averages: 1.85, 1.85, 1.63

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.