Discrete logarithm - Citizendia

In mathematics, specifically in abstract algebra and its applications, discrete logarithms are group-theoretic analogues of ordinary logarithms. Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and Abstract algebra is the subject area of Mathematics that studies Algebraic structures such as groups, rings, fields, modules In Mathematics, a group is a set of elements together with an operation that combines any two of its elements to form a third element In Mathematics, the logarithm of a number to a given base is the power or Exponent to which the base must be raised in order to produce 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$ .

1 Example
2 Definition
3 Algorithms
4 Comparison with integer factorization
5 Cryptography
6 References

Example

Discrete logarithms are perhaps simplest to understand in the group (Z_p)^×. In Modular arithmetic the set of Congruence classes Relatively prime to the modulus n form a group under multiplication called the multiplicative This is the set of congruence classes {1, …, p − 1} under multiplication modulo the prime p. In Mathematics, modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic) is a system of Arithmetic for Integers In Mathematics, modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic) is a system of Arithmetic for Integers In Mathematics, a prime number (or a prime) is a Natural number which has exactly two distinct natural number Divisors 1

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₁₇)^×.

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¹⁶ ≡ 1 (mod 17) it also follows that if n is an integer then 3^{4+16 n} ≡ 13 x 1ⁿ ≡ 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₁₇)^× these are all solutions. In Number theory, given an Integer a and a positive integer n with gcd ( a, n) = 1 the multiplicative order Equivalently, the solution can be expressed as k ≡ 4 (mod 16).

Definition

In general, let G be a finite cyclic group with n elements. In Group theory, a cyclic group or monogenous group is a group that can be generated by a single element in the sense that the group has an 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. In Abstract algebra, a generating set of a group G is a Subset S such that every element of G can be expressed as the Furthermore, any two such integers representing g will be congruent modulo n. In Mathematics, modular arithmetic (sometimes called modulo arithmetic, or clock arithmetic) is a system of Arithmetic for Integers We can thus define a function

$\log_b:\ G\ \rightarrow\ \mathbf{Z}_n$

(where Z_n denotes the ring of integers modulo n) by assigning to g the congruence class of k modulo n. In Mathematics, a ring is an Algebraic structure which generalizes the algebraic properties of the Integers though the rational, real This function is a group isomorphism, called the discrete logarithm to base b. 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

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

$\log_c (g) = \log_c (b) \cdot \log_b (g).$

Algorithms

No efficient 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. To analyze an Algorithm is to determine the amount of resources (such as time and storage necessary to execute it There exists an efficient quantum algorithm due to Peter Shor however (http://arxiv.org/abs/quant-ph/9508027).

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.

Baby-step giant-step
Pollard's rho algorithm for logarithms
Pollard's lambda algorithm (aka Pollard's kangaroo 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 non-quantum 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 exploited to construct various cryptographic (code) systems. In Group theory, a branch of mathematics the baby-step giant-step Algorithm is a series of well-defined steps to compute the Discrete logarithm. Pollard's rho algorithm for logarithms is an algorithm for solving the Discrete logarithm problem analogous to Pollard's rho algorithm for solving the Integer In mathematics specifically Computational number theory and Computational algebra, Pollard's lambda algorithm (aka Pollard's kangaroo algorithm, see In mathematics the Pohlig–Hellman algorithm is an Algorithm for the computation of Discrete logarithms in a Multiplicative group whose order is a In Group theory, the index calculus algorithm is an Algorithm for computing Discrete logarithms This is the best known algorithm for certain groups such In Mathematics, the general number field sieve (GNFS is the most efficient classical Algorithm known for factoring integers larger than 100 In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation A quantum computer is a device for Computation that makes direct use of distinctively Quantum mechanical Phenomena, such as superposition Cryptography (or cryptology; from Greek grc κρυπτός kryptos, "hidden secret" and grc γράφω gráphō, "I write"

Cryptography

Computing discrete logarithms is apparently difficult. Not only is no efficient algorithm known for the worst case, but the average-case complexity can be shown to be at least as hard as the worst case using random self-reducibility. Random self-reducibility (RSR: A good algorithm for the average case implies a good algorithm for the worst case

At the same time, the inverse problem of discrete exponentiation is not (it can be computed efficiently using exponentiation by squaring, for example). Exponentiating by squaring is an Algorithm used for the fast computation of large Integer powers of a Number. 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. In Cryptography, the ElGamal encryption system is an Asymmetric key encryption algorithm for Public-key cryptography which is based on the Diffie-Hellman Diffie-Hellman key exchange ( D-H) is a Cryptographic protocol that allows two parties that have no prior knowledge of each other to jointly establish a shared secret The Digital Signature Algorithm (DSA is a United States Federal Government standard or FIPS for Digital signatures It was proposed by the

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 smooth, projective Algebraic curve of genus one on which there is a specified point O 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 The use

References

Richard Crandall; Carl Pomerance. Richard E Crandall is an American Computer scientist and physicist who has made contributions to Computational number theory, most notably the development Carl Pomerance (born in 1944 in Joplin, Missouri) is a well known number theorist. Chapter 5, Prime Numbers: A computational perspective, 2nd ed. , Springer.
Douglas R. Stinson. Cryptography: Theory and Practice, CRC Press, 2002.

© 2009 citizendia.org; parts available under the terms of GNU Free Documentation License, from http://en.wikipedia.org
network: | |