Modular exponentiation: Difference between revisions

Revision as of 15:12, 8 November 2021

Latest revision as of 22:32, 21 August 2025

(18 intermediate revisions by 14 users not shown)

Line 1:

{{Short description|OperationExponentation in modular arithmetic}}

{{refimprovemore citations needed|date=February 2018}}

'''Modular exponentiation''' is [[exponentiation]] performed over a [[modular arithmetic|modulus]]. It is useful in [[computer science]], especially in the field of [[public-key cryptography]], where it is used in both [[Diffie-HellmanDiffie–Hellman Keykey Exchangeexchange]] and [[RSA_RSA (cryptosystem)|RSA public/private keys]].

Modular exponentiation is the remainder when an integer {{math|''b''}} (the base) is raised to the power {{math|''e''}} (the exponent), and divided by a [[positive integer]] {{math|''m''}} (the modulus); that is, {{math|''c'' {{=}} ''b''^''e'' [[Modulo operation|mod]] ''m''}}. From the definition of division, it follows that {{math|0 ≤ ''c'' < ''m''}}.

Line 7:

For example, given {{math|1=''b'' = 5}}, {{math|1=''e'' = 3}} and {{math|1=''m'' = 13}}, dividing {{math|5³ {{=}} 125}} by {{math|13}} leaves a remainder of {{math|1=''c'' = 8}}.

ModularWhen exponentiation{{math|''b''}} can be performed with aand {{math|''negativem''}} are [[Coprime integers|relatively prime]], one can also allow the exponent {{math|''e''}} to be negative by finding the [[modularModular multiplicative inverse|multiplicative inverse]] {{math|''d''}} of {{math|''b''}} modulo {{math|''m''}} using(for theinstance by using [[extended Euclidean algorithm]]). ThatMore isprecisely:

:{{math|''c'' {{=}} ''b''{{sup|''e''}} mod ''m'' {{=}} ''d''{{sup|−''e''}} mod ''m''}}, where {{math|''e'' < 0}} and {{math|''b'' ⋅ ''d'' ≡ 1 (mod ''m'')}}.

Line 18:

One could use a calculator to compute 4¹³; this comes out to 67,108,864. Taking this value modulo 497, the answer {{math|''c''}} is determined to be 445.

Note that {{math|''b''}} is only one digit in length and that {{math|''e''}} is only two digits in length, but the value {{math|''b''^''e''}} is 8eight digits in length.

