# All Science Fair Projects

## Science Fair Project Encyclopedia for Schools!

 Search    Browse    Forum  Coach    Links    Editor    Help    Tell-a-Friend    Encyclopedia    Dictionary

# Science Fair Project Encyclopedia

For information on any area of science that interests you,
enter a keyword (eg. scientific method, molecule, cloud, carbohydrate etc.).
Or else, you can start by choosing any of the categories below.

# Discrete logarithm

(Redirected from Discrete logarithm problem)

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

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

(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

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

## 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.

03-10-2013 05:06:04