Talk:Modular exponentiation

Left-to-Right algorithm work with a fractional modulus?[edit]

Plugging in 3, 10 and 7.1 for the variables base, exponent and modulous yield 1.74 instead of 6. — Preceding unsigned comment added by 223.206.114.1 (talk) 04:43, 13 August 2011 (UTC)[reply]

Anonymous suggestions[edit]

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). — Preceding unsigned comment added by 63.202.83.229 (talk • contribs) February 20, 2005

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.— Preceding unsigned comment added by 72.19.80.208 (talk • contribs) November 12, 2005

Binary modular algorithm and fractional modulus[edit]

A base of 10, a exponent of 3 and a modulus of 7.1 (1000 % 7.1) yields 1.74 instead of 6. — Preceding unsigned comment added by 223.206.114.1 (talk) 01:32, 13 August 2011 (UTC)[reply]

operator precedence in example implementations?[edit]

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)[reply]

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)[reply]

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

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)[reply]

I think using e%2 followed by decrementing e to reflect that e is odd, then dividing e by 2 instead of shifting it would be more readable to the average person than using (e&1 > 0) amd e>>=1 Something like

Bignum modpow(Bignum base, Bignum exponent, Bignum modulus) {

    Bignum result = 1;
 
    while (exponent > 0) {
        if ((exponent%2) == 1) {
            // exponent is odd, multiply base^(exponent-1) by the base to get base^exponent
            result = (result * base) % modulus;
            --exponent;
        }
        exponent /= 2;
        base = (base * base) % modulus;
    }
 
    return result;
}

Flying Bishop (talk) 18:16, 27 August 2008 (UTC)[reply]

(exponent&1) is a very efficient machine operation; on some processors, it would be a single TEST opcode, on others it would be a bitwise AND into a register where the result doesn't get used (just check the flags). An optimizing compiler will probably recognize that modulo a power of two can be implemented with a bitwise AND against the bitwise NOT of the modulus minus one, but it will still need the result to compare in the == part of the expression, i.e. extra work.

I see two possible problems with exponent /= 2. First is that if Bignum is signed, the compiler has no choice but to call the division operator. Sure, we know that Bignum will always hold a positive number in the particular applications where we will be doing modular exponentiation, but the compiler doesn't know that, and so it can't change the divide-by-a-power-of-2 into a much more efficient right shift. The second problem is that conceptually, a right shift of the bits is exactly what you want to do. Dividing by two accomplishes the right shift (on an unsigned number), but it's not as clear why you want to do that, as compared to shifting right to get the next bit.

Regardless of whether you use /=2 or >>=1, decrementing exponent is unnecessary. The low-order bit will fall off the end (into the carry flag, depending on the machine code), and so the decrement only adds extra code that a compiler may not be able to optimize away. Pfagerburg (talk) 00:14, 10 September 2008 (UTC)[reply]

I understand that they are more efficient: however, this should not be about providing an ideally efficient implementation. It should perform the algorithm in an easily understood manner. (Maybe the python should be replaced with a concise version that uses proper variable names and normal math operators.) The point is, knowledge of binary arithmetic should not be necessary to understand the basic implementation of the algorithm. Most beginners' courses don't even cover what they do. Maybe the ideal way would be to have a simple version, using meaningful variable names (this is documentation, not quick I-don't-feel-like-writing-the-word-exponent code) and no binary operators, then a section on optimization explaining why the literal translation of the mathematical algorithm can be further improved. Flying Bishop (talk • contribs) 16:10, 10 September 2008 (UTC)[reply]

The code is in a section titled "An Efficient Method", and it is preceded by an explanation of the binary arithmetic, including notes that the algorithm operates one bit at a time. So I feel that the bitwise operations are conceptually correct for this code. Pfagerburg (talk) 03:40, 11 September 2008 (UTC)[reply]

However, I do agree with you that the code should be re-written to have proper variable names, so that it's a little easier to follow. And the python code seems a bit messy and not very well explained. Pfagerburg (talk) 03:42, 11 September 2008 (UTC)[reply]

"unique solution"[edit]

The article currently states

c\equiv b^{e}{\pmod {m}}

...

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)[reply]

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 b^e-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)[reply]

avoiding ambiguity[edit]

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)[reply]

optimized example ??[edit]

please someone remove that section. the algorithm is just a re-written version of the C# code. contrary to the claim, it is inefficient and not suited for hardware implementation . it seems the only reason it is there is to please the python zealots. 213.80.27.34 (talk) 12:09, 28 November 2007 (UTC)[reply]

I removed the reference to cleverness; the author seems entirely too pleased with himself. This article is about modular exponentiation, there is no reason to consider regular exponentiation in the example code, and the original implementation also "cleverly" uses a single variable. I see no reason to include the python, even if it is cleaned up. The C++ could probably be made a little clearer with the use of actual variable names, and by using normal operators instead of bitwise ones. Flying Bishop (talk) 18:30, 27 August 2008 (UTC)[reply]

