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

[paulunderwood]

Originally Posted by xilman

Anyone any idea how long it generally takes factordb to verify a certificate?

3178^1543+1543^3178 is still in the Processing state.

System load
Load average, last minute 25.75
Load average, last 5 minutes 26.17
Load average, last 15 minutes 26.76

(FactorDB)

[Batalov]

Reposting an update from Andreas (this is re: "some stage 1 steps may search quite long"; now shorter)

Am Thu, May 12, 2022 at 10:49:11AM +0200 schrieb Andreas Enge:
> Instead of backtracking, I noticed that I could also relax some
> constraints in my code.

this is now implemented, and can be downloaded from the git or as a
tarball from the website at
https://www.multiprecision.org/cm/

Thanks for the report, which forced me to address this known problem!

As said, I do not intend to implement backtracking :)
If you happen to come along a new problematic number that is not gracefully handled by the new implementation, please do not hesitate to complain.

Enjoy the weekend,
Andreas

Refresh your copy of the code. - the corresponding version can also be downloaded as a tarball with a signature.

[Batalov]

Originally Posted by xilman

Anyone any idea how long it generally takes factordb to verify a certificate?

3178^1543+1543^3178 is still in the Processing state.

The 50001-digit cert verified in just a day or two. I've seen some Primo certs (much smaller) to take way longer to verify.

[xilman]

Originally Posted by Batalov

Reposting an update from Andreas (this is re: "some stage 1 steps may search quite long"; now shorter)

Refresh your copy of the code. - the corresponding version can also be downloaded as a tarball with a signature.

Anyone had problems with the git version?

There is no configure script, which is fair enough, but running autoconf produces

pcl@thoth:~/nums/cm$ autoconf
configure.ac:29: error: possibly undefined macro: AM_INIT_AUTOMAKE
      If this token and others are legitimate, please use m4_pattern_allow.
      See the Autoconf documentation.
configure.ac:30: error: possibly undefined macro: AM_MAINTAINER_MODE
configure.ac:92: error: possibly undefined macro: AM_CONDITIONAL
pcl@thoth:~/nums/cm$ ./configure
configure: error: cannot find required auxiliary files: config.guess config.sub
pcl@thoth:~/nums/cm$

Not entirely sure what to do next.

[xilman]

Originally Posted by xilman

Anyone had problems with the git version?

There is no configure script, which is fair enough, but running autoconf produces

pcl@thoth:~/nums/cm$ autoconf
configure.ac:29: error: possibly undefined macro: AM_INIT_AUTOMAKE
      If this token and others are legitimate, please use m4_pattern_allow.
      See the Autoconf documentation.
configure.ac:30: error: possibly undefined macro: AM_MAINTAINER_MODE
configure.ac:92: error: possibly undefined macro: AM_CONDITIONAL
pcl@thoth:~/nums/cm$ ./configure
configure: error: cannot find required auxiliary files: config.guess config.sub
pcl@thoth:~/nums/cm$

Not entirely sure what to do next.

Remembered to start with aclocal (doh!) but now get

pcl@thoth:~/nums/cm$ ./configure
configure: error: cannot find required auxiliary files: ltmain.sh compile config.guess config.sub missing install-sh
pcl@thoth:~/nums/cm$

[WraithX]

Originally Posted by xilman

Remembered to start with aclocal (doh!) but now get

pcl@thoth:~/nums/cm$ ./configure
configure: error: cannot find required auxiliary files: ltmain.sh compile config.guess config.sub missing install-sh
pcl@thoth:~/nums/cm$

Not sure how much this will help, but here are some notes from the gmp-ecm README.dev file:

To use the autotools:

$ libtoolize
$ autoheader
$ aclocal
$ automake -c -a
$ autoconf
$ ./configure --with-gmp=<directory_where_gmp_is_installed>
$ make
$ make check

Alternatively, you can simply type:

$ autoreconf -i
$ ./configure --with-gmp=<directory_where_gmp_is_installed>
$ make
$ make check

Perhaps some combination of the first group of instructions will help? :fingerscrossed: At least until someone more knowledgeable chimes in.

[xilman]

Originally Posted by WraithX

Not sure how much this will help, but here are some notes from the gmp-ecm README.dev file:

To use the autotools:

$ libtoolize
$ autoheader
$ aclocal
$ automake -c -a
$ autoconf
$ ./configure --with-gmp=<directory_where_gmp_is_installed>
$ make
$ make check

Alternatively, you can simply type:

$ autoreconf -i
$ ./configure --with-gmp=<directory_where_gmp_is_installed>
$ make
$ make check

Perhaps some combination of the first group of instructions will help? :fingerscrossed: At least until someone more knowledgeable chimes in.

Andreas got back to me. The magic incantation is "autoreconf -vfi". A "git reset --hard" afterwards is advisable too.

[R. Gerbicz]

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

Yeah. One very "trivial" improvement would come to call a faster prp routine, so not call the gmp's built-in mpz_probab_prime_p function. Maybe use pfgw, or directly using the gw library. Notice that the prp is costly in ecpp on all sizes, takes also O(log(N)^(4+eps)) time.
[For small numbers you can keep the gmp's routine, if that is the faster/fastest].

I have some other ideas on the code also, only what I can understand..

[Batalov]

Originally Posted by xilman

Andreas got back to me. The magic incantation is "autoreconf -vfi". A "git reset --hard" afterwards is advisable too.

I diffed all *.c and *.h files between two branches (and there were only 2 *.c files) - and then moved them to the branch were last build was. And then rebuilt there.
This is admittedly simplistic, but worked for this small change.

find . -name \*.[ch] -exec cmp ../cm0.4.0/{} {} \;
diff ...
diff ...

[paulunderwood]

Originally Posted by R. Gerbicz

Yeah. One very "trivial" improvement would come to call a faster prp routine, so not call the gmp's built-in mpz_probab_prime_p function. Maybe use pfgw, or directly using the gw library. Notice that the prp is costly in ecpp on all sizes, takes also O(log(N)^(4+eps)) time.
[For small numbers you can keep the gmp's routine, if that is the faster/fastest].

I have some other ideas on the code also, only what I can understand..

I tried unsuccessfully to get a return value from a system call to pfgw.

Now i have written gwnum code, but have no idea where to add a link to gwnum.a when compiling through the makefile system. Can somebody point me in the right direction, please. Usually I compile with

//gcc -o lucasPRP lucasPRP.c gwnum/gwnum.a gwnum/gwnum.ld -lm -lpthread -lstdc++

[WraithX]

Originally Posted by paulunderwood

I tried unsuccessfully to get a return value from a system call to pfgw.

Now i have written gwnum code, but have no idea where to add a link to gwnum.a when compiling through the makefile system. Can somebody point me in the right direction, please. Usually I compile with

//gcc -o lucasPRP lucasPRP.c gwnum/gwnum.a gwnum/gwnum.ld -lm -lpthread -lstdc++

Put the file gwnum.a in the same folder that libgmp.a is in (not sure if gwnum.ld is needed, since I've never used it for anything).
I've renamed my gwnum.a file to libgwnum.a
Then, you can compile with:

//gcc -o lucasPRP lucasPRP.c -lgwnum -lm -lpthread -lstdc++

Renaming gwnum.a to libgwnum.a may not be needed as some compilers actually look for both when specifying -lgwnum in the compile command.