Example
Discrete logarithms are perhaps simplest to understand in the group (Zp)×. This is the set {1, …, p − 1} of congruence classes under multiplication modulo the prime p.
If we want to find the kth power of one of the numbers in this group, we can do so by finding its kth power as an integer and then finding the remainder after division by p. This process is called discrete exponentiation. For example, consider (Z17)×. To compute 34 in this group, we first compute 34 = 81, and then we divide 81 by 17, obtaining a remainder of 13. Thus 34 = 13 in the group (Z17)×.
Discrete logarithm is just the inverse operation. For example, take the equation 3k ≡ 13 (mod 17) for k. As shown above k=4 is a solution, but it is not the only solution. Since 316 ≡ 1 (mod 17), it also follows that if n is an integer then 34+16 n ≡ 13 × 1n ≡ 13 (mod 17). Hence the equation has infinitely many solutions of the form 4 + 16n. Moreover, since 16 is the smallest positive integer m satisfying 3m ≡ 1 (mod 17), i.e. 16 is the order of 3 in (Z17)×, these are the only solutions. Equivalently, the solution can be expressed as k ≡ 4 (mod 16).
Read more about this topic: Discrete Logarithm
Famous quotes containing the word example:
“Our intellect is not the most subtle, the most powerful, the most appropriate, instrument for revealing the truth. It is life that, little by little, example by example, permits us to see that what is most important to our heart, or to our mind, is learned not by reasoning but through other agencies. Then it is that the intellect, observing their superiority, abdicates its control to them upon reasoned grounds and agrees to become their collaborator and lackey.”
—Marcel Proust (1871–1922)