 Discrete logarithm

In mathematics, specifically in abstract algebra and its applications, discrete logarithms are grouptheoretic analogues of ordinary logarithms. In particular, an ordinary logarithm log_{a}(b) is a solution of the equation a^{x} = b over the real or complex numbers. Similarly, if g and h are elements of a finite cyclic group G then a solution x of the equation g^{x} = h is called a discrete logarithm to the base g of h in the group G.
Contents
Example
Discrete logarithms are perhaps simplest to understand in the group (Z_{p})^{×}. 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 (Z_{17})^{×}. To compute 3^{4} in this group, we first compute 3^{4} = 81, and then we divide 81 by 17, obtaining a remainder of 13. Thus 3^{4} = 13 in the group (Z_{17})^{×}.
Discrete logarithm is just the inverse operation. For example, take the equation 3^{k} ≡ 13 (mod 17) for k. As shown above k=4 is a solution, but it is not the only solution. Since 3^{16} ≡ 1 (mod 17) it also follows that if n is an integer then 3^{4+16 n} ≡ 13 × 1^{n} ≡ 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 3^{m} ≡ 1 (mod 17), i.e. 16 is the order of 3 in (Z_{17})^{×}, these are the only solutions. Equivalently, the solution can be expressed as k ≡ 4 (mod 16).
Definition
In general, 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 g of G can be written in the form g = b^{k} for some integer k. Furthermore, any two such integers k_{1} and k_{2} representing g will be congruent modulo n. We can thus define a function
(where Z_{n} denotes the ring of integers modulo n) by assigning to each g 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
Algorithms
See also: discrete logarithm recordsUnsolved problems in computer science Can the discrete logarithm be computed in polynomial time on a classical computer? No efficient classical algorithm for computing general discrete logarithms log_{b} g is known. The naive algorithm is to raise b to higher and higher powers k until the desired g is found; this is sometimes called trial multiplication. This algorithm requires running time linear in the size of the group G and thus exponential in the number of digits in the size of the group. There exists an efficient quantum algorithm due to Peter Shor.^{[1]}
More sophisticated algorithms exist, usually inspired by similar algorithms for integer factorization. These algorithms run faster than the naive algorithm, but none of them runs in polynomial time (in the number of digits in the size of the group).
 Babystep giantstep
 Pollard's rho algorithm for logarithms
 Pollard's kangaroo algorithm (aka Pollard's lambda algorithm)
 Pohlig–Hellman algorithm
 Index calculus algorithm
 Number field sieve
 Function field sieve
Comparison with integer factorization
While the problem of computing discrete logarithms and the problem of integer factorization are distinct problems they share some properties:
 both problems are difficult (no efficient algorithms are known for nonquantum computers),
 for both problems efficient algorithms on quantum computers are known,
 algorithms from one problem are often adapted to the other, and
 the difficulty of both problems has been utilized to construct various cryptographic systems.
Cryptography
There exist groups for which computing discrete logarithms is apparently difficult. In some cases (e.g. large prime order subgroups of groups (Z_{p})^{×}) there is not only no efficient algorithm known for the worst case, but the averagecase complexity can be shown to be about as hard as the worst case using random selfreducibility.
At the same time, the inverse problem of discrete exponentiation is not difficult (it can be computed efficiently using exponentiation by squaring, for example). This asymmetry is analogous to the one between integer factorization and integer multiplication. Both asymmetries have been exploited in the construction of cryptographic systems.
Popular choices for the group G in discrete logarithm cryptography are the cyclic groups (Z_{p})^{×}; see ElGamal encryption, 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.
References
 ^ Shor, Peter (1997). "PolynomialTime Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer". SIAM Journal on Computing 26 (5): 1484–1509. arXiv:quantph/9508027.
 Richard Crandall; Carl Pomerance. Chapter 5, Prime Numbers: A computational perspective, 2nd ed., Springer.
 Stinson, Douglas Robert (2006), Cryptography: Theory and Practice (3rd ed.), London: CRC Press, ISBN 9781584885085
