Modular exponentiation: Difference between revisions

Revision as of 18:21, 20 October 2021

Revision as of 18:39, 20 October 2021

Line 3:

'''Modular exponentiation''' is [[exponentiation]] performed over a [[modular arithmetic|modulus]]. It is useful in [[computer science]], especially in the field of [[public-key cryptography]].

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

For example, given {{math|1=''b'' = 5}}, {{math|1=''e'' = 3}} and {{math|1=''m'' = 13}}, the solution {{math|1=''c'' = 8}} is the remainder of dividing {{math|5³ {{=}} 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 similar to the one described above is considered easyefficient to compute, even whenfor thevery large integers involved are enormous. On the other hand, computing the modular [[discrete logarithm]] – that is, the task of 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.

== Direct method ==