mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Computer Science & Computational Number Theory

Reply
 
Thread Tools
Old 2013-08-06, 17:48   #23
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

38A16 Posts
Default

Quote:
Originally Posted by chris2be8 View Post
One question inspired by that page is can ECPP exploit known factors of n+1 or n-1? Eg cases like R49081 where n-1 has several algebraic factors, but not enough are fully factored to prove it prime by the n-1 method.
This is more a math-of-ECPP question, but to the best of my knowledge, no. We can combine the proofs, but only really in the sense that for any proof that reads "N is prime if Q [and Q2 and Q3...] are prime" we can use ECPP as an option for proving the Q(s) prime. ECPP doesn't operate on n-1 or n+1. My program, like many others, does a quick n-1 and n+1 proof attempt (BLS75 theorems 3 and 15) for each Q, but it is done purely as a time saver, and if we don't use the n-1 or n+1 proof, we don't use the factors found. We use ECPP to give us a list of other numbers we try to partially factor (it's a little different than the BLS75, Pocklington, etc. style proofs in that we're trying to get a single large prime factor, rather than a product of primes).

Last fiddled with by danaj on 2013-08-06 at 17:50 Reason: clarify that factors found in n-1/n+1 are used only if those proofs are used
danaj is offline   Reply With Quote
Old 2013-08-10, 21:00   #24
yoyo
 
yoyo's Avatar
 
Oct 2006
Berlin, Germany

3×197 Posts
Default

Hello,

I did some tests with the 1.01 verions an have some questions:

1) Should it be noticeable faster if I compile and run it on a 64 bit system instead a 32 bit system? Currently I run it on e 32 bit system.

2) How to generate a prime certificate out of it?

yoyo
yoyo is offline   Reply With Quote
Old 2013-08-10, 22:29   #25
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

11100010102 Posts
Default

Quote:
Originally Posted by yoyo View Post
Hello,

I did some tests with the 1.01 verions an have some questions:

1) Should it be noticeable faster if I compile and run it on a 64 bit system instead a 32 bit system? Currently I run it on e 32 bit system.
I know my native code is much faster on x86_64 and Power7 64-bit machines, but that's due to the mulmod code that isn't used by GMP. Almost every machine I have access to now is 64-bit, but I'll dig up an old 32-bit machine and try it out.

Here's something I just tried. It's a 64-bit Windows 7 machine (Intel 3770K) but the compilers I have are using 32-bit for unsigned long. I compiled with Cygwin and under DOS using MinGW (whatever is included with the Strawberry Perl distribution). Cygwin comes out about 3-4x slower than the MinGW compiled code, for the same code on the same machine. This looks pretty repeatable. For a 500-digit number I just ran, the MinGW-compiled code finished the entire proof by the time the Cygwin-compiled version got to the second Q value. So definitely try some different systems out to see which works best.

That isn't a pure 32-bit machine, so in theory GMP would be smart enough to do the right thing in most cases regardless of the compiler's choice. Still, clearly the result is very different. The one machine I do have which is pure 32-bit is an Intel Atom, and it's just sluggish on everything, so I'm not sure how much I'd learn.

Another thing I could do is spend a little more time working on the GMP-ECM integration. It's a bit slower than my p-1 on x86_64 machines for the typical depths I'm using, but I imagine it's well tuned on a larger range of machines and it'll be far better once we need deeper factoring. If I were making a distributed system that was going after quite large numbers, I'd probably just go directly to GMP-ECM as I'd be more interested in getting its factoring prowess on the larger numbers than about it taking 2s vs 1s on the small numbers.

Quote:
2) How to generate a prime certificate out of it?
If you run ecpp-dj with no arguments it should print:
Code:
Usage: standalone/ecpp-dj [options] <number>

Options:
   -v     set verbose
   -V     set extra verbose
   -c     print certificate
   -nm1   use n-1 proof only
   -aks   use AKS for proof
   -help  this message
If you compile with WraithX's APR-CL (put the 3 files in the directory then add -DUSE_APRCL to the Makefile) you can use -aprcl as an option.

