Editing Modular exponentiation (section)

{{Short description|Operation in modular arithmetic}}
{{more 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–Hellman key exchange]] and [[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''<sup>''e''</sup> [[Modulo operation|mod]] ''m''}}. From the definition of division, it follows that {{math|0 ≤ ''c'' &lt; ''m''}}.

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

Modular exponentiation can be performed with a ''negative'' exponent {{math|''e''}} by finding the [[modular multiplicative inverse]] {{math|''d''}} of {{math|''b''}} modulo {{math|''m''}} using the [[extended Euclidean algorithm]]. That is:
:{{math|''c'' {{=}} ''b''{{sup|''e''}} mod ''m'' {{=}} ''d''{{sup|−''e''}} mod ''m''}}, where {{math|''e'' < 0}} and {{math|''b'' ⋅ ''d'' ≡ 1 (mod ''m'')}}.

Modular exponentiation is efficient to compute, even for very large integers.  On the other hand, computing the modular [[discrete logarithm]] – that is, finding the exponent {{math|''e''}} when given {{math|''b''}}, {{math|''c''}}, and {{math|''m''}} – is believed to be difficult. This [[one-way function]] behavior makes modular exponentiation a candidate for use in cryptographic algorithms.