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

[Prime95]

Originally Posted by andreas

as far as I can tell, gwnum is non-free software and as such incompatible with CM under GPL. So I do not intend to support it and would appreciate if this direction were not pursued.

IANAL. Yes, GPL and gwnum licencses are incompatible.

That said, I believe there is no issue with publishing source code that allows a user to create an executable linked with gwnum for their own personal use. GMP-ECM has done this for years.

Furthermore, if an executable linked with gwnum does leak into the wild no one on this end will care (it would violate the GPL license, not the gwnum license).

[R. Gerbicz]

Originally Posted by ATH

What would happen in the extremely unlikely case of a composite prp was considered to be prime? Would the certificate fail later on?

You could not make a certificate, that would violate the ecpp method's proof.
To hack the initial prp test is not that hard: use my super prp prime, see https://www.mersenneforum.org/showpo...postcount=1546
Running on the original non modifed code, but on gmp-6.1.2.

gerbicz@gerbicz-MS-7972:~/cmexp000/cm/cm-0.4.1dev/src$ mpirun ecpp-mpi -v -g -n '1396981702787004809899378463251' -c -f cert-0k
MPI with 3 workers initialised, of which 3 are local.
CM: include 0.4.1dev, lib 0.4.1dev
GMP: include 6.1.2, lib 6.1.2
MPFR: include 4.1.0, lib 4.1.0
MPC: include 1.2.1, lib 1.2.1
MPFRCX: include 0.6.3, lib 0.6.3
PARI: include 2.11.1, lib 2.11.1
--- Time for primality test:       0.0 (0.0)
Could not open file 'cert-0k.cert1' for reading.
Writing to 'cert-0k.cert1'.
-- Time for class numbers up to Dmax=2548: 0.0 (0.0)
-- Time for primorial of B=108: 0.0 (0.0)
-- hmaxprime: 29
-- Size [0]:  101 bits
   Time for discriminant       -3:   6.9 (  7.1)
   largest prime of d: 3
   largest prime of h: 1
       discriminants: 6.9 (6.9)
        6 qroot:      0.0 (0.0)
       20 Cornacchia: 0.0 (0.0)
       10 trial div:  0.0 (0.0)
        9 is_prime:   0.0 (0.1)
-- Size [1]:   95 bits
   Time for discriminant      -39:   0.0 (  0.2)
   largest prime of d: 13
   largest prime of h: 2
       discriminants: 6.9 (6.9)
       15 qroot:      0.0 (0.1)
       51 Cornacchia: 0.0 (0.1)
       42 trial div:  0.0 (0.0)
       18 is_prime:   0.0 (0.1)
-- Size [2]:   84 bits
   Time for discriminant       -7:   0.0 (  0.2)
   largest prime of d: 7
   largest prime of h: 1
       discriminants: 6.9 (6.9)
       30 qroot:      0.0 (0.2)
       83 Cornacchia: 0.0 (0.1)
       56 trial div:  0.1 (0.1)
       24 is_prime:   0.0 (0.2)
-- Size [3]:   76 bits
   Time for discriminant      -39:   0.0 (  0.2)
   largest prime of d: 13
   largest prime of h: 2
       discriminants: 6.9 (6.9)
       36 qroot:      0.0 (0.3)
      109 Cornacchia: 0.0 (0.1)
      108 trial div:  0.1 (0.1)
       30 is_prime:   0.0 (0.2)
--- Time for first ECPP step, depth 4:  7.0 (7.7)
Could not open file 'cert-0k.cert2' for reading.
Writing to 'cert-0k.cert2'.
-- Time for   95 bits (discriminant -39, invariant s, parameters 4_1_8): 6.7
-- Timings after job   1: CM   6.7, roots   0.0, point   0.0
-- Time for   76 bits (discriminant -39, invariant s, parameters 4_1_8): 0.0
-- Timings after job   3: CM   6.7, roots   0.0, point   0.0

*** No suitable curve found!
--------------------------------------------------------------------------
Primary job  terminated normally, but 1 process returned
a non-zero exit code. Per user-direction, the job has been aborted.
--------------------------------------------------------------------------
-- Time for   84 bits (discriminant -7, invariant w, parameters 7_1_24): 6.8
-- Timings after job   2: CM  13.5, roots   0.0, point   0.0
--------------------------------------------------------------------------
mpirun detected that one or more processes exited with non-zero status, thus causing
the job to be terminated. The first process to do so was:

  Process name: [[30251,1],3]
  Exit code:    1
--------------------------------------------------------------------------
gerbicz@gerbicz-MS-7972:~/cmexp000/cm/cm-0.4.1dev/src$

What is so interesting that it is caught only in the 2nd phase.
I could catch most of these on the Tonelli-Shanks part of the algorithm, using a single mulmod (per core), what is ultra cheap.

[paulunderwood]

There were some serious errors in Version 6 of my GWNUM addition. I was using "use the next fft" on generic mod.

There are now two versions: One uses a bigger FFT size (Ver-2b) and the other uses safe mult only (Ver-3). See: post 148

[kruoli]

Do you think this might have caused such a high amount of runs stalling?

[paulunderwood]

Originally Posted by kruoli

Do you think this might have caused such a high amount of runs stalling?

Yes

[frmky]

