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

[paulunderwood]

Originally Posted by Luminescence

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.

I have just put out (post 148) code that does autoincrement of FFT size on excessive round-off error. Attached is the concept test program.

[frmky]

*** Maximum error of 0.500000 excessive at iteration 108154. Increasing FFT size.
prp

real    0m41.429s

Being a bit more conservative with a limit of 0.35 gives

*** Maximum error of 0.375000 excessive at iteration 108660. Increasing FFT size.
prp

real    0m41.536s

which switches a bit more than 500 iterations earlier.

[paulunderwood]

Attached is a version that uses a quick gwswap() rather than a slow gwcopy(). I have added the corresponding Ver_5 code to post 148.

[paulunderwood]

The ultimate Ver_6 has been uploaded to post 148. It uses functions and a neat piece of code to calculate odd d for n-1=d*2^r thanks to frmky. It might be a little bit quicker. As I state there, comment out the printf(); function messaging about FFT increases if you find them annoying at runtime.

frmky is working on 3-SPRP GMP code to be used above a certain threshold based this UTM page. This is useful for ARM based computers.

[frmky]

Originally Posted by paulunderwood

frmky is working on 3-SPRP GMP code to be used above a certain threshold based this UTM page. This is useful for ARM based computers.

Below is the code I settled on. I thank Paul for his suggestions and comments! I have tested it on many known primes and base-3 strong pseudoprimes.

This code is slower than Paul's version using gwnum but is faster than mpz_probab_prime_p(). It's useful where gwnum is not available.

int cm_nt_is_prime (mpz_t n)

{
   unsigned long j, r;
   int prime = 0;
   mpz_t d, a, x, n_sub_1;

   if (mpz_sizeinbase(n, 2) < 4096) return (mpz_probab_prime_p(n, 0) > 0);
   if (mpz_even_p(n)) return 0;

   mpz_inits(d, a, x, n_sub_1, NULL);

   mpz_sub_ui(n_sub_1, n, 1);
   r = mpz_scan1(n_sub_1, 0);
   mpz_fdiv_q_2exp(d, n_sub_1, r);

   mpz_set_ui(a, 3);
   mpz_powm(x, a, d, n);

   if ((mpz_cmp_ui(x, 1) == 0) || (mpz_cmp(x, n_sub_1) == 0)) prime = 1;
   else {
      for (j = 1; j < r; j++) {
         mpz_powm_ui(x, x, 2, n);
         if (mpz_cmp(x, n_sub_1) == 0) {
            prime = 1;
            break;
         }
      }
   }
    
   mpz_clears(d, a, x, n_sub_1, NULL);
   return prime;
}

[bur]

edit: running sudo ldconfig solved the issue...

I compiled ecpp and when running ecpp I get:

ecpp: error while loading shared libraries: libcm.so.0: cannot open shared object file: No such file or directory

libcm.so.0 exists:

$ ls /usr/local/lib/libcm* -l
-rw-r--r-- 1 root root 892160 Jun 30 07:56 /usr/local/lib/libcm.a
-rwxr-xr-x 1 root root    967 Jun 30 07:56 /usr/local/lib/libcm.la
-rw-r--r-- 1 root root 980172 Jun 30 07:56 /usr/local/lib/libcm_mpi.a
-rwxr-xr-x 1 root root   1041 Jun 30 07:56 /usr/local/lib/libcm_mpi.la
lrwxrwxrwx 1 root root     18 Jun 30 07:56 /usr/local/lib/libcm_mpi.so -> libcm_mpi.so.0.0.0
lrwxrwxrwx 1 root root     18 Jun 30 07:56 /usr/local/lib/libcm_mpi.so.0 -> libcm_mpi.so.0.0.0
-rwxr-xr-x 1 root root 553384 Jun 30 07:56 /usr/local/lib/libcm_mpi.so.0.0.0
lrwxrwxrwx 1 root root     14 Jun 30 07:56 /usr/local/lib/libcm.so -> libcm.so.0.0.0
lrwxrwxrwx 1 root root     14 Jun 30 07:56 /usr/local/lib/libcm.so.0 -> libcm.so.0.0.0
-rwxr-xr-x 1 root root 502448 Jun 30 07:56 /usr/local/lib/libcm.so.0.0.0

The only problem I ran into during compiling/installing was that make install complained about a permission error, so I ran sudo make install which went fine. Is that the issue? Same thing happened when installing mpfrx, permissions error and I did sudo make install.

[xilman]

Originally Posted by bur

I compiled ecpp and when running ecpp I get:

ecpp: error while loading shared libraries: libcm.so.0: cannot open shared object file: No such file or directory

libcm.so.0 exists:

$ ls /usr/local/lib/libcm* -l
-rw-r--r-- 1 root root 892160 Jun 30 07:56 /usr/local/lib/libcm.a
-rwxr-xr-x 1 root root    967 Jun 30 07:56 /usr/local/lib/libcm.la
-rw-r--r-- 1 root root 980172 Jun 30 07:56 /usr/local/lib/libcm_mpi.a
-rwxr-xr-x 1 root root   1041 Jun 30 07:56 /usr/local/lib/libcm_mpi.la
lrwxrwxrwx 1 root root     18 Jun 30 07:56 /usr/local/lib/libcm_mpi.so -> libcm_mpi.so.0.0.0
lrwxrwxrwx 1 root root     18 Jun 30 07:56 /usr/local/lib/libcm_mpi.so.0 -> libcm_mpi.so.0.0.0
-rwxr-xr-x 1 root root 553384 Jun 30 07:56 /usr/local/lib/libcm_mpi.so.0.0.0
lrwxrwxrwx 1 root root     14 Jun 30 07:56 /usr/local/lib/libcm.so -> libcm.so.0.0.0
lrwxrwxrwx 1 root root     14 Jun 30 07:56 /usr/local/lib/libcm.so.0 -> libcm.so.0.0.0
-rwxr-xr-x 1 root root 502448 Jun 30 07:56 /usr/local/lib/libcm.so.0.0.0

The only problem I ran into during compiling/installing was that make install complained about a permission error, so I ran sudo make install which went fine. Is that the issue? Same thing happened when installing mpfrx, permissions error and I did sudo make install.

Do you have /usr/local/lib in your ${LD_LIBRARY_PATH}? I ran into the exact same problem, which was fixed by putting the line

export LD_LIBRARY_PATH=/usr/local/lib:$LD_LIBRARY_PATH

into my .bashrc

[bur]

Thanks, I did ldconfig which fixed it.

[bur]

A question regarding the progress with the -v switch, I noticed values like qroot, Cornacchia and trial div increase over time, are those the values to look out for? If so, up to which value will they increase?

[paulunderwood]

Originally Posted by bur

A question regarding the progress with the -v switch, I noticed values like qroot, Cornacchia and trial div increase over time, are those the values to look out for? If so, up to which value will they increase?

Those are accumulative times. Each step is quicker than the last. It runs at O(log(n)^4) meaning a number twice in length takes 16 times as long to compute. So as each of the two stages finish it will look like it is speeding up.

I suggest that you start with some small test cases like (10^1031-1)/9.

[sweety439]

Originally Posted by paulunderwood

Those are accumulative times. Each step is quicker than the last. It runs at O(log(n)^4) meaning a number twice in length takes 16 times as long to compute. So as each of the two stages finish it will look like it is speeding up.

I suggest that you start with some small test cases like (10^1031-1)/9.

For (10^1031-1)/9, N-1 can be easily >= 1/3 factored, and N-1 primality proving can be used, I think 10^1000+453 (which is the next prime after 10^1000) may be better.