In strong cryptography, {{math|''b''}} is often at least 1024 [[bit]]s.<ref>{{Cite web|url=https://weakdh.org/|title=Weak Diffie-HellmanDiffie–Hellman and the Logjam Attack|website=weakdh.org|access-date=2019-05-03}}</ref> Consider {{math|''b'' {{=}} 5 × 10⁷⁶}} and {{math|''e'' {{=}} 17}}, both of which are perfectly reasonable values. In this example, {{math|''b''}} is 77 digits in length and {{math|''e''}} is 2two digits in length, but the value {{math|''b''^''e''}} is 1,304 decimal digits in length. Such calculations are possible on modern computers, but the sheer magnitude of such numbers causes the speed of calculations to slowdrop considerably. As {{math|''b''}} and {{math|''e''}} increase even further to provide better security, the value {{math|''b''^''e''}} becomes unwieldy.

The time required to perform the exponentiation depends on the operating environment and the processor. The method described above requires {{math|[[Big O notation|OΘ]](''e'')}} multiplications to complete.

== Memory-efficient method ==

Line 31:

The modified algorithm is:

:'''Inputs''' ''An integer {{mvar|b}} (base), integer {{mvar|e}} (exponent), and a positive integer {{mvar|m}} (modulus)''

# Set {{math|''c'' {{=}} 1}}, {{math|''e′'' {{=}} 0}}.

:'''Outputs''' ''The modular exponent {{mvar|c}} where'' {{math|''c'' {{=}} ''b''^''e'' ''mod m''}}

# Increase {{mvar|e′}} by 1.

:# SetInitialise {{math|''c'' {{=}} (b1}} ⋅and c)loop modvariable {{math|''me′'' {{=}} 0}}.

:# IfWhile {{math|''e′'' &lt; ''e''}}, go to step 2. Else, {{math|''c''}} contains the correct solution to {{math|''c'' ≡ ''b''{{sup|e}} (mod ''m'')}}.do

:## IncreaseIncrement {{mvar|e′}} by 1.

:## SetCalculate {{math|''c'' {{=}} 1}},(''b'' ⋅ {{math|''e′c'') {{=}}mod 0''m''}}.

:# Output {{mvar|c}}

Note that inat the end of every passiteration through stepthe 3loop, the equation {{math|''c'' ≡ ''b''{{sup|''e′''}} (mod ''m'')}} holds true. WhenThe stepalgorithm 3ends when the loop has been executed {{mvar|e}} times,. then,At that point {{mvar|c}} contains the answerresult that was sought. In summary, this algorithm basically counts upof {{mvar|e′}} by ones until {{mvar|e′}} reaches {{mvarmath|''b''^''e}},'' doingmod a multiply by {{mvar|b''m''}} and a modulo operation each time it adds one (to ensure the results stay small).

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 passes through step 3 thirteen times:

* {{math|''e′'' {{=}} 1. ''c'' {{=}} (1 ⋅ 4) mod 497 {{=}} 4 mod 497 {{=}} '''4'''.}}

* {{math|''e′'' {{=}} 2. ''c'' {{=}} (4 ⋅ 4) mod 497 {{=}} 16 mod 497 {{=}} '''16'''.}}

* {{math|''e′'' {{=}} 3. ''c'' {{=}} (16 ⋅ 4) mod 497 {{=}} 64 mod 497 {{=}} '''64'''.}}

* {{math|''e′'' {{=}} 4. ''c'' {{=}} (64 ⋅ 4) mod 497 {{=}} 256 mod 497 {{=}} '''256'''.}}

* {{math|''e′'' {{=}} 5. ''c'' {{=}} (256 ⋅ 4) mod 497 {{=}} 1024 mod 497 {{=}} '''30'''.}}

* {{math|''e′'' {{=}} 6. ''c'' {{=}} (30 ⋅ 4) mod 497 {{=}} 120 mod 497 {{=}} '''120'''.}}

* {{math|''e′'' {{=}} 7. ''c'' {{=}} (120 ⋅ 4) mod 497 {{=}} 480 mod 497 {{=}} '''480'''.}}

* {{math|''e′'' {{=}} 8. ''c'' {{=}} (480 ⋅ 4) mod 497 {{=}} 1920 mod 497 {{=}} '''429'''.}}

* {{math|''e′'' {{=}} 9. ''c'' {{=}} (429 ⋅ 4) mod 497 {{=}} 1716 mod 497 {{=}} '''225'''.}}

* {{math|''e′'' {{=}} 10. ''c'' {{=}} (225 ⋅ 4) mod 497 {{=}} 900 mod 497 {{=}} '''403'''.}}

* {{math|''e′'' {{=}} 11. ''c'' {{=}} (403 ⋅ 4) mod 497 {{=}} 1612 mod 497 {{=}} '''121'''.}}

* {{math|''e′'' {{=}} 12. ''c'' {{=}} (121 ⋅ 4) mod 497 {{=}} 484 mod 497 {{=}} '''484'''.}}

* {{math|''e′'' {{=}} 13. ''c'' {{=}} (484 ⋅ 4) mod 497 {{=}} 1936 mod 497 {{=}} '''445'''.}}

The example {{math|''b'' {{=}} 4}}, {{math|''e'' {{=}} 13}}, and {{math|''m'' {{=}} 497}} is presented again. The algorithm passesperforms throughthe step 3iteration thirteen times:

The final answer for {{mvar|c}} is therefore 445, as in the first method.

*: {{math|''(e′'' {{=}} 11.{{spaces|en}}1) {{spaces|em}} ''c'' {{=}} (4034 ⋅ 41) mod 497 {{=}} 16124 mod 497 {{=}} '''1214'''.}}

*: {{math|''(e′'' {{=}} 10.{{spaces|en}}2) {{spaces|em}} ''c '' {{=}} (2254 ⋅ 4) mod 497 {{=}} 90016 mod 497 {{=}} '''40316'''.}}

*: {{math|''(e′'' {{=}} 12.{{spaces|en}}3) {{spaces|em}} ''c'' {{=}} (1214 ⋅ 416) mod 497 {{=}} 48464 mod 497 {{=}} '''48464'''.}}

*: {{math|''(e′'' {{=}} 13.{{spaces|en}}4) {{spaces|em}} ''c'' {{=}} (4844 ⋅ 464) mod 497 {{=}} 1936256 mod 497 {{=}} '''445256'''.}}

*: {{math|''(e′'' {{=}} {{spaces|en}}5.) {{spaces|em}} ''c'' {{=}} (2564 ⋅ 4256) mod 497 {{=}} 1024 mod 497 {{=}} '''30'''.}}

*: {{math|''(e′'' {{=}} {{spaces|en}}6.) {{spaces|em}} ''c'' {{=}} (304 ⋅ 430) mod 497 {{=}} 120 mod 497 {{=}} '''120'''.}}

*: {{math|''(e′'' {{=}} {{spaces|en}}7.) {{spaces|em}} ''c'' {{=}} (1204 ⋅ 4120) mod 497 {{=}} 480 mod 497 {{=}} '''480'''.}}

*: {{math|''(e′'' {{=}} {{spaces|en}}8.) {{spaces|em}} ''c'' {{=}} (4804 ⋅ 4480) mod 497 {{=}} 1920 mod 497 {{=}} '''429'''.}}

*: {{math|''(e′'' {{=}} {{spaces|en}}9.) {{spaces|em}} ''c'' {{=}} (4294 ⋅ 4429) mod 497 {{=}} 1716 mod 497 {{=}} '''225'''.}}

*: {{math|''(e′'' {{=}} 1.10) {{spaces|em}} ''c'' {{=}} (14 ⋅ 4225) mod 497 {{=}} 4900 mod 497 {{=}} '''4403'''.}}

*: {{math|''(e′'' {{=}} 3.11) {{spaces|em}} ''c'' {{=}} (164 ⋅ 4403) mod 497 {{=}} 641612 mod 497 {{=}} '''64121'''.}}

*: {{math|''(e′'' {{=}} 2.12) {{spaces|em}} ''c'' {{=}} (4 ⋅ 4121) mod 497 {{=}} 16484 mod 497 {{=}} '''16484'''.}}

*: {{math|''(e′'' {{=}} 4.13) {{spaces|em}} ''c'' {{=}} (644 ⋅ 4484) mod 497 {{=}} 2561936 mod 497 {{=}} '''256445'''.}}

The final answer for {{mvar|c}} is therefore 445, as in the first[[#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.

Line 67 ⟶ 72:

== Right-to-left binary method ==

A third method drastically reduces the number of operations to perform modular exponentiation, while keeping the same [[memory footprint]] as in the previous method. It is a combination of the previous method and a more general principle called [[exponentiation by squaring]] (also known as ''binary exponentiation'').

First, it is required that the exponent {{math|''e''}} be [[Binary numeral system#Decimal|converted to binary notation]]. That is, {{math|''e''}} can be written as:

Line 82 ⟶ 87:

=== Pseudocode ===

The following is an example in pseudocode based on ''Applied Cryptography'' by [[Bruce Schneier]].<ref name="schneier96p244">[[#Schneier96|Schneier 1996]], p. 244.</ref> The inputs <var>base</var>, <var>exponent</var>, and <var>modulus</var> correspond to {{mvar|b}}, {{mvar|e}}, and {{mvar|m}} in the equations given above.

'''function''' modular_pow(base, exponent, modulus) '''is'''

Line 99 ⟶ 104:

Note that upon entering the loop for the first time, the code variable <var>base</var> is equivalent to {{mvar|b}}. However, the repeated squaring in the third line of code ensures that at the completion of every loop, the variable <var>base</var> is equivalent to {{math|''b''{{sup|2{{sup|''i''}}}} mod ''m''}}, where {{mvar|i}} is the number of times the loop has been iterated. (This makes {{mvar|i}} the next working bit of the binary exponent <var>exponent</var>, where the least-significant bit is <var>exponent₀</var>).

The first line of code simply carries out the multiplication in <math>\prod_{i=0}^{n-1} b^{a_i 2^i}\pmod m</math>. If {{mvar|a}} is zero, no code executes since this effectively multiplies the running total by one. If {{mvar|a}} instead is one, the variable <var>base</var> (containing the value {{math|''b''{{sup|2{{sup|''i''}}}} mod ''m''}} of the original base) is simply multiplied in.

In this example, the base {{mvar|b}} is raised to the exponent {{math|1=''e'' = 13}}.

Line 137 ⟶ 142:

'''if''' m == 1 '''then'''

'''return''' 0

'''elseend'''

'''local''' r = 1

b = b % m

'''while''' e > 0 '''do'''

'''if''' e % 2 == 1 '''then'''

r = (r*b) % m

'''end'''

b = (b*b) % m

e = e >> 1 --use 'e = math.floor(e / 2)' on Lua 5.2 or older

'''end'''

'''return'''b r= (b*b) % m

e = e >> 1 --use 'e = math.floor(e / 2)' on Lua 5.2 or older

'''end'''

'''endreturn''' r

'''end'''

== Left-to-right binary method ==

We can also use the bits of the exponent in left to right order. In practice, we would usually want the result modulo some modulus {{math|''m''}}. In that case, we would reduce each multiplication result {{math|(mod ''m'')}} before proceeding. For simplicity, the modulus calculation is omitted here. This example shows how to compute <math>b^{13}</math> using left to right binary exponentiation. The exponent is 1101 in binary; there are 4four bits, so there are 4four iterations.

Initialize the result to 1: <math>r \leftarrow 1 \, ( = b^0)</math>.

Line 182 ⟶ 186:

=== Reversible and quantum modular exponentiation ===

In [[quantum computing]], modular exponentiation appears as the bottleneck of [[Shor's algorithm]], where it must be computed by a circuit consisting of [[reversible computing|reversible gates]], which can be further broken down into [[quantum gate]]s appropriate for a specific physical device. Furthermore, in Shor's algorithm it is possible to know the base and the modulus of exponentiation at every call, which enables various circuit optimizations.<ref>{{cite journal|author=I. L. Markov, M. Saeedi |title=Constant-Optimized Quantum Circuits for Modular Multiplication and Exponentiation |journal=Quantum Information and Computation |volume=12 |issue=5–6 |pages=0361–0394 |year=2012 |doi=10.26421/QIC12.5-6-1 |arxiv=1202.6614 |bibcode=2012arXiv1202.6614M |s2cid=16595181 }}</ref>

== Software implementations ==

{{Wikibooks|Algorithm Implementation|Mathematics/Modular Exponentiation|Modular Exponentiation}}

Because modular exponentiation is an important operation in computer science, and there are efficient algorithms (see above) that are much faster than simply exponentiating and then taking the remainder, many programming languages and arbitrary-precision integer libraries have a dedicated function to perform modular exponentiation:

* [[Python (programming language)|Python]]'s built-in <code>pow()</code> (exponentiation) function [https://docs.python.org/library/functions.html#pow] takes an optional third argument, the modulus

Line 198 ⟶ 201:

* The [[GNU Multiple Precision Arithmetic Library]] (GMP) library contains a <code>mpz_powm()</code> function [http://gmplib.org/manual/Integer-Exponentiation.html] to perform modular exponentiation

* Custom Function <code>[http://www.briandunning.com/cf/1482 @PowerMod()]</code> for [[FileMaker]] Pro (with 1024-bit [[RSA (algorithm)|RSA]] encryption example)

* [[Ruby (programming language)|Ruby]]'s <code>openssl</code> package has the <code>OpenSSL::BN#mod_exp</code> method [httphttps://docs.ruby-doclang.org/stdlib-trunk/libdoc/opensslen/rdocmaster/OpenSSL/BN.html#method-i-mod_exp] to perform modular exponentiation.

* The [[HP Prime]] Calculator has the CAS.powmod() function [http://h20628.www2.hp.com/km-ext/kmcsdirect/emr_na-c04120022-1.pdf] to perform modular exponentiation. For a^b mod c, a can be no larger than 1 EE 12. This is the maximum precision of most HP calculators including the Prime.

== See also ==

Line 210 ⟶ 212:

== External links ==

{{Wikibooks|Algorithm Implementation|Mathematics/Modular Exponentiation|Modular Exponentiation}}

*{{cite book|title=Applied Cryptography: Protocols, Algorithms, and Source Code in C, Second Edition|url=https://archive.org/details/Applied_Cryptography_2nd_ed._B._Schneier|last=Schneier|first=Bruce|authorlink=Bruce Schneier|year=1996|publisher=Wiley|edition=2nd|isbn=978-0-471-11709-4|ref=Schneier96}}