Editing Exponentiation by squaring (section)

==Further applications==
The approach also works with [[semigroup]]s that are not of [[characteristic zero]], for example allowing fast computation of large [[Modular exponentiation|exponents modulo]] a number. Especially in [[cryptography]], it is useful to compute powers in a [[Ring (mathematics)|ring]] of [[modular arithmetic|integers modulo {{mvar|q}}]]. For example, the evaluation of
:{{math|13789<sup>722341</sup> (mod 2345) {{=}} 2029}}
would take a very long time and much storage space if the naïve method of computing {{math|13789<sup>722341</sup>}} and then taking the [[remainder]] when divided by 2345 were used. Even using a more effective method will take a long time: square 13789, take the remainder when divided by 2345, multiply the [[result]] by 13789, and so on.

Applying above ''exp-by-squaring'' algorithm, with "*" interpreted as {{math|1=''x'' * ''y'' = ''xy'' mod 2345}} (that is, a multiplication followed by a division with remainder) leads to only 27 multiplications and divisions of integers, which may all be stored in a single machine word. Generally, any of these approaches will take fewer than {{math|2log{{sub|2}}(722340) &leq; 40}} modular multiplications.

The approach can also be used to compute integer powers in a [[group (mathematics)|group]], using either of the rules
:{{math|Power(''x'', −''n'') {{=}} Power(''x''<sup>−1</sup>, ''n'')}},
:{{math|Power(''x'', −''n'') {{=}} (Power(''x'', ''n''))<sup>−1</sup>}}.

The approach also works in [[non-commutative]] semigroups and is often used to compute powers of [[matrix (mathematics)|matrices]].

More generally, the approach works with positive integer exponents in every [[magma (algebra)|magma]] for which the binary operation is [[power associative]].