Talk:Modular exponentiation

From Wikipedia, the free encyclopedia

Could discuss top down vs. bottom up exponentiation.

Could add optimizations (for "top down") that are faster but use more memory. Examples: bit windowing (or sliding windows).

modpow is not complete. for all x, (x^0 mod 1) is 0, not 1. because e is zero, the loop is ignored and a result of 1 is returned. one general fix for this is:

return result % m;

another would be a fairly thorough conditional statement.

Contents 1 operator precedence in example implementations? 2 Small improvement to modpow (Right to left algorithm) 3 "unique solution" 4 avoiding ambiguity

[edit] operator precedence in example implementations?

In the implementation of modexp_leftToRight, A = A * A % m; does not have any parens, but A = (A * g) % m; does. Operator precedence following C/C++ rules would interpret A * A % m as A * ( A % m ). Is that the correct order for this algorithm, or should it parenthesized as A = ( A * A ) % m;? --Pfagerburg 22:53, 20 March 2006 (UTC)

Either way, we should put in parenthesis to make the correct order obvious to our readers.

Fixed: the article now reads b = (b * b) % m;

--70.189.77.59 17:36, 16 October 2006 (UTC)

[edit] Small improvement to modpow (Right to left algorithm)

In the algorithm shown, during the last pass of the loop, the square b is calculated but never used.

A speed-up is to make it conditional based on the e value.

  while (e > 0) {
     if ((e & 1) > 0) result = (result * b) % m;
     e >>= 1;
     if (e > 0)
       b = (b * b) % m;
  }

Surely, calculating an if statement on each pass is costly, and a single branch misprediction would make this worse than just calculating the square an extra time, right? Any hyperpipelined processor will make this inefficient, and large exponents will probably do the same. Why not just put the last pass outside the loop? That's what I did when I 'reinvented' RTL modular exponentiation. CRGreathouse (talk • contribs) 05:21, 6 August 2006 (UTC)

[edit] "unique solution"

The article currently states

...

If b, e, and m are non-negative and b < m, then a unique solution c exists and has the property 0 ≤ c < m.

I don't understand the point of "b<m". Would it be OK to replace that sentence with

If b, e, and m are non-negative, then a unique solution c exists and has the property 0 ≤ c < m.

or is there something I'm missing? --70.189.77.59 17:36, 16 October 2006 (UTC)

I'm note sure about in that specific context, but the "memory-efficient" algorithm, at least (as given), won't work if b >= m, because, according to the thing about it, b^e (mod m) = (b^e-1*b) (mod m) = ((b^e-1 (mod m))*(b (mod m))) (mod m). The "c" variable contains the iterative value of be-1 (mod m), but the algorithm as shown doesn't do b (mod m), which isn't neccessary anyway if b is < m. B.Mearns^*, KSC 19:00, 1 March 2007 (UTC)

[edit] avoiding ambiguity

What restrictions do I need on b and e and m must be, in order to avoid an ambiguous system? (An ambiguous system allows 2 different b values produce onto the same c value, allows 2 different plaintexts to produce the same ciphertext -- Bob would be unable to figure out which plaintext message Alice intended to send). (Is there some other article that discusses ambiguity of modular exponentiation?)

To be unambigous, b must be 0 ≤ b < m because of the pigeonhole principle. But 0 ≤ b < m is not sufficient -- for example, both

1^2 mod 4 = 1

3^2 mod 4 = 1

. Is it enough to set e prime (RSA mentions that the prime 2^16 + 1 = "65537 is a commonly used value for e"), and make sure m is not a multiple of e? --70.189.77.59 17:36, 16 October 2006 (UTC)