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

[paulunderwood]

Originally Posted by paulunderwood

I'd say 4-5 months on 1024 cores with my above hack.

I should revise this figure down a lot. On 64 cores, it took 20 months for Primo to certify R49081. Call it 600 days. It would take Primo (86453/49081)^4 times as long i.e. 5776 days. Now FastECPP is twice as fast and my GWNUM hack will be 4 times as fast still at that bit level. So 722 days. On 16 times as many cores (i.e 1024 cores) that would only be ~45 days to certify R86453.

If no one is going to pick up R86453, I'd like to reserve it for myself for certification

[rudy235]

Originally Posted by paulunderwood

I should revise this figure down a lot. On 64 cores, it took 20 months for Primo to certify R49081. Call it 600 days. It would take Primo (86453/49081)^4 times as long i.e. 5776 days. Now FastECPP is twice as fast and my GWNUM hack will be 4 times as fast still at that bit level. So 722 days. On 16 times as many cores (i.e 1024 cores) that would only be ~45 days to certify R86453.

If no one is going to pick up R86453, I'd like to reserve it for myself for certification

Go for it Paul!


...and tell me is a 100,000 digit PRP EVEN theoretically possible with the present software/hardware.

[paulunderwood]

Originally Posted by rudy235

Go for it Paul!


...and tell me is a 100,000 digit PRP EVEN theoretically possible with the present software/hardware.

I guess so -- something like a top500 computer would eat it for breakfast.

[ryanp]

Originally Posted by paulunderwood

The attached code can be compiled with GWNUM (after that has compiled from P95 source) in the P95 directory

Then make the change to lib/nt.c of CM (FastECCP code):

int cm_nt_is_prime (mpz_t a) {
   char str[60000];
   if ( mpz_sizeinbase (a, 2) < 26000 ) { // is 26000 optimal?
      return (mpz_probab_prime_p(a, 0)>0);
   }
   strcpy (str, "/home/paul/Downloads/p95/gw_prp "); // note the space
   strcat (str, mpz_get_str(NULL, 10, a));
   return (system(str));
}

This is quite useful. Thank you!

Could your call to mpz_probab_prime_p() in the if block be replaced by mpz_millerrabin as R. Gerbicz suggested?

Originally Posted by paulunderwood

I am pretty sure it would be way better if the code was internal to CM instead of making use of system().

Perhaps this could be supported by some sort of --with-gwnum option to configure, as GMP-ECM allows.

[paulunderwood]

Originally Posted by ryanp

This is quite useful. Thank you!

Could your call to mpz_probab_prime_p() in the if block be replaced by mpz_millerrabin as R. Gerbicz suggested?

Perhaps this could be supported by some sort of --with-gwnum option to configure, as GMP-ECM allows.

You're welcome!

I don't know the probabilities of M-R compared to BPSW -- but Robert's point about superfluous trial division is valid.

I leave the configure option for Andreas to implement.

I tried compiling the code for gw_num.c inside lib/nt.c but got errors about things like SQLite and fPIC and other things -- it is beyond my skills.

[paulunderwood]

Which CM/FastECPP are you all using? We had a long time on Step [1] with a 13k digit PRP with 0.4.1dev and reverted the install back to 0.4.0. Were we impatient?

[Batalov]

0.4.1dev works well. (Specifically cm-0.4.1dev-41c4bce )

Latest news, UTM was updated with the new proof root code change called "E*"; and CM was changed to a 'program'.

[frmky]

Originally Posted by Batalov

0.4.1dev works well. (Specifically cm-0.4.1dev-41c4bce )

I still haven't been able to get through the step I got stuck on with that version. I've set it aside for now.

[Batalov]

I recently built a rather involved package for R (it is called leafcutter, if anyone is interested); so for it, I'd built ...well - everything. Because many of its prereqs (if I count them now, it's dozens, which in turn built hundreds; but half a dozen failed) were development tools (if they weren't you can use R's own internal tools, like for python one uses pip), so I needed aclocal, autoconf, latest pkg-config, too... but also many things that I'd had but were not good enough for all those tools. (some tools built graphs of intermediate results, and they were using whatever they preferred, - for example libjpeg, which I think the last time I built maybe in 2006). Some tools needed CXX14, some were dated 1999; some said "you have libblah, but you have to rebuild it with -fPIC"...

Of these, building aclocal, autoconf, libtool were the easiest - from source, and then you own them. For building CM, only 4 packages were needed; once you have ac* tools, they all are a breeze to build.

I ended up having several pythons (for various packages; what is good for a Russian is death for a German, some say -- same for tools), several R's (some packages in BioConductor are abandoneware, so R 3.8 doesn't build them; so you need 3.6, 3.3, 3.0), several perl's even, several gcc's. Madness! Once you do those, building anything is peanuts.

[frmky]

1987

But compiling CM isn't an issue. A run just gets stuck on a step for which it can't find a suitable discriminant. I'll look at it again later this week or next week when I have more time.

[paulunderwood]

Originally Posted by frmky

1987

But compiling CM isn't an issue. A run just gets stuck on a step for which it can't find a suitable discriminant. I'll look at it again later this week or next week when I have more time.

We had a problematic number on an Intel cluster. The number works fine on an AMD box. It is shot in the dark, but could it be this difference that is the cause of the problem?

The number is numbpart(140593907). On the Intel cluster it takes an inordinate amount of time with 0.4.1dev-3865637+GWNUM to do Step [1].

On the Intel cluster:

Size [0]: 43850 bits
   Time for discriminant -48625528: 271949.5 (15256.3)
   largest prime of d: 868313
   largest prime of h: 31
       discriminants: 23.3 (23.3)
    36813 qroot:      251653.6 (12125.1)
  3319702 Cornacchia: 12635.2 (667.7)
    12238 trial div:  7632.3 (380.7)
    11623 is_prime:   5.1 (2059.5)
--
Size [1]: 43818 bits
^C  
real    847m52.780s
user    11357m49.201s
sys    542m47.063s

On the AMD box:

-- Size [1]: 43808 bits
   Time for discriminant -52151523: 5649.9 (138.0)
   largest prime of d: 283
   largest prime of h: 2
       discriminants: 4.3 (4.3)
      189 qroot:      2546.1 (54.8)
   420610 Cornacchia: 5361.0 (86.8)
     5166 trial div:  5862.6 (97.3)
     1134 is_prime:   0.4 (105.3)