primo question - Page 2

schickel · 2009-01-30, 07:41

Quote:

Originally Posted by 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?

This is for WinXP Home SP3, Celeron 3.06 GHz, 2 Gigs RAM. And, not knowing how much of a load it is, it's running a wireless USB access point to bridge my upstairs/downstairs network segments....

This is for the first one:

Code:

Selected=1
Processed=1
Certified=1
Candidate #1=Certified, 10h 53mn 40s

I can run the other one if you need the other datapaoint.

fivemack · 2009-01-30, 11:03

I would be quite interested in the primo timings for 10^3000+1027, and indeed 10^4000+16483, though I suspect the latter will be at least a week's computation.

It seems that ECPP is presently in the slightly frustrating state that the NFS was prior to ggnfs, and the NFS with parallel linear algebra is now: there is evidence in the literature of several careful and fast implementations, none of which is available as unimpeded source code. Maybe now that there's less belief that Cryptography is the way to endless wealth, ECPP and elliptic-curve point counting algorithms can return to the realm of mathematical software.

pari-gp probably does count as a careful implementation of APRCL with unimpeded source code (it's a step-by-step implementation of the algorithm as given in Cohen's book, down to the function names), and the underlying libraries are fast, though I can't quite see where the terrifying memory requirements come from, and it would be nice (and probably even also possible

) to parallelize the search over q in step 4.

CRGreathouse · 2009-01-30, 15:00

Quote:

Originally Posted by 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?

Primo 3.0.2 on one core of a Pentium D 915 @ 2.8 GHz under Windows Vista Business (32-bit):
10^2000-9297: 12h08m07s
10^3000+1027: not finished -- 9386/9966 bits after 24:48:30

Pari 2.4.2 on one core of a Pentium D 915 @ 2.8 GHz under Windows Vista Business (32-bit):
10^2000-9297: failed with "*** isprime: zero argument in factorint." after 8-20 hours.

alpertron · 2009-01-30, 17:14

Notice that APR-CL does not generate results that can be verified by an independent program, so you need to be sure that your computer is stable enough (no overclocking is better, and do not run it on Summer time).

schickel · 2009-01-30, 17:43

Quote:

Originally Posted by fivemack

I would be quite interested in the primo timings for 10^3000+1027, and indeed 10^4000+16483, though I suspect the latter will be at least a week's computation.

OK, give me a day or two while I run a c110 through a quick NFS job and I'll get back to you....

schickel · 2009-01-31, 11:03

Crud, wouldn't you know it, I have 6 certs from Primo that I generated in 2006, but there are no timings in the cert files.....I did one whopper of a job at 3812 digits on a 2+ GHz Win98 system, but I don't have the slightest idea how long it took (other than a veeeeeerrrryyyy loooonnggg time). This was the result:

Code:

Version=2.3.1

Created=10/03/2006 02:21:17 pm
TestCount=535
Status=Candidate certified prime

Expression=3^7989-2

HexadecimalSize=3166
DecimalSize=3812
BinarySize=12663

ATH · 2009-01-31, 15:29

I have Primo running in 39h now on 10^3000+1027, and its still phase1 at bits 3714/9966.

ATH · 2009-02-01, 13:42

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

10^3000+1027: 52h 53min
Max mem usage was during phase2 around 29Mb.

I did use some games and programs on other cores during this test (didn't on 10^2000-9297), dunno how much it slowed it down, primo was always showing 25% usage (100% of 1 core).

ATH · 2009-02-02, 15:18

Did 2 more timings, so the 4 timings so far:

10^1500+2329: 2h3m
10^2000-9297: 5h59m
10^2500+11859: 18h51m
10^3000+1027: 52h53m

This fits pretty good with: time = k * a^log(n) for number n.

R.D. Silverman · 2009-02-02, 15:42

Quote:

Originally Posted by ATH

Did 2 more timings, so the 4 timings so far:

10^1500+2329: 2h3m
10^2000-9297: 5h59m
10^2500+11859: 18h51m
10^3000+1027: 52h53m

This fits pretty good with: time = k * a^log(n) for number n.

May I suggest that you read my paper "A Perspective on
Computational Number Theory", in Notices of the AMS (I don't
recall the exact year; around 1990). It discusses the dangers of
"curve-fitting" in the manner you suggest above.

Assuming that primo uses ECPP, the run time should scale as
log(n)^{c + o(1)) . The value of c will be implementation dependent.
c = 4 is achievable in practice (but not fully proved). Also, the "constant"
k that you use probably is not a constant, but rather a multipler that
depends on the size of n. [thus the o(1) that I suggest]. It may
change too slowly for you to nice over the range of numbers that you
are testing.

ECPP is polynomial in the size of the problem. The degree of the polynomial
will be implementation dependent.

fivemack · 2009-02-02, 16:02

