Discrete logarithms are fundamental to a number of public-key algorithms, includ- ing Diffie-Hellman key exchange and the digital signature algorithm (DSA).

**DISCRETE
LOGARITHMS**

Discrete logarithms are fundamental to a number
of public-key algorithms, includ- ing Diffie-Hellman key exchange and the digital
signature algorithm (DSA). This section provides a brief overview of discrete
logarithms. For the interested
reader, more detailed developments of this topic
can be found in [ORE67]
and [LEVE90].

The Powers of
an Integer, Modulo *n*

Recall from Eulerâ€™s theorem [Equation (8.4)]
that, for every *a *and *n *that are rela- tively prime,

where Ï•(*n*), Eulerâ€™s totient function, is the number of positive integers less than *n *and relatively prime to *n*. Now consider the more general expression:

If *a *and
*n *are relatively prime, then there is at least one integer *m *that satisfies Equation (8.10), namely, *M** *= Ï•(*n*).
The least positive exponent *m** *for which Equation (8.10) holds is referred to in several
ways:

â€¢
The order of *a *(mod *n*)

â€¢
The exponent to which *a *belongs (mod *n*)

â€¢
The length of the period
generated by *a*

Table 8.3 shows all the powers of *a*, modulo 19 for all positive *a *6 19. The length of
the sequence for each base value is indicated by shading. Note the following:

**1.
**All sequences end in 1. This is consistent with the reasoning of the preceding few paragraphs.

**2.
**The length of a sequence divides Ï•(19)
= 18. That is, an integral number of sequences occur in each row of the table.

**3.
**Some of the sequences
are of length 18. In this case, it is said that the base inte-
ger *a *generates (via powers)
the set of nonzero integers
modulo 19. Each such
integer is called a primitive
root of the modulus 19.

More generally, we can say that the highest possible
exponent to which a number can belong (mod *n*) is Ï•(*n*). If a number is of this order, it is referred to as a **primitive root **of *n*. The importance of this notion
is that if *a *is a primitive root of *n*,
then its powers

are distinct (mod *n*) and are all relatively prime to *n*. In particular, for a prime
number *p*, if *a *is a primitive
root of *p*, then

are distinct (mod *p*). For the prime number 19, its primitive roots are 2, 3,
10, 13, 14, and 15.

Not all integers have primitive roots. In
fact, the only integers with primitive
roots are those of the form 2, 4, *p**a*, and 2*p**a*, where *p *is any odd prime and
*a *is
a positive integer. The proof is not
simple but can be found in many number theory books, including [ORE76].

Logarithms for Modular Arithmetic

With ordinary positive real numbers, the
logarithm function is the inverse of expo- nentiation. An analogous function
exists for modular arithmetic.

Let us briefly
review the properties of ordinary logarithms. The logarithm of a number is
defined to be the power to which some positive base (except 1) must be raised in order to equal the number. That is, for base *x *and for a value *y*,

Consider a primitive root *a *for some prime number *p *(the
argument can be developed for nonprimes as well). Then we know that the powers
of *a *from 1 through (*p *- 1) produce each
integer from 1 through (*p *- 1) exactly once. We
also know that any integer *b *satisfies

by the definition of modular arithmetic. It follows that for any integer *b *and a prim- itive root *a *of prime
number *p*, we can find a unique exponent
*i *such that

This exponent *i *is referred to as the **discrete
logarithm **of the number *b *for the base *a *(mod *p*). We denote this
value as dlog*a*,*p*(*b*).10

Note the following:

dlog*a*,*p*(1)
= 0
because *a*0 mod
*p *= 1 mod *p *= 1
**(8.13)**

dlog*a*,*p*(*a*) = 1 because *a*1 mod *p *= *a
***(8.14)**

This demonstrates the analogy between true
logarithms and discrete logarithms.

Keep in mind that unique discrete logarithms
mod *m *to some base *a *exist only if *a *is a primitive root of *m*.

Table 8.4, which is directly derived from Table 8.3, shows the sets of discrete
logarithms that can be defined for modulus 19.

**Table 8.4 **Tables
of Discrete Logarithms, Modulo 19

Calculation of Discrete Logarithms

Consider the equation

*y *= *g**x *mod
*p*

Given *g*,
*x*, and *p*, it is a
straightforward matter to calculate *y*. At the worst, we
must perform *x *repeated
multiplications, and algorithms exist for achieving greater effi- ciency (see
Chapter 9).

However,
given *y*, *g*, and *p*, it is, in general, very difficult to calculate *x *(take the
discrete logarithm). The difficulty
seems to be on the same order of magnitude as that of factoring primes
required for RSA. At the time of this writing,
the asymptoti- cally fastest
known algorithm for taking discrete
logarithms modulo a prime number is on the order
of [BETH91]:

*e*((ln *p*)1/3(ln(ln *p*))2/3))

which is not feasible for large primes.

Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail

Cryptography and Network Security Principles and Practice : Asymmetric Ciphers : Introduction to Number Theory : Discrete Logarithms |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright Â© 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.