FastECPP software and 50000 digit primality proof (reposted from NMBRTHRY)

[frmky]

Here's a small change that will allow idle MPI workers to yield their core. I've sent this to Andreas in case he wants to use it. With this change I can use one worker per hyperthread without slowing the end of phase 2.

--- lib/mpi.c.orig      2022-05-11 10:13:12.940302581 -0700
+++ lib/mpi.c   2022-05-11 11:26:12.823859553 -0700
@@ -555,6 +555,12 @@
    finish = false;
    while (!finish) {
       /* Wait for a message from the server. */
+      int message_ready = 0;
+      MPI_Iprobe(0, MPI_ANY_TAG, MPI_COMM_WORLD, &message_ready, &status);
+      while (!message_ready) {
+         usleep(100);
+         MPI_Iprobe(0, MPI_ANY_TAG, MPI_COMM_WORLD, &message_ready, &status);
+      }
       MPI_Recv (&job, 1, MPI_INT, 0, MPI_ANY_TAG, MPI_COMM_WORLD, &status);
       cm_stat_init (stat);
       switch (status.MPI_TAG) {

[paulunderwood]

I noticed that some numbers stall the program, like (10^79-1)/9. Primo does a BPSW sanity test before ECPP.

@Serge: The 50001 digit ECPP proof is still not in the UTM database. You had better ask Andreas to go through the submission process -- unless CC is on holiday or something.

[Batalov]

I will write to him. (I've also already invited him to join the forum. There is a good source of debug/improvement cases here for him.)

So far, I had good exchange about the backtrack (indeed, in future plans; at this point the code relies on the fact that it will sooner or later find the step unlike Primo that had finite set of invariants/curves/test units).

[xilman]

--- Total time for ECPP: 976676.0 (197674.8)
--- Time for ECPP check (true): 15687.0

real 1373m20.172s
user 8416m44.292s
sys 2m44.721s

[ixfd64]

Two more questions:

1. How is ecpp able to generate Primo certificates?

To my knowledge, Primo is closed source. Did the author of ecpp reverse-engineer Primo, or did Martin also contribute code?

2. I checked the source code and noticed that this program is written in pure C. Could it benefit from hand-tuned assembly like Prime95 does?

[Batalov]

Originally Posted by ixfd64

1. How is ecpp able to generate Primo certificates?

To my knowledge, Primo is closed source. Did the author of ecpp reverse-engineer Primo, or did Martin also contribute code?

Implementation is closed source (pssst: it is coded in Pascal for some reason, Primo, that is) but the certificate format is well described and community accepted. It describes the curve and point (partial case, N ± 1 steps, when they apply). That is why Pari/gp validator existed for ages, regardless of a competitive implementation. Markus was using it for years.

[frmky]

Originally Posted by ixfd64

2. I checked the source code and noticed that this program is written in pure C. Could it benefit from hand-tuned assembly like Prime95 does?

It is built on GMP and MPFR, which are well optimized for common architectures.

[ixfd64]

I see, thanks for the information.

I figured the Primo format was an open specification but didn't see anything about it in the ecpp documentation.

[frmky]

ecpp only outputs Pari/gp format. Pari/gp supports converting that to Primo format.

[mathwiz]

This is pretty awesome. An open source ECPP implementation that is fast, pure C, and highly scalable with MPI.

Can't wait to see how this gets extended and improved. Hats off to Andreas!

[ldesnogu]

Originally Posted by frmky

It is built on GMP and MPFR, which are well optimized for common architectures.

I wonder what proportion of its speed compared to Primo comes from using these highly tuned libs vs ECPP specific algorithmic improvements (all of which are described in available publications, if my very limited understanding is correct).