Editing Modular exponentiation (section)

== Generalizations ==
=== Matrices ===
The {{mvar|m}}-th term of any [[constant-recursive sequence]] (such as [[Fibonacci numbers]] or [[Perrin numbers]]) where each term is a linear function of {{mvar|k}} previous terms can be computed efficiently modulo {{mvar|n}} by computing {{math|''A<sup>m</sup>'' mod ''n''}}, where {{mvar|A}} is the corresponding {{math|''k''×''k''}} [[Companion matrix#Linear recursive sequences|companion matrix]]. The above methods adapt easily to this application. This can be used for [[Fibonacci number#Primality testing|primality testing]] of large numbers {{mvar|n}}, for example.

; Pseudocode
A recursive algorithm for <code>ModExp(A, b, c)</code> = {{math|''A<sup>b</sup>'' mod ''c''}}, where {{mvar|A}} is a square matrix.
 '''function''' Matrix_ModExp(Matrix A, int b, int c) '''is'''
     '''if''' b == 0 '''then'''
         '''return''' I  // The identity matrix
     '''if''' (b '''mod''' 2 == 1) '''then'''
         '''return''' (A * Matrix_ModExp(A, b - 1, c)) '''mod''' c
     Matrix D := Matrix_ModExp(A, b / 2, c)
     '''return''' (D * D) '''mod''' c

=== Finite cyclic groups ===
[[Diffie–Hellman key exchange]] uses exponentiation in finite cyclic groups. The above methods for modular matrix exponentiation clearly extend to this context. The modular matrix multiplication {{math|''C'' ≡ ''AB'' (mod ''n'')}} is simply replaced everywhere by the group multiplication {{math|1=''c'' = ''ab''}}.

=== 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>