Version 2b still fails on http://factordb.com/index.php?id=1100000003606729924. Version 3 works. It's about 2.5x slower on that number, but still almost 6x faster than GMP at that size.

[paulunderwood]

Originally Posted by frmky

Version 2b still fails on http://factordb.com/index.php?id=1100000003606729924. Version 3 works. It's about 2.5x slower on that number, but still almost 6x faster than GMP at that size.

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include "gwnum/giants.h"
#include "gwnum/gwnum.h"
#include "gwnum/gwcommon.h"
#include <gmp.h>

int main(int argc, char *argv[]){

   char string[100000];
   int i, j, k, LEN, r;
   unsigned init_b[1] = {3};
   giant  n, gb;
   gwnum wb;
   gwhandle *gwdata;
   mpz_t a, gmp_var;

   mpz_init_set_str ( a, argv[1], 10 );

        mpz_get_str( string, 10, a );
        LEN = strlen ( string ); LEN = ( LEN >> 2 ) + 8;
        n  = newgiant ( LEN );
        gb = newgiant ( LEN );

        gwdata = (gwhandle*) malloc (sizeof ( gwhandle ) );
        gwinit ( gwdata );

        ctog ( string, n );

        gwsetup_general_mod_giant( gwdata, n );
        wb = gwalloc ( gwdata );

        // Base 3 strong Fermat PRP test
        mpz_init ( gmp_var );
        mpz_sub_ui ( gmp_var, a, 1 );
        r = 0;
        do {
                if ( r == 50 ) break;
                r++;
                mpz_tdiv_q_2exp ( gmp_var, gmp_var, 1 );
        } while mpz_even_p ( gmp_var );
        mpz_clear ( gmp_var );

        binarytogw ( gwdata, init_b, 1, wb );
        j = mpz_sizeinbase ( a, 2 ) - 2;
        k = j - 50;
        for ( i =  j; i > k; i-- ) {
                gwsquare2_carefully ( gwdata, wb, wb );
                if ( mpz_tstbit ( a, i ) ) gwsmallmul( gwdata, 3.0, wb );
        }
        for ( i = k; i > 50; i-- ) {
                gwstartnextfft ( gwdata, 1 );
                if ( mpz_tstbit ( a, i ) ) gwsquare2 ( gwdata, wb, wb, 0x0200 );
                else gwsquare2 ( gwdata, wb, wb, 0 );
                gwstartnextfft ( gwdata, 0 );
        }
        for ( i = 50; i >= r; i-- ) {
                gwsquare2_carefully ( gwdata, wb, wb );
                if ( mpz_tstbit ( a, i ) ) gwsmallmul( gwdata, 3.0, wb );
        }
        gwtogiant ( gwdata, wb, gb );
        modg ( n, gb );
        if ( ( isone ( gb ) ) ) { gwdone ( gwdata ); printf("prp\n"); return ( 1 ); }
        for ( i = r; i > 0; i-- ) {
                gwtogiant ( gwdata, wb, gb );
                iaddg ( 1, gb );
                modg ( n, gb );
                if ( isZero ( gb ) ) { gwdone ( gwdata ); printf("prp\n"); return ( 1 ); }
                if ( i == 1 ) break;
                gwsquare2_carefully ( gwdata, wb, wb );
        }
        gwdone ( gwdata ); printf("composite\n"); return ( 0 );

}

The above code gives "prp" on my Celeron, but gives "composite" on the my Threadripper and frmky's Xeon,

Is this a bug in GWNUM, George?

(Calls to gwstartnextfft can be commented out -- they are in the wrong place anyway, beside not working for generic mod.)

[Luminescence]

Originally Posted by paulunderwood

[CODE]
The above code gives "prp" on my Celeron, but gives "composite" on the my Threadripper and frmky's Xeon,

Is this a bug in GWNUM, George?

(Calls to gwstartnextfft can be commented out -- they are in the wrong place anyway, beside not working for generic mod.)

Odd... gives PRP on a Celeron, but doesn't like Threadripper and Xeons.
It also does not work on my Xeon Platinums. I checked with gwnum V30.7 and V30.8b15

[paulunderwood]

Originally Posted by Luminescence

Odd... gives PRP on a Celeron, but doesn't like Threadripper and Xeons.
It also does not work on my Xeon Platinums. I checked with gwnum V30.7 and V30.8b15

I had the fft length increase in the wrong place in the code for "Ver-2b". Please try out now. I have overkilled with 2 notches of increase.

[frmky]

No increase.

fft size: 10240
avx: 3
round off 3: 0.000000
round off 2: 0.000000
round off 1: 0.000000
composite

real	0m25.121s

One notch increase

fft size: 15360
avx: 3
round off 3: 0.000000
round off 2: 0.000000
prp

real	0m40.148s

Two notches increase

fft size: 16384
avx: 3
round off 3: 0.000000
round off 2: 0.000000
prp

real	0m39.606s

Thanks!

[Luminescence]

Originally Posted by paulunderwood

I had the fft length increase in the wrong place in the code for "Ver-2b". Please try out now. I have overkilled with 2 notches of increase.

fft size: 16384
avx: 8
round off 3: 0.000000
round off 2: 0.000000
prp

real	0m9,978s

Nice.

So in short: the latest code works, but the FFT size needs to be increased.