Editing Modular exponentiation (section)

== Memory-efficient method ==
Keeping the numbers smaller requires additional modular reduction operations, but the reduced size makes each operation faster, saving time (as well as memory) overall.

This algorithm makes use of the identity
: {{math|(''a'' ⋅ ''b'') mod ''m'' {{=}} [(''a'' mod ''m'') ⋅ (''b'' mod ''m'')] mod ''m''}}

The modified algorithm is:
:'''Inputs''' ''An integer {{mvar|b}} (base), integer {{mvar|e}} (exponent), and a positive integer {{mvar|m}} (modulus)''
:'''Outputs''' ''The modular exponent {{mvar|c}} where'' {{math|''c'' {{=}} ''b''<sup>''e''</sup> ''mod m''}}
:# Initialise {{math|''c'' {{=}} 1}} and loop variable {{math|''e′'' {{=}} 0}}
:# While {{math|''e′'' &lt; ''e''}} do
:## Increment {{mvar|e′}} by 1
:## Calculate {{math|''c'' {{=}} (''b'' ⋅ ''c'') mod ''m''}}
:# Output {{mvar|c}}

Note that at the end of every iteration through the loop, the equation {{math|''c'' ≡ ''b''{{sup|''e′''}} (mod ''m'')}} holds true.  The algorithm ends when the loop has been executed {{mvar|e}} times. At that point {{mvar|c}} contains the result of {{math|''b''<sup>''e''</sup> mod ''m''}}.

In summary, this algorithm increases {{mvar|e′}} by one until it is equal to {{mvar|e}}. At every step multiplying the result from the previous iteration, {{mvar|c}}, by {{mvar|b}} and performing a modulo operation on the resulting product, thereby keeping the resulting {{mvar|c}} a small integer.

The example {{math|''b'' {{=}} 4}}, {{math|''e'' {{=}} 13}}, and {{math|''m'' {{=}} 497}} is presented again.  The algorithm performs the iteration thirteen times:
: {{math|''(e′'' {{=}} {{spaces|en}}1) {{spaces|em}} ''c'' {{=}} (4 ⋅ 1) mod 497 {{=}} 4 mod 497 {{=}} '''4'''}}
: {{math|''(e′'' {{=}} {{spaces|en}}2) {{spaces|em}} ''c '' {{=}} (4 ⋅ 4) mod 497 {{=}} 16 mod 497 {{=}} '''16'''}}
: {{math|''(e′'' {{=}} {{spaces|en}}3) {{spaces|em}} ''c'' {{=}} (4 ⋅ 16) mod 497 {{=}} 64 mod 497 {{=}} '''64'''}}
: {{math|''(e′'' {{=}} {{spaces|en}}4) {{spaces|em}} ''c'' {{=}} (4 ⋅ 64) mod 497 {{=}} 256 mod 497 {{=}} '''256'''}}
: {{math|''(e′'' {{=}} {{spaces|en}}5) {{spaces|em}} ''c'' {{=}} (4 ⋅ 256) mod 497 {{=}} 1024 mod 497 {{=}} '''30'''}}
: {{math|''(e′'' {{=}} {{spaces|en}}6) {{spaces|em}} ''c'' {{=}} (4 ⋅ 30) mod 497 {{=}} 120 mod 497 {{=}} '''120'''}}
: {{math|''(e′'' {{=}} {{spaces|en}}7) {{spaces|em}} ''c'' {{=}} (4 ⋅ 120) mod 497 {{=}} 480 mod 497 {{=}} '''480'''}}
: {{math|''(e′'' {{=}} {{spaces|en}}8) {{spaces|em}} ''c'' {{=}} (4 ⋅ 480) mod 497 {{=}} 1920 mod 497 {{=}} '''429'''}}
: {{math|''(e′'' {{=}} {{spaces|en}}9) {{spaces|em}} ''c'' {{=}} (4 ⋅ 429) mod 497 {{=}} 1716 mod 497 {{=}} '''225'''}}
: {{math|''(e′'' {{=}} 10) {{spaces|em}} ''c'' {{=}} (4 ⋅ 225) mod 497 {{=}} 900 mod 497 {{=}} '''403'''}}
: {{math|''(e′'' {{=}} 11) {{spaces|em}} ''c'' {{=}} (4 ⋅ 403) mod 497 {{=}} 1612 mod 497 {{=}} '''121'''}}
: {{math|''(e′'' {{=}} 12) {{spaces|em}} ''c'' {{=}} (4 ⋅ 121) mod 497 {{=}} 484 mod 497 {{=}} '''484'''}}
: {{math|''(e′'' {{=}} 13) {{spaces|em}} ''c'' {{=}} (4 ⋅ 484) mod 497 {{=}} 1936 mod 497 {{=}} '''445'''}}

The final answer for {{mvar|c}} is therefore 445, as in the [[#Direct method|direct method]].

Like the first method, this requires {{math|O(''e'')}} multiplications to complete.  However, since the numbers used in these calculations are much smaller than the numbers used in the first algorithm's calculations, the computation time decreases by a factor of at least {{math|O(''e'')}} in this method.

In pseudocode, this method can be performed the following way:
 '''function''' modular_pow(base, exponent, modulus) '''is'''
     '''if''' modulus = 1 '''then'''
         '''return''' 0
     c := 1
     '''for''' e_prime = 0 '''to''' exponent-1 '''do'''
         c := (c * base) '''mod''' modulus
     '''return''' c