In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. The problem of computing discrete logarithms is a sort of sibling to the problem of integer factorization, in that both problems are difficult (no efficient algorithms are known), algorithms from one problem are often adapted to the other, and the difficulty of both problems has been exploited to construct various cryptographic (code) systems. Euclid, a famous Greek mathematician known as the father of geometry, is shown here in detail from The School of Athens by Raphael. ... Abstract algebra is the field of mathematics concerned with the study of algebraic structures such as groups, rings and fields. ... In mathematics, a group is a set, together with a binary operation, such as multiplication or addition, satisfying certain axioms, detailed below. ... Logarithms to various bases: is to base e, is to base 10, and is to base 1. ... In number theory, the integer factorization problem is the problem of finding a non-trivial divisor of a composite number; for example, given a number like 91, the challenge is to find a number such as 7 which divides it. ... Flowcharts are often used to represent algorithms. ... The German Lorenz cipher machine Cryptography or cryptology is a field of mathematics and computer science concerned with information security and related issues, particularly encryption and authentication. ...

Example

Discrete logarithms are perhaps simplest to understand in the group (Z_p)^×. This is the set of integers {1, …, p − 1} under multiplication modulo the prime p. In mathematics, the multiplicative group of integers modulo n is the group defined by multiplication of the units (that is, the numbers relatively prime to ) in the ring for a given integer . ... The integers consist of the positive natural numbers (1, 2, 3, …), their negatives (−1, −2, −3, ...) and the number zero. ... Modular arithmetic (sometimes called modulo arithmetic) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ... In mathematics, a prime number (or a prime) is a natural number that has exactly two (distinct) natural number divisors, which are 1 and the prime number itself. ...

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₁₇)^×. To compute 3⁴ in this group, we first compute 3⁴ = 81, and then we divide 81 by 17, obtaining a remainder of 13. Thus 3⁴ = 13 in the group (Z₁₇)^×. In mathematics, exponentiation (frequently known colloquially as raising a number to a power) is a process generalized from repeated (or iterated) multiplication, in much the same way that multiplication is a process generalized from repeated addition. ...

Discrete logarithm is just the inverse operation: Given that 3^k ≡ 13 (mod 17), what is the k that makes this true? Actually, there are infinitely many answers, due to the modular nature of the problem; we typically seek the least nonnegative answer, which is k = 4.

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 representing g will be congruent modulo n. We can thus define a function In group theory, a cyclic group is a group that can be generated by a single element, in the sense that the group has an element a (called a generator of the group) such that, when written multiplicatively, every element of the group is a power of a (or na... In abstract algebra, a generating set of a group is a subset S such that every element of G can be expressed as the product of finitely many elements of S and their inverses. ... Modular arithmetic (sometimes called modulo arithmetic) is a system of arithmetic for integers, where numbers wrap around after they reach a certain value — the modulus. ...

(where Z_n denotes the ring of integers modulo n) by assigning to g the congruence class of k modulo n. This function is a group isomorphism, called the discrete logarithm to base b. In ring theory, a branch of abstract algebra, a ring is an algebraic structure in which addition and multiplication are defined and have similar properties to those familiar from the integers. ... In abstract algebra, a group isomorphism is a function between two groups that sets up a one-to-one correspondence between the elements of the groups in a way that respects the given group operations. ...

The familiar base change formula for ordinary logarithms remains valid: If c is another generator of G, then we have

Algorithms

No efficient algorithm for computing general discrete logarithms 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. To analyze an algorithm is to determine the amount of resources (such as time and storage) necessary to execute it. ...

More sophisticated algorithms exist, usually inspired by similar algorithms for integer factorization. These algorithms run faster than the naive algorithm, but they are still slower than polynomial time.

• Baby-step giant-step
• Pollard's rho algorithm for logarithms
• Pohlig-Hellman algorithm
• Index calculus algorithm
• Number field sieve
• Function field sieve

In group theory, a branch of mathematics, the baby-step giant-step algorithm refers to a series of well defined steps to compute the discrete logarithm. ... Pollards rho algorithm for logarithms is an algorithm for solving the discrete logarithm problem analogous to Pollards rho algorithm for solving the Integer factorization problem. ... In mathematics, the Pohlig-Hellman algorithm is an algorithm for the computation of discrete logarithms in a multiplicative group whose order is a smooth integer. ... In group theory, the index calculus algorithm is an algorithm for computing discrete logarithms. ... In mathematics, the general number field sieve is the most efficient algorithm known for factoring integers. ...

Cryptography

Computing discrete logarithms is apparently difficult (no efficient algorithm is known), while the inverse problem of discrete exponentiation is not (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. Exponentiating by squaring is an algorithm used for the fast computation of large integer powers of a number. ... In mathematics, multiplication is an arithmetic operation which is the inverse of division, and in elementary arithmetic, can be interpreted as repeated addition. ...

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. The ElGamal algorithm is an asymmetric key encryption algorithm for public key cryptography which is based on Diffie-Hellman key agreement. ... Diffie-Hellman key exchange is a cryptographic protocol which allows two parties to agree on a secret key over an insecure communication channel. ... The Digital Signature Algorithm (DSA) is a United States Federal Government standard for digital signatures. ...

Newer cryptography applications use discrete logarithms in cyclic subgroups of elliptic curves over finite fields; see elliptic curve cryptography. In mathematics, an elliptic curve is a plane curve defined by an equation of the form y2 = x3 + a x + b, which is non-singular; that is, its graph has no cusps or self-intersections. ... In abstract algebra, a finite field or Galois field (so named in honor of Évariste Galois) is a field that contains only finitely many elements. ... Elliptic curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ...