Discrete logarithm
In abstract algebra and its applications, the discrete logarithms are defined in group theory in analogy to ordinary logarithms. Let G be a finite cyclic group with n elements. We assume that the group is written multiplicatively. Let b be a generator of G; then every element x of G can be written in the form x = bk for some integer k. Furthermore, any two such integers representing x will be congruent modulo n. We can thus define a function
(where Zn denotes the ring of integers modulo n) by assigning to x the congruence class of k modulo n. This function is a group isomorphism, called the discrete logarithm to base b. The familiar base change formula for ordinary logarithms remains valid: if c is another generator of G, then we have -
Practical uses
For some groups, computing discrete logarithms is believed to be difficult, while the inverse problem of discrete exponentiation is not; this asymmetry is exploited in some applications in cryptography.
Popular choices for G in cryptography are the cyclic groups (Zp)× (consisting of the numbers {1, …, p − 1} under multiplication modulo the prime p); see ElGamal discrete log cryptosystem, Diffie-Hellman key exchange and the Digital Signature Algorithm.
Newer cryptography applications use discrete logarithms in cyclic subgroups of elliptic curves over finite fields. See elliptic curve cryptography.
Algorithms for finding discrete logarithms
Many of these algorithms are analogous to integer factorization algorithms. Integer factorization is another mathematically hard problem that finds applications in cryptography. Trial multiplication Baby-step giant-step Pollard's rho algorithm for logarithms Pohlig-Hellman algorithm Index calculus algorithm
|
|
