hermann on Fri, 03 May 2024 14:52:34 +0200


[Date Prev] [Date Next] [Thread Prev] [Thread Next] [Date Index] [Thread Index]

Simpler PARI/GP code than this?


GIMPS mprime software creates ".proof" files for fast verification of a completed (long time) PRP proof/disproof.

I asked about software to verify such .proof, and @Prime95 provided main.c and roots.c.
The missing rootsdata.txt can be created with GP:

...
// This is a compacted table computed in pari-gp of z(p) = znorder(Mod(2,p)), associating for each "z" entry
// the set of primes "p" that have that z(p) value.
// The keys "z" are stored as negative values to distinguish them from the primes that follow each z.
int merged[] = {
#include "rootsdata.txt"
};
...

$ head rootsdata.txt && echo "..." && tail -3 rootsdata.txt
-2, 3,
-3, 7,
-4, 5,
-5, 31,
-7, 127,
-8, 17,
-9, 73,
-10, 11,
-11, 23, 89,
-12, 13,
...
-65322, 65323,
-65356, 65357,
-65370, 65371,
$


I came up with this GP script to create rootsdata.txt, verify_PRP could be compiled and used (generation of PRP proof for 9.4million decimal digit prime took 6:12h (with 16 threads), verification took only 5:17min):

https://www.mersenneforum.org/showthread.php?p=656165&postcount=7

z(p) = znorder(Mod(2,p));
o=[List()|i<-[1..2^16]];
forprime(p=3,2^16+1,listput(~o[z(p)],p));
{
  for(i=1,2^16,if(#o[i],
    print1("-", i,",");
    foreach(o[i],x,print1(" ",x,","));
    print();
  ));
}

I feel that rootsdata.txt can be created with a much smaller GP script, is that true?

Regards,

Hermann.