mersenneforum.org ECPP-DJ
 User Name Remember Me? Password
 Register FAQ Search Today's Posts Mark Forums Read

2013-08-06, 17:48   #23
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

38A16 Posts

Quote:
 Originally Posted by chris2be8 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

 2013-08-10, 21:00 #24 yoyo     Oct 2006 Berlin, Germany 3×197 Posts 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
2013-08-10, 22:29   #25
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

11100010102 Posts

Quote:
 Originally Posted by yoyo 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.

 2013-12-23, 22:14 #26 yoyo     Oct 2006 Berlin, Germany 3×197 Posts 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
2013-12-23, 23:01   #27
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

11100010102 Posts

Quote:
 Originally Posted by yoyo 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.

2013-12-24, 12:50   #28
WraithX

Mar 2006

1110110002 Posts

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

2013-12-24, 18:11   #29
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

2·3·151 Posts

Quote:
 Originally Posted by WraithX 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.

 2014-08-21, 00:53 #30 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 2·3·151 Posts 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 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]
 2014-08-21, 03:46 #31 Jayder     Dec 2012 1000101102 Posts Thanks for the update! Performance looks nice under 500 digits. I'll see if I can make it and try it out a bit.
2014-08-21, 05:08   #32
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

16128 Posts

Quote:
 Originally Posted by Jayder 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.

2014-10-20, 05:31   #33
wombatman
I moo ablest echo power!

May 2013

5×347 Posts

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
 testcert.zip (96.8 KB, 86 views)

 Similar Threads Thread Thread Starter Forum Replies Last Post mjm Computer Science & Computational Number Theory 33 2020-02-13 14:50 CRGreathouse Software 10 2015-09-14 12:32 trhabib Miscellaneous Math 6 2011-08-19 16:34 nuggetprime Software 14 2010-03-07 17:09 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