Editing Discrete logarithm (section)

==Examples==
=== Powers of 10 ===
The [[power of 10|powers of 10]] are
:<math>\ldots, 0.001, 0.01, 0.1, 1, 10, 100, 1000, \ldots.</math>
For any number <math>a</math> in this list, one can compute <math>\log_{10}a</math>. For example, <math>\log_{10}{10000}=4</math>, and <math>\log_{10}{0.001}=-3</math>. These are instances of the discrete logarithm problem.

Other base-10 logarithms in the real numbers are not instances of the discrete logarithm problem, because they involve non-integer exponents. For example, the equation <math>\log_{10}{53}=1.724276\ldots</math> means that <math>10^{1.724276\ldots}</math>. While integer exponents can be defined in any group using products and inverses, arbitrary real exponents, such as this 1.724276…, require other concepts such as the [[exponential function]].

In [[group-theoretic]] terms, the powers of 10 form a [[cyclic group]] <math>G</math> under multiplication, and 10 is a [[cyclic group|generator]] for this group. The discrete logarithm <math>\log_{10}a</math> is defined for any <math>a</math> in <math>G</math>.

=== Powers of a fixed real number ===
A similar example holds for any non-zero real number <math>b</math>. The powers form a multiplicative [[subgroup]] <math>G = \{\ldots , b^{-2}, b^{-1}, 1, b^{1}, b^{2}, \ldots \}</math> of the non-zero real numbers. For any element <math>a</math> of <math>G</math>, one can compute <math>\log_b a</math>.

=== Modular arithmetic ===
One of the simplest settings for discrete logarithms is the group [[multiplicative group of integers modulo n|'''Z'''<sub>''p''</sub><sup>×</sup>]]. This is the group of multiplication [[modular arithmetic|modulo]] the [[prime number|prime]] <math>p</math>. Its elements are non-zero [[Modular arithmetic#Congruence class|congruence classes]] modulo <math>p</math>, and the group product of two elements may be obtained by ordinary integer multiplication of the elements followed by reduction modulo&nbsp;<math>p</math>.

The <math>k</math><sup>th</sup> [[exponentiation|power]] of one of the numbers in this group may be computed by finding its '<math>k</math><sup>th</sup> power as an integer and then finding the remainder after division by <math>p</math>. When the numbers involved are large, it is more efficient to reduce modulo <math>p</math> multiple times during the computation. Regardless of the specific algorithm used, this operation is called [[modular exponentiation]]. For example, consider '''Z'''<sub>17</sub><sup>×</sup>. To compute <math>3^4</math> in this group, compute <math>3^4=81</math>, and then divide <math>81</math> by <math>17</math>, obtaining a remainder of <math>13</math>. Thus <math>3^4=13</math> in the group '''Z'''<sub>17</sub><sup>×</sup>.

The discrete logarithm is just the inverse operation. For example, consider the equation <math>3^k \equiv 13 \pmod{17}</math>. From the example above, one solution is <math>k=4</math>, but it is not the only solution. Since <math>3^{16}\equiv 1 \pmod{17}</math> —as follows from [[Fermat's little theorem]]— it also follows that if <math>n</math> is an integer then <math>3^{4+16n}\equiv 3^4\cdot (3^{16})^n \equiv 3^4 \cdot 1^n \equiv 3^4 \equiv 13 \pmod{17}</math>. Hence the equation has infinitely many solutions of the form <math>4+16n</math>. Moreover, because <math>16</math> is the smallest positive integer <math>m</math> satisfying <math>3^m\equiv 1 \pmod{17}</math>, these are the only solutions. Equivalently, the set of all possible solutions can be expressed by the constraint that <math>k\equiv 4 \pmod{16}</math>.

=== Powers of the identity ===
In the special case where <math>b</math> is the identity element <math>1</math> of the group <math>G</math>, the discrete logarithm <math>\log_ba</math> is undefined for <math>a</math> other than <math>1</math>, and every integer <math>k</math> is a discrete logarithm for <math>a=1</math>.