I'm going to remove the entire section. The IP that originally added it has been inactive for over a year and a half. The section has recently been tagged with a lot of OR and FACT tags, which really should have been there since the explanations were added (thanks, bishop!), and I doubt they will be answered. Also, as Flying Bishop noted, there is no need to consider general exponentiation (without a modulus) in this article. Pfagerburg (talk) 04:23, 11 September 2008 (UTC)[reply]

Fractional modulo[edit]

Fractional modulo used with binary algorithm yielding incorrect results? Given base = 10, exponent = 3 and modulus of 7.1 returns 1.74 instead of 6.

result = 1

Loop 1: result = (1 * 10) MOD 7.1 = 2.9 exp >> 1 = 1 base = (10 * 10) MOD 7.1 = .6

Loop 2: result = (2.9 * .6) MOD 7.1 = 1.74 exp>> = 0

result = 1.74 — Preceding unsigned comment added by 223.206.114.1 (talk) 15:02, 12 August 2011 (UTC)[reply]

True. Multiplication operation with a fractional modulus isn't associative, so this algorithm doesn't work with it. -- X7q (talk) 15:33, 12 August 2011 (UTC)[reply]

...This algorithm makes use of the fact that, given two integers a and b, the following two equations are equivalent...[edit]

c\equiv (a\cdot b){\pmod {m}}

c\equiv (a\cdot (b\ ({\mbox{mod}}\ m))){\pmod {m}}

This isn't completely obvious (to me!), is there a link to another wikipedia page that might show why this is always the case? I can see it is now I've tried it out on paper...Thanks for the great article by the way! Lionfish0 (talk) 17:12, 26 January 2012 (UTC)[reply]

This wasn't obvious for me either, although I have a master in physics. I could also reproduce it on paper, but it would be nice to reference an explanation. Ansiwen (talk) 16:23, 4 September 2018 (UTC)[reply]

Constant multiplication[edit]

Given that the article states that "even when the numbers involved are enormous", it should take into account that multiplication of large numbers may not be computable directly on the processor. Thus, the runtimes should be depending on the efficiency of the multiplication algorithm: as in http://en.wikipedia.org/wiki/Computational_complexity_of_mathematical_operations.

Per.Zut (talk) 10:14, 5 August 2013 (UTC)[reply]

Mention Euler's Theorem[edit]

In general, if one needs to calculate $b^{e}{\bmod {m}}$ for arbitrary given $b,e,m$ , then it makes sense first to reduce the exponent to $e{\bmod {\varphi (m)}}$ because of Euler's theorem. In many application, e.g. in cryptography, you will already have $e<\varphi (m)$ , and this reduction does not improve efficiency. — Preceding unsigned comment added by Wstomv (talk • contribs) 22:11, 21 January 2016 (UTC)[reply]

In order to compute

\varphi (m)

you need the factorization of m and, in general, this looks harder than calculating

b^{e}{\bmod {m}}

with the methods described in the page.78.15.205.250 (talk) 10:34, 8 April 2016 (UTC)[reply]

On the other hand there are cryptographic methods based on just that. It's baffling that the totient is not mentioned at all in this article. — jdorje (talk) 07:43, 13 May 2016 (UTC)[reply]

Right-to-left binary method[edit]

I rewrote the example of raising a number to the 13 th power.

First, percents didn't belong there because percent is a modulus operator in specific computer languages. Second, I found the example with the four bullet points very hard to follow.

So, I wrote the basic algorithm following the example of raising a number to the 13 th power. The original example kept squaring the original base b; I used the unnecessary variable x so the explanation could explain what power of b was being computed. I then followed the algorithmic description with a rewrite of the original example with numbers b = 4, e = 13, modulus m = 497. I don't feel this numeric example makes things clearer, but I'll let other people decide whether to delete it. MathPerson (talk) 15:07, 6 April 2017 (UTC)[reply]

What is up with this "Memory Efficient Method" featured prominently as the second section in the article?[edit]

This ultra naive algorithm is not a "method" and it has zero citations. I barely understand why it's worth mentioning, let alone dedicate multiple paragraphs and fully worked-out example with pseudocode to boot. The only purpose this can possibly serve is conceptual understanding, it is not used in the real world. Can it be condensed? Rubydesic (talk) 07:53, 10 February 2024 (UTC)[reply]

Like in the explanation in this post, it builds up to more efficient methods. The memory efficient one is the starting point. It explains how to use the product rule of modular arithmetic in the most simple case. 84.198.41.61 (talk) 12:17, 25 February 2024 (UTC)[reply]