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

[Niels Möller]

hermann at stamm-wilbrandt.de writes:

> 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

Curious. I would suspect some enviromental factors (e.g., high processor
temperature sometimes leading to some frquency throttling, or something
else on the machine periodically competing for cpu).
 
> 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()?

I don't think so, the intermediate values mod p should have a rather
random-looking distribution regardless of the initial value. And your
graph doesn't show a random noise process, but a process with
dependency: it's looks like it's jumping between a "fast" and a "slow"
state, with a dozen or so computations done in each state. I find it
difficult to explain that behavior with properties of the underlying
arithmetics.

> Memory allocation?

Memory allocation is *not* expected to take on the order of 1% of the
running time. But I guess it's possible you're hitting some anomaly,
e.g., sometimes getting good locality for working storage, sometimes
worse.

Maybe it would be helpful to monitor performance related measurements
such as cpu frequency (or cycle counter), temperature, and count of
cache misses as computation progresses?

Regards,
/Niels

-- 
Niels Möller. PGP key CB4962D070D77D7FCB8BA36271D8F1FF368C6677.
Internet email is subject to wholesale government surveillance.