HOME

TheInfoList



OR:

In
mathematics Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...
, for given
real number In mathematics, a real number is a number that can be used to measure a ''continuous'' one-dimensional quantity such as a distance, duration or temperature. Here, ''continuous'' means that values can have arbitrarily small variations. Every ...
s ''a'' and ''b'', the
logarithm In mathematics, the logarithm is the inverse function to exponentiation. That means the logarithm of a number  to the base  is the exponent to which must be raised, to produce . For example, since , the ''logarithm base'' 10 ...
log''b'' ''a'' is a number ''x'' such that . Analogously, in any
group A group is a number of persons or things that are located, gathered, or classed together. Groups of people * Cultural group, a group whose members share the same cultural identity * Ethnic group, a group whose members share the same ethnic ide ...
''G'', powers ''b''''k'' can be defined for all
integer An integer is the number zero (), a positive natural number (, , , etc.) or a negative integer with a minus sign ( −1, −2, −3, etc.). The negative numbers are the additive inverses of the corresponding positive numbers. In the languag ...
s ''k'', and the discrete logarithm log''b'' ''a'' is an integer ''k'' such that . In
number theory Number theory (or arithmetic or higher arithmetic in older usage) is a branch of pure mathematics devoted primarily to the study of the integers and integer-valued functions. German mathematician Carl Friedrich Gauss (1777–1855) said, "Ma ...
, the more commonly used term is index: we can write ''x'' = ind''r'' ''a'' (mod ''m'') (read "the index of ''a'' to the base ''r'' modulo ''m''") for ''r''''x'' ≡ ''a'' (mod ''m'') if ''r'' is a primitive root of ''m'' and gcd(''a'',''m'') = 1. Discrete logarithms are quickly computable in a few special cases. However, no efficient method is known for computing them in general. Several important algorithms in
public-key cryptography Public-key cryptography, or asymmetric cryptography, is the field of cryptographic systems that use pairs of related keys. Each key pair consists of a public key and a corresponding private key. Key pairs are generated with cryptographic a ...
, such as ElGamal base their security on the assumption that the discrete logarithm problem over carefully chosen groups has no efficient solution.


Definition