I tried running some large numbers with APRCL under pari over the weekend on a 16G machine here, but everything got horribly stuck while computing the e(t) values, since (beyond the hard-wired table which is usable only to 1000 digits) pari finds a usable e(t) by computing e(t) for all multiples of 840 greater than 10^8 to full precision (rather than using logarithms), and this unsurprisingly takes too long. Also generates >4GB of log file since computing e(t) requires incremental calls to isprime which log the process of factorising p-1

I get the feeling nobody expected me to use pari on primes >10kbit ...

I've computed incremental-maxima of log e(t) with my own code for all t<10^9 and am doing it for t<10^11 divisible by 5040 (since, below 10^9, all e(t)>10^1500 had 5040|t), which should be enough for APRCL up to >5k digits, but I'll have to put in a patch and build a new version of pari before I can do particularly sensible timings even about 1500 digits.

So, thanks very much for the timings so far, but I'm afraid I won't have comparable pari timings for several days, maybe not until next weekend

2009-01-30, 11:03	#13
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 6419₁₀ Posts	I would be quite interested in the primo timings for 10^3000+1027, and indeed 10^4000+16483, though I suspect the latter will be at least a week's computation. It seems that ECPP is presently in the slightly frustrating state that the NFS was prior to ggnfs, and the NFS with parallel linear algebra is now: there is evidence in the literature of several careful and fast implementations, none of which is available as unimpeded source code. Maybe now that there's less belief that Cryptography is the way to endless wealth, ECPP and elliptic-curve point counting algorithms can return to the realm of mathematical software. pari-gp probably does count as a careful implementation of APRCL with unimpeded source code (it's a step-by-step implementation of the algorithm as given in Cohen's book, down to the function names), and the underlying libraries are fast, though I can't quite see where the terrifying memory requirements come from, and it would be nice (and probably even also possible ) to parallelize the search over q in step 4. Last fiddled with by fivemack on 2009-01-30 at 11:05

2009-01-31, 11:03	#17
schickel "Frank <^>" Dec 2004 CDP Janesville 2×1,061 Posts	Crud, wouldn't you know it, I have 6 certs from Primo that I generated in 2006, but there are no timings in the cert files.....I did one whopper of a job at 3812 digits on a 2+ GHz Win98 system, but I don't have the slightest idea how long it took (other than a veeeeeerrrryyyy loooonnggg time). This was the result: Code: Version=2.3.1 Created=10/03/2006 02:21:17 pm TestCount=535 Status=Candidate certified prime Expression=3^7989-2 HexadecimalSize=3166 DecimalSize=3812 BinarySize=12663

2009-02-02, 16:02	#22
fivemack (loop (#_fork)) Feb 2006 Cambridge, England 7²×131 Posts	silly performance-bug in pari aprcl I tried running some large numbers with APRCL under pari over the weekend on a 16G machine here, but everything got horribly stuck while computing the e(t) values, since (beyond the hard-wired table which is usable only to 1000 digits) pari finds a usable e(t) by computing e(t) for all multiples of 840 greater than 10^8 to full precision (rather than using logarithms), and this unsurprisingly takes too long. Also generates >4GB of log file since computing e(t) requires incremental calls to isprime which log the process of factorising p-1 I get the feeling nobody expected me to use pari on primes >10kbit ... I've computed incremental-maxima of log e(t) with my own code for all t<10^9 and am doing it for t<10^11 divisible by 5040 (since, below 10^9, all e(t)>10^1500 had 5040\|t), which should be enough for APRCL up to >5k digits, but I'll have to put in a patch and build a new version of pari before I can do particularly sensible timings even about 1500 digits. So, thanks very much for the timings so far, but I'm afraid I won't have comparable pari timings for several days, maybe not until next weekend

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Primo	ET_	FactorDB	163	2021-06-02 09:14
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

2009-01-30, 17:14	#15
alpertron Aug 2002 Buenos Aires, Argentina 1366₁₀ Posts	Notice that APR-CL does not generate results that can be verified by an independent program, so you need to be sure that your computer is stable enough (no overclocking is better, and do not run it on Summer time).

2009-01-31, 15:29	#18
ATH Einyen Dec 2003 Denmark 110001010111₂ Posts	I have Primo running in 39h now on 10^3000+1027, and its still phase1 at bits 3714/9966.

2009-02-01, 13:42	#19
ATH Einyen Dec 2003 Denmark 3⁵·13 Posts	Primo 3.0.6 32bit on 1 core of Q9450 2.66Ghz (Windows XP 64bit): 10^3000+1027: 52h 53min Max mem usage was during phase2 around 29Mb. I did use some games and programs on other cores during this test (didn't on 10^2000-9297), dunno how much it slowed it down, primo was always showing 25% usage (100% of 1 core).

2009-02-02, 15:18	#20
ATH Einyen Dec 2003 Denmark 6127₈ Posts	Did 2 more timings, so the 4 timings so far: 10^1500+2329: 2h3m 10^2000-9297: 5h59m 10^2500+11859: 18h51m 10^3000+1027: 52h53m This fits pretty good with: time = k * a^log(n) for number n.