Use -c to get a certificate (from the default ECPP or nm1, AKS and APRCL don't give certificates).

The tar file includes a verification program written in Perl, though it requires some additional CPAN modules. It also works for Primo certificates. Alternately you can get my pure GMP verifier here: vcert.c which also does both Primo and MPU certificates.

All the development is done on github, and you can bring up issues there also.
danaj is offline   Reply With Quote
Old 2013-12-23, 22:14   #26
yoyo
 
yoyo's Avatar
 
Oct 2006
Berlin, Germany

3×197 Posts
Default

The smallest PRP in factorDB has currently 2357 digits. How long will it need to calculate a prime certificate for it with ecpp-dj? Does this make sense?
yoyo
yoyo is offline   Reply With Quote
Old 2013-12-23, 23:01   #27
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

11100010102 Posts
Default

Quote:
Originally Posted by yoyo View Post
The smallest PRP in factorDB has currently 2357 digits. How long will it need to calculate a prime certificate for it with ecpp-dj? Does this make sense?
yoyo
It does, but I'll first say that I discussed the Primo proof for that number with Marcel Martin and got a reply. He is going to update his verifier, and I'll update mine and send to Syd so we can handle the proof recent versions of Primo generate for it.
danaj is offline   Reply With Quote
Old 2013-12-24, 12:50   #28
WraithX
 
WraithX's Avatar
 
Mar 2006

1110110002 Posts
Default

Quote:
Originally Posted by danaj View Post
It does, but I'll first say that I discussed the Primo proof for that number with Marcel Martin and got a reply. He is going to update his verifier, and I'll update mine and send to Syd so we can handle the proof recent versions of Primo generate for it.
I saw your email to Marcel, but I never saw a reply to from him. Could you let me know what was discussed so I can make sure my verifier will work with recent versions of Primo?
WraithX is offline   Reply With Quote
Old 2013-12-24, 18:11   #29
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·3·151 Posts
Default

Quote:
Originally Posted by WraithX View Post
I saw your email to Marcel, but I never saw a reply to from him. Could you let me know what was discussed so I can make sure my verifier will work with recent versions of Primo?
I forwarded it to you. S=1 is allowed if all other conditions are met. His email has more details.
danaj is offline   Reply With Quote
Old 2014-08-21, 00:53   #30
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·3·151 Posts
Default

Link to latest version: ecpp-dj.tar.gz

Permission to edit the first post would be nice to allow it to show the latest information.

Version 1.04 has been released.

1.00 June 2013
1.01 July 2013
1.02 <not released>
1.03 April 2014
1.04 August 2014

1.03 added performance enhancements to ECPP. 1.04 has no ECPP changes, but includes spelling changes and an expression parser (thanks to Mathew for corrections and suggestions).


Let me know any suggestions or comments.


Latest performance chart

[i4770K, 4.3GHz, DDR3-2133, GMP 6.0.0a, gcc 4.8.2, Fedora; all single core; average time; 100 random primes to 150 digits, 5 random primes to 2000 digits; GMP versions even for 10-20 digits; ecpp-dj run with large 28M poly set]
danaj is offline   Reply With Quote
Old 2014-08-21, 03:46   #31
Jayder
 
Jayder's Avatar
 
Dec 2012

1000101102 Posts
Default

Thanks for the update! Performance looks nice under 500 digits. I'll see if I can make it and try it out a bit.
Jayder is offline   Reply With Quote
Old 2014-08-21, 05:08   #32
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

16128 Posts
Default

Quote:
Originally Posted by Jayder View Post
Thanks for the update! Performance looks nice under 500 digits.
I find it very useful for my own work, but mpz_aprcl, Pari, and Primo are other good choices. Also note the graph is log-log, so at 500 digits these are all in the 10-15 second range. The graph does a nice job of showing the differences, just keep in mind the scale -- the actual time difference on the low end is quite small, and on the high end what looks like a small difference can be the difference between 1 hour and 3 hours. Primo also comes with multi-threading out of the box.
danaj is offline   Reply With Quote
Old 2014-10-20, 05:31   #33
wombatman
I moo ablest echo power!
 
wombatman's Avatar
 
May 2013

5×347 Posts
Default

Apologies for the dumb question, but does ecpp-dj produce a certificate that can be uploaded directly to FactorDB? I generated a certificate for this number (http://factorization.ath.cx/index.ph...00000718032814) and verified it with vcert.exe, but when I tried to upload it, FactorDB said it couldn't find the input number. I've attached the cert file.
Attached Files
File Type: zip testcert.zip (96.8 KB, 86 views)
wombatman is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
New ECPP record mjm Computer Science & Computational Number Theory 33 2020-02-13 14:50
ECPP on Windows? CRGreathouse Software 10 2015-09-14 12:32
Can I just leave this here? (ECPP) trhabib Miscellaneous Math 6 2011-08-19 16:34
Looking for ECPP software nuggetprime Software 14 2010-03-07 17:09
new ECPP article R. Gerbicz GMP-ECM 2 2006-09-13 16:24

All times are UTC. The time now is 18:36.

Thu Nov 26 18:36:04 UTC 2020 up 77 days, 15:47, 3 users, load averages: 1.40, 1.43, 1.43

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.