Let ''G'' be any group. Denote its group operation by multiplication and its
identity element In mathematics, an identity element, or neutral element, of a binary operation operating on a set is an element of the set that leaves unchanged every element of the set when the operation is applied. This concept is used in algebraic structures su ...
by 1. Let ''b'' be any element of ''G''. For any positive integer ''k'', the expression ''b''''k'' denotes the product of ''b'' with itself ''k'' times: :b^k = \underbrace_. Similarly, let ''b''−''k'' denote the product of ''b''−1 with itself ''k'' times. For ''k'' = 0, the ''k''th power is the
identity Identity may refer to: * Identity document * Identity (philosophy) * Identity (social science) * Identity (mathematics) Arts and entertainment Film and television * ''Identity'' (1987 film), an Iranian film * ''Identity'' (2003 film), an ...
: . Let ''a'' also be an element of ''G''. An integer ''k'' that solves the equation is termed a discrete logarithm (or simply logarithm, in this context) of ''a'' to the base ''b''. One writes ''k'' = log''b'' ''a''.


Examples


Powers of 10

The powers of 10 are :\ldots, 0.001, 0.01, 0.1, 1, 10, 100, 1000, \ldots. For any number ''a'' in this list, one can compute log10 ''a''. For example, log10 10000 = 4, and log10 0.001 = −3. 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 log10 53 = 1.724276… means that 101.724276… = 53. 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 The exponential function is a mathematical function denoted by f(x)=\exp(x) or e^x (where the argument is written as an exponent). Unless otherwise specified, the term generally refers to the positive-valued function of a real variable, ...
. In group-theoretic terms, the powers of 10 form a
cyclic group In group theory, a branch of abstract algebra in pure mathematics, a cyclic group or monogenous group is a group, denoted C''n'', that is generated by a single element. That is, it is a set of invertible elements with a single associative bina ...
''G'' under multiplication, and 10 is a generator for this group. The discrete logarithm log10 ''a'' is defined for any ''a'' in ''G''.


Powers of a fixed real number

A similar example holds for any non-zero real number ''b''. The powers form a multiplicative subgroup ''G'' = of the non-zero real numbers. For any element ''a'' of ''G'', one can compute log''b'' ''a''.


Modular arithmetic

One of the simplest settings for discrete logarithms is the group (Z''p'')×. This is the group of multiplication
modulo In computing, the modulo operation returns the remainder or signed remainder of a division, after one number is divided by another (called the '' modulus'' of the operation). Given two positive numbers and , modulo (often abbreviated as ) is ...
the
prime A prime number (or a prime) is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways ...
''p''. Its elements are congruence classes modulo ''p'', and the group product of two elements may be obtained by ordinary integer multiplication of the elements followed by reduction modulo ''p''. The ''k''th
power Power most often refers to: * Power (physics), meaning "rate of doing work" ** Engine power, the power put out by an engine ** Electric power * Power (social and political), the ability to influence people or events ** Abusive power Power may a ...
of one of the numbers in this group may be computed by finding its ''k''th power as an integer and then finding the remainder after division by ''p''. When the numbers involved are large, it is more efficient to reduce modulo ''p'' multiple times during the computation. Regardless of the specific algorithm used, this operation is called
modular exponentiation Modular exponentiation is exponentiation performed over a modulus. It is useful in computer science, especially in the field of public-key cryptography, where it is used in both Diffie-Hellman Key Exchange and RSA public/private keys. Modul ...
. For example, consider (Z17)×. To compute 34 in this group, compute 34 = 81, and then divide 81 by 17, obtaining a remainder of 13. Thus 34 = 13 in the group (Z17)×. The discrete logarithm is just the inverse operation. For example, consider the equation 3''k'' ≡ 13 (mod 17) for ''k''. From the example above, one solution is ''k'' = 4, but it is not the only solution. Since 316 ≡ 1 (mod 17)—as follows from
Fermat's little theorem Fermat's little theorem states that if ''p'' is a prime number, then for any integer ''a'', the number a^p - a is an integer multiple of ''p''. In the notation of modular arithmetic, this is expressed as : a^p \equiv a \pmod p. For example, if = ...
—it also follows that if ''n'' is an integer then 34+16''n'' ≡ 34 × (316)''n'' ≡ 13 × 1''n'' ≡ 13 (mod 17). Hence the equation has infinitely many solutions of the form 4 + 16''n''. Moreover, because 16 is the smallest positive integer ''m'' satisfying 3''m'' ≡ 1 (mod 17), these are the only solutions. Equivalently, the set of all possible solutions can be expressed by the constraint that ''k'' ≡ 4 (mod 16).


Powers of the identity

In the special case where ''b'' is the identity element 1 of the group ''G'', the discrete logarithm log''b'' ''a'' is undefined for ''a'' other than 1, and every integer ''k'' is a discrete logarithm for ''a'' = 1.


Properties

Powers obey the usual algebraic identity ''b''''k'' + ''l'' = ''b''''k'' ''b''''l''. In other words, the function :f \colon \mathbf \to G defined by ''f''(''k'') = ''b''''k'' is a
group homomorphism In mathematics, given two groups, (''G'', ∗) and (''H'', ·), a group homomorphism from (''G'', ∗) to (''H'', ·) is a function ''h'' : ''G'' → ''H'' such that for all ''u'' and ''v'' in ''G'' it holds that : h(u*v) = h(u) \cdot h(v) w ...
from the integers Z under addition onto the
subgroup In group theory, a branch of mathematics, given a group ''G'' under a binary operation ∗, a subset ''H'' of ''G'' is called a subgroup of ''G'' if ''H'' also forms a group under the operation ∗. More precisely, ''H'' is a subgroup ...
''H'' of ''G'' generated by ''b''. For all ''a'' in ''H'', log''b'' ''a'' exists. Conversely, log''b'' ''a'' does not exist for ''a'' that are not in ''H''. If ''H'' is infinite, then log''b'' ''a'' is also unique, and the discrete logarithm amounts to a
group isomorphism 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. If there exists an isomorphism between two gr ...
:\log_b \colon H \to \mathbf. On the other hand, if ''H'' is finite of
order Order, ORDER or Orders may refer to: * Categorization, the process in which ideas and objects are recognized, differentiated, and understood * Heterarchy, a system of organization wherein the elements have the potential to be ranked a number of ...
''n'', then log''b'' ''a'' is unique only up to congruence modulo ''n'', and the discrete logarithm amounts to a group isomorphism :\log_b\colon H \to \mathbf_n, where Z''n'' denotes the additive group of integers modulo ''n''. The familiar base change formula for ordinary logarithms remains valid: If ''c'' is another generator of ''H'', then :\log_c a = \log_c b \cdot \log_b a.


Algorithms

The discrete logarithm problem is considered to be computationally intractable. That is, no efficient classical algorithm is known for computing discrete logarithms in general. A general algorithm for computing log''b'' ''a'' in
finite group Finite is the opposite of infinite. It may refer to: * Finite number (disambiguation) * Finite set, a set whose cardinality (number of elements) is some natural number * Finite verb, a verb form that has a subject, usually being inflected or ma ...
s ''G'' is to raise ''b'' to larger and larger powers ''k'' until the desired ''a'' is found. This algorithm is sometimes called ''trial multiplication''. It requires
running time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
linear in the size of the group ''G'' and thus exponential in the number of digits in the size of the group. Therefore, it is an exponential-time algorithm, practical only for small groups ''G''. More sophisticated algorithms exist, usually inspired by similar algorithms for integer factorization. These algorithms run faster than the naïve algorithm, some of them proportional to the square root of the size of the group, and thus exponential in half the number of digits in the size of the group. However none of them runs in
polynomial time In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...
(in the number of digits in the size of the group). *
Baby-step giant-step In group theory, a branch of mathematics, the baby-step giant-step is a meet-in-the-middle algorithm for computing the discrete logarithm or order of an element in a finite abelian group by Daniel Shanks. The discrete log problem is of fundamental ...
* Function field sieve *
Index calculus algorithm In computational number theory, the index calculus algorithm is a probabilistic algorithm for computing discrete logarithms. Dedicated to the discrete logarithm in (\mathbb/q\mathbb)^* where q is a prime, index calculus leads to a family of algorit ...
*
Number field sieve In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than . Heuristically, its complexity for factoring an integer (consisting of bits) is of the form :\exp\left( ...
*
Pohlig–Hellman algorithm In group theory, the Pohlig–Hellman algorithm, sometimes credited as the Silver–Pohlig–Hellman algorithm, Mollin 2006, pg. 344 is a special-purpose algorithm for computing discrete logarithms in a finite abelian group whose order is a smoot ...
*
Pollard's rho algorithm for logarithms Pollard's rho algorithm for logarithms is an algorithm introduced by John Pollard in 1978 to solve the discrete logarithm problem, analogous to Pollard's rho algorithm to solve the integer factorization problem. The goal is to compute \gamma suc ...
*
Pollard's kangaroo algorithm In computational number theory and computational algebra, Pollard's kangaroo algorithm (also Pollard's lambda algorithm, see Naming below) is an algorithm for solving the discrete logarithm problem. The algorithm was introduced in 1978 by the numb ...
(aka Pollard's lambda algorithm) There is an efficient
quantum algorithm In quantum computing, a quantum algorithm is an algorithm which runs on a realistic model of quantum computation, the most commonly used model being the quantum circuit model of computation. A classical (or non-quantum) algorithm is a finite s ...
due to
Peter Shor Peter Williston Shor (born August 14, 1959) is an American professor of applied mathematics at MIT. He is known for his work on quantum computation, in particular for devising Shor's algorithm, a quantum algorithm for factoring exponentially f ...
. Efficient classical algorithms also exist in certain special cases. For example, in the group of the integers modulo ''p'' under addition, the power ''b''''k'' becomes a product ''bk'', and equality means congruence modulo ''p'' in the integers. The
extended Euclidean algorithm In arithmetic and computer programming, the extended Euclidean algorithm is an extension to the Euclidean algorithm, and computes, in addition to the greatest common divisor (gcd) of integers ''a'' and ''b'', also the coefficients of Bézout's id ...
finds ''k'' quickly. With Diffie–Hellman a
cyclic group In group theory, a branch of abstract algebra in pure mathematics, a cyclic group or monogenous group is a group, denoted C''n'', that is generated by a single element. That is, it is a set of invertible elements with a single associative bina ...
modulus a prime ''p'' is used, allowing an efficient computation of the discrete logarithm with Pohlig–Hellman if the order of the group (being ''p''−1) is sufficiently
smooth Smooth may refer to: Mathematics * Smooth function, a function that is infinitely differentiable; used in calculus and topology * Smooth manifold, a differentiable manifold for which all the transition maps are smooth functions * Smooth algebrai ...
, i.e. has no large prime factors.


