Primo

[henryzz]

Originally Posted by danaj

Primo has so many more discriminants available that numbers this size are simple.

What would it take to add more discriminants? Most of us wouldn't mind having a huge file around. Is it calculation it needs?

[danaj]

Originally Posted by henryzz

What would it take to add more discriminants? Most of us wouldn't mind having a huge file around. Is it calculation it needs?

First, I'm not sure if we're hijacking this thread. It looked off-topic for some time, but maybe a different thread should be made?

More polynomials -- well, more computation in theory could do it and I could work on that. At some point it's going to be hard to have enough. Here's a quote from Marcel Martin in 2001:

I will not change my position. Small disc table + Backtracking is a loosing strategy. Backtracking is useful to compensate the fact that a software has no arbitrary length floating-point library on board and, thus, cannot build polynomials on the fly. Backtracking is nothing but a crutch.

For those of us just starting, sometimes crutches are the only things that let us take our first steps.

From the literature, Weber polynomials should be able to be computed in a reasonable amount of time. GNU MPFR has a lot more functionality than GMP's mpf, and would make things much easier.

Also, lest someone misunderstand what I said earlier, there's a lot more to Primo than just many more discriminants. A limited set is the bottleneck for my software at this point as the numbers get larger, but it's not a panacea for huge numbers. In many ways I've not even matched Morain's 1993 work (and clearly I have the advantage of far more memory, GMP, and their paper to peruse). On the other hand, it is much faster than GMP-ECPP and given GMP, it's pretty portable.

[yoyo]

Originally Posted by danaj

I'm not sure how much people care, but I have an open source ECPP implementation that is much faster than GMP-ECPP, and doesn't use gmpxx. It runs on 32-bit and 64-bit machines, including Win32 (command line). It would take a little massaging to turn into a standlone program (it is part of a Perl module now). If anyone wanted, I could do it.

I would be interested to get a command line version and the source code for it so I can Boincify it for win 32/64 and Linux 32/64 to create prime certificates for the PRP in factordb:
http://factorization.ath.cx/listtype.php?t=1

yoyo

[Stargate38]

Me too, especially the source code.

[danaj]

Originally Posted by Stargate38

Me too, especially the source code.

The main thread is here: ECPP-DJ

Version 1.01 is the latest, with a link later in the thread. I made a link so the latest version is always here: ecpp-dj.tar.gz

I am distributing it with the Perl license (user chooses Artistic License or GPL) but could be convinced to switch to LGPLv3 (the same license used by GMP) instead if people prefer that.

Performance chart: [image]
I didn't include Primo but I expect it would be faster than anything else once past 350 digits or so. Pari's APR-CL is also faster than WraithX's APR-CL but the code isn't exactly portable outside of Pari. GMP-ECPP is taking multiple days to get results that APR-CL and ECPP-DJ take ~1 minute on, so I'm going to kill it soon just to get my computer back.

The next release will have more discriminants (I'm up to about 16000 to choose from), with a different set chosen. I'm using Atkin/Morain's idea of prioritizing H/G (used for selection of source candidates, but I use strictly H ordering while running). I've also got D%3=0 Weber root conversion code so I can use many more Weber polys (saves space and time).


More on topic for this thread, I've also written a standalone certificate verifier in C+GMP. It handles both Primo and MPU formats, and is pretty fast (if I get projective EC working it will be even faster; everything should be present in the source, if you get it working please share). vcert-0.9.c

Since verification is crucial, let me know if you see any issues.

[danaj]

This entry is giving Primo 4.0.4 some problems:

1100000000301279543

Can't seem to find a working discriminant even after trying 33 bits (2 passes). It ends with "ABORTED DUE TO INTERNAL ERROR 1.17.102.1"

I used ecpp-dj to get this proof, albeit ~7 hours on one core.

[mjm]

Can't seem to find a working discriminant even after trying 33 bits (2 passes).

I guess you made use of (11000,32) as parameters. For a 2000 digit number, Primo does not sieve more than with, say, (5000,26).
(11000,32) means "uses 2^32 with numbers having 11000 digits or more".

I certified your number in about 20 minutes with Primo 4.0.4.
I set (2000,32) as parameters, I aborted once a step was found and I resumed with the default parameters (5000,26).

It ends with "ABORTED DUE TO INTERNAL ERROR 1.17.102.1"

It looks like a bug.

[danaj]

Originally Posted by mjm

I certified your number in about 20 minutes with Primo 4.0.4.
I set (2000,32) as parameters, I aborted once a step was found and I resumed with the default parameters (5000,26).

Very nice. Thanks for the help with parameters -- I just reread the manual as well.

I had tried numerous smaller settings, all of which failed for me, but your suggestion of 2000,32 did finally get the first step after 12 minutes on 8 cores. Running with 2000,27 also worked well and finishes much faster: 31 minutes on 8 cores.

[Puzzle-Peter]

This is really interesting. I tried to certify this number a few weeks ago, still using v4.0.1 and it wouldn't work. So v4.0.4 is more than only speed optimization.

I'll switch to v4.0.4 as soon as my currently running tests are finished.

[ET_]

Originally Posted by Puzzle-Peter

This is really interesting. I tried to certify this number a few weeks ago, still using v4.0.1 and it wouldn't work. So v4.0.4 is more than only speed optimization.

I'll switch to v4.0.4 as soon as my currently running tests are finished.

Primo v4.0.5 (November 7, 2013)

Fixed a bug that could raise the internal error 1.17.102.1 during the phase 1.

[danaj]

Originally Posted by ET_

Primo v4.0.5 (November 7, 2013)

Thanks!