Quick question about PP and PP_INVERTED defines

[Brett Kuntz]

Hello, for a quick background on my question: I have been working on large (100k++) prime numbers recently and discovered that the primality testing algorithms could use some improvements, both to reduce cpu operations and also to reduce insane page faults (50k faults per second in some cases). I have been analyzing mpz_probab_prime_p, mpz_millerrabin, millerrabin, and mpz_stronglucas. I noticed that millerrabin's internal mpz_powm(y, x, q, n) is quite slow and the commenting is "Improve handling of buffers. It is pretty ugly now.". Since the first miller test is to base 2 and that the mod will always be an odd number I think I can make a custom function specifically for the miller base 2 test... 

Anyways, on to my quick question: 



gmp-impl.h

#if GMP_NUMB_BITS == 64 
#define PP CNST_LIMB(0xE221F97C30E94E1D) /* 3 x 5 x 7 x 11 x ... x 53 */ 
#define PP_INVERTED CNST_LIMB(0x21CFE6CFC938B36B) 
#define PP_FIRST_OMITTED 59 
#endif 



pprime_p.c

#if defined (PP_INVERTED) 
r = MPN_MOD_OR_PREINV_MOD_1(PTR(n), (mp_size_t)SIZ(n), (mp_limb_t)PP, (mp_limb_t)PP_INVERTED); 
#else 
r = mpn_mod_1(PTR(n), (mp_size_t)SIZ(n), (mp_limb_t)PP); 
#endif 



I read this Wikipedia article: https://en.wikipedia.org/wiki/Primality_test

I get what PP is, and I get why it's needed. But I do not understand what the PP_INVERTED define is, how it's calculated, or why? 

So my understanding is instead of doing many repeated divisibility tests on a large number we can simplify and just multiply a bunch of primes together, mod the tested number once, and then perform the same divisibility tests on the remainder (which will be much faster). I get that. But what is the inversion? What is MPN_MOD_OR_PREINV_MOD_1 doing? Why is there a PP_INVERTED for 32/64 bits but not the others?

I am trying to over-haul the primality testing specifically for 64-bit limbs and VERY large numbers, so any help would be greatly appreciated.

-Brett Kuntz