Question about the performance of the GMP on a specific integer division case

[Torbjörn Granlund]

Jeronimo Pellegrini <j_p at aleph0.info> writes:

  Looking at the y and Y cases it seems that it may be several times
  faster to check if abs(A) < abs(B) and not do the full computation; and
  the x and X cases seem to indicate that it may be just slightly slower
  to do the verification if compiler optimization is on a reasonable level
  (-O2).

  So I was wondering why this case is not optimized. Are the mpz division
  functions used in the implementation of mpz_powm_sec, or something like
  that? Or is it because the small overhead of the verification is
  considered already too much, and hence the user would have the
  responsibility to do the check, if it's the case?

I think it is safe to assume that computing A / B for A < B is not a common
use of GMP.

In general, we tend to avoid checking for particular operand values, and
instead have general code which handles the majority of cases effficiently.
There are exceptions to that rule, but optimising for anomaly cases is not
something we do.

Please check the sources of mpz_powm_sec to find the answer to your
question about how it computes its mod reductions.

-- 
Torbjörn
Please encrypt, key id 0xC8601622