Why different runtimes for constant exponent and (huge) modulus for mpz_powm()?

hermann at stamm-wilbrandt.de hermann at stamm-wilbrandt.de
Fri Jul 21 13:35:43 CEST 2023


Last night I posted on 75 days sequential computation I started:
https://gmplib.org/list-archives/gmp-devel/2023-July/006190.html

After first 18.2h 112 rounds of 11121 rounds in total are completed.
The C++ code makes sure that the job output files Birth date is set 
before a loop computation, and that Modified date gets set after 
computation:

https://github.com/Hermann-SW/9383761-digit-prime/blob/main/job.cc#L69-L74
     for (; j < loops; ++j) {
         create_birth(f, j+1);
         mpz_powm(a.get_mpz_t(), b.get_mpz_t(), c.get_mpz_t(), 
p.get_mpz_t());
         write_close(f, a);
         b = a;
     }


For this computation p is 9,383,761-digit-prime, and exponent c is 
constant value 2^2803 (to the power of).

I would have awaited different runtimes for dferent exponents, but 
obviously different values of b do the 2803 squarings (mod p) in 
different runtimes [s]:
min/avg/max = 573.6/584.6/590.6

It is not only the difference in runtimes, but also the distribution 
over time (up/down/up/down):
https://stamm-wilbrandt.de/en/forum/first_112_rounds.png

Since the amount of "small" numbers mod p is small, what can be the 
reason for these (not that big, -1.9%/+1.0% from average) runtimes of 
mpz_powm()?
Memory allocation?


Regards,

Hermann.


More information about the gmp-devel mailing list