Primality tests AKS · APR · Baillie–PSW · ECPP · Elliptic curve · Pocklington · Fermat · Lucas · Lucas–Lehmer · Lucas–Lehmer–Riesel · Proth's theorem · Pépin's · Solovay–Strassen · Miller–Rabin · Trial divisionSieving algorithms Integer factorization algorithms CFRAC · Dixon's · ECM · Euler's · Pollard's rho · p − 1 · p + 1 · QS · GNFS · SNFS · rational sieve · Fermat's · Shanks' square forms · Trial division · Shor'sMultiplication algorithms Ancient Egyptian multiplication · Karatsuba algorithm · Toom–Cook multiplication · Schönhage–Strassen algorithm · Fürer's algorithmDiscrete logarithm algorithms Babystep giantstep · Pollard rho · Pollard kangaroo · Pohlig–Hellman · Index calculus · Function field sieveGCD algorithms Modular square root algorithms Cipolla · Pocklington's · Tonelli–ShanksOther algorithms Italics indicate that algorithm is for numbers of special forms; bold indicates deterministic algorithm for primality tests (current article is always in bold).Categories: Modular arithmetic
 Group theory
 Cryptography
 Logarithms
 Finite fields
 Binary operations
 Computational hardness assumptions
 Unsolved problems in computer science
Wikimedia Foundation. 2010.
Look at other dictionaries:
Discrete logarithm records — are the best results achieved to date in solving the discrete logarithm problem, which is the problem of finding solutions x to the equation gx = h given elements g and h of a finite cyclic group G. The difficulty of this problem… … Wikipedia
Logarithm — The graph of the logarithm to base 2 crosses the x axis (horizontal axis) at 1 and passes through the points with coordinates (2, 1), (4, 2), and (8, 3) … Wikipedia
Complex logarithm — A single branch of the complex logarithm. The hue of the color is used to show the arg (polar coordinate angle) of the complex logarithm. The saturation (intensity) of the color is used to show the modulus of the complex logarithm. The page with… … Wikipedia
List of logarithm topics — This is a list of logarithm topics, by Wikipedia page. See also the list of exponential topics.*Acoustic power *antilogarithm *Apparent magnitude *Bel *Benford s law *Binary logarithm *Bode plot *Henry Briggs *Cologarithm *Common logarithm… … Wikipedia
Integral logarithm — The term integral logarithm may stand for: * Discrete logarithm in algebra, * Logarithmic integral function in calculus … Wikipedia
Elliptic curve cryptography — (ECC) is an approach to public key cryptography based on the algebraic structure of elliptic curves over finite fields. The use of elliptic curves in cryptography was suggested independently by Neal Koblitz[1] and Victor S. Miller[2] in 1985.… … Wikipedia
IEEE P1363 — is an Institute of Electrical and Electronics Engineers (IEEE) standardization project for public key cryptography. It includes specifications for: Traditional public key cryptography (IEEE Std 1363 2000 and 1363a 2004) Lattice based public key… … Wikipedia
Index calculus algorithm — In group theory, the index calculus algorithm is an algorithm for computing discrete logarithms. This is the best known algorithm for certain groups, such as mathbb{Z} m^* (the multiplicative group modulo m ).Dubiousdate=April 2008 Description… … Wikipedia
Pollard's lambda algorithm — In mathematics, specifically computational number theory and computational algebra, Pollard s lambda algorithm (aka Pollard s kangaroo algorithm, see Naming below) is an algorithm for solving the discrete logarithm. The algorithm was introduced… … Wikipedia
Proof of knowledge — In cryptography, a proof of knowledge is an interactive proof in which the prover succeeds convincing a verifier that it knows something. What it means for a machine to know something is defined in terms of computation. A machine knows something … Wikipedia