Comparison with integer factorization

While computing discrete logarithms and factoring integers are distinct problems, they share some properties: *both are special cases of the hidden subgroup problem for finite
abelian group In mathematics, an abelian group, also called a commutative group, is a group in which the result of applying the group operation to two group elements does not depend on the order in which they are written. That is, the group operation is comm ...
s, *both problems seem to be difficult (no efficient
algorithm In mathematics and computer science, an algorithm () is a finite sequence of rigorous instructions, typically used to solve a class of specific problems or to perform a computation. Algorithms are used as specifications for performing ...
s are known for non-
quantum computer Quantum computing is a type of computation whose operations can harness the phenomena of quantum mechanics, such as superposition, interference, and entanglement. Devices that perform quantum computations are known as quantum computers. Thoug ...
s), *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 used to construct various
cryptographic Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or '' -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adv ...
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
average-case complexity In computational complexity theory, the average-case complexity of an algorithm is the amount of some computational resource (typically time) used by the algorithm, averaged over all possible inputs. It is frequently contrasted with worst-case com ...
can be shown to be about as hard as the worst case using
random self-reducibility Random self-reducibility (RSR) is the rule that a good algorithm for the average case implies a good algorithm for the worst case. RSR is the ability to solve all instances of a problem by solving a large fraction of the instances. Definition If f ...
. At the same time, the inverse problem of discrete exponentiation is not difficult (it can be computed efficiently using
exponentiation by squaring Exponentiation is a mathematical operation, written as , involving two numbers, the '' base'' and the ''exponent'' or ''power'' , and pronounced as " (raised) to the (power of) ". When is a positive integer, exponentiation corresponds to re ...
, for example). This asymmetry is analogous to the one between integer factorization and integer
multiplication Multiplication (often denoted by the Multiplication sign, cross symbol , by the mid-line #Notation and terminology, dot operator , by juxtaposition, or, on computers, by an asterisk ) is one of the four Elementary arithmetic, elementary Op ...
. Both asymmetries (and other possibly one-way functions) have been exploited in the construction of cryptographic systems. Popular choices for the group ''G'' in discrete logarithm
cryptography Cryptography, or cryptology (from grc, , translit=kryptós "hidden, secret"; and ''graphein'', "to write", or '' -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of adv ...
(DLC) are the cyclic groups (Z''p'')× (e.g.
ElGamal encryption In cryptography, the ElGamal encryption system is an asymmetric key encryption algorithm for public-key cryptography which is based on the Diffie–Hellman key exchange. It was described by Taher Elgamal in 1985. ElGamal encryption is used in t ...
,
Diffie–Hellman key exchange Diffie–Hellman key exchangeSynonyms of Diffie–Hellman key exchange include: * Diffie–Hellman–Merkle key exchange * Diffie–Hellman key agreement * Diffie–Hellman key establishment * Diffie–Hellman key negotiation * Exponential key exc ...
, and the
Digital Signature Algorithm The Digital Signature Algorithm (DSA) is a public-key cryptosystem and Federal Information Processing Standard for digital signatures, based on the mathematical concept of modular exponentiation and the discrete logarithm problem. DSA is a var ...
) and cyclic subgroups of
elliptic curve In mathematics, an elliptic curve is a smooth, projective, algebraic curve of genus one, on which there is a specified point . An elliptic curve is defined over a field and describes points in , the Cartesian product of with itself. I ...
s over
finite field In mathematics, a finite field or Galois field (so-named in honor of Évariste Galois) is a field that contains a finite number of elements. As with any field, a finite field is a set on which the operations of multiplication, addition, subtr ...
s (''see''
Elliptic curve cryptography Elliptic-curve cryptography (ECC) is an approach to public-key cryptography based on the algebraic structure of elliptic curves over finite fields. ECC allows smaller keys compared to non-EC cryptography (based on plain Galois fields) to provid ...
). While there is no publicly known algorithm for solving the discrete logarithm problem in general, the first three steps of the
number field sieve In number theory, the general number field sieve (GNFS) is the most efficient classical algorithm known for factoring integers larger than . Heuristically, its complexity for factoring an integer (consisting of bits) is of the form :\exp\left( ...
algorithm only depend on the group ''G'', not on the specific elements of ''G'' whose finite log is desired. By precomputing these three steps for a specific group, one need only carry out the last step, which is much less computationally expensive than the first three, to obtain a specific logarithm in that group. It turns out that much Internet traffic uses one of a handful of groups that are of order 1024 bits or less, e.g. cyclic groups with order of the Oakley primes specified in RFC 2409. The
Logjam A log jam is a naturally occurring phenomenon characterized by a dense accumulation of tree trunks and pieces of large wood across a vast section of a river, stream, or lake. ("Large wood" is commonly defined as pieces of wood more than in diame ...
attack used this vulnerability to compromise a variety of Internet services that allowed the use of groups whose order was a 512-bit prime number, so called export grade. The authors of the
Logjam A log jam is a naturally occurring phenomenon characterized by a dense accumulation of tree trunks and pieces of large wood across a vast section of a river, stream, or lake. ("Large wood" is commonly defined as pieces of wood more than in diame ...
attack estimate that the much more difficult precomputation needed to solve the discrete log problem for a 1024-bit prime would be within the budget of a large national
intelligence agency An intelligence agency is a government agency responsible for the collection, analysis, and exploitation of information in support of law enforcement, national security, military, public safety, and foreign policy objectives. Means of inf ...
such as the U.S.
National Security Agency The National Security Agency (NSA) is a national-level intelligence agency of the United States Department of Defense, under the authority of the Director of National Intelligence (DNI). The NSA is responsible for global monitoring, collecti ...
(NSA). The Logjam authors speculate that precomputation against widely reused 1024 DH primes is behind claims in leaked NSA documents that NSA is able to break much of current cryptography.


References

* *


Further reading

* Richard Crandall;
Carl Pomerance Carl Bernard Pomerance (born 1944 in Joplin, Missouri) is an American number theorist. He attended college at Brown University and later received his Ph.D. from Harvard University in 1972 with a dissertation proving that any odd perfect number ...
. Chapter 5, ''Prime Numbers: A computational perspective'', 2nd ed., Springer. *


See also

* A. W. Faber Model 366 *
Percy Ludgate Percy Edwin Ludgate (2 August 1883 – 16 October 1922) was an Irish amateur scientist who designed the second analytical engine (general-purpose Turing-complete computer) in history. Life Ludgate was born on 2 August 1883 in Skibbereen, C ...
and Irish logarithm {{DEFAULTSORT:Discrete Logarithm Modular arithmetic Group theory Cryptography Logarithms Finite fields Computational hardness assumptions Unsolved problems in computer science