Discrete logarithm

In group theory and number theory , the discrete logarithm is the analogue of the ordinary logarithm from analysis ; In this context, discrete can be understood as an integer . The discrete exponentiation in a cyclic group is the inverse of the discrete logarithm. As a comparison: The natural exponential function on the real numbers is the inverse function of the natural logarithm .

An important application occurs when computing modulo p . The discrete logarithm of the base is the smallest exponent here the equation , given the natural numbers , and the prime number . For example, when calculating modulo the discrete logarithm from to the base is equal , there is. ${\ displaystyle m}$ ${\ displaystyle a}$ ${\ displaystyle x}$ ${\ textstyle a ^ {x} \ equiv m \ mod p}$ ${\ displaystyle m}$ ${\ displaystyle a}$ ${\ displaystyle p}$ ${\ textstyle 11}$ ${\ displaystyle 5}$ ${\ displaystyle 2}$ ${\ textstyle 4}$ ${\ textstyle 2 ^ {4} = 16 \ equiv 5 \ mod 11}$

Since mostly only inefficient algorithms (in the sense of complexity theory ) are known for the discrete logarithm , while the inverse function, the discrete exponential function, can be calculated easily (in the sense of complexity theory), the discrete exponential function is suitable as a one-way function in cryptography . Application examples include a.

theory

general definition

Let it be a finite cyclic group with producer of order . Then is the discrete exponentiation ${\ textstyle (G, \ circ)}$ ${\ textstyle g}$ ${\ textstyle n}$

{\ textstyle {\ begin {aligned} \ exp _ {g} \ colon \ mathbb {Z} / n \ mathbb {Z} & \ to G \\ x & \ mapsto g ^ {x} \ end {aligned}}}

a group isomorphism . The associated inverse function

{\ textstyle {\ begin {aligned} \ log _ {g} \ colon G & \ to \ mathbb {Z} / n \ mathbb {Z} \\ x & \ mapsto \ log _ {g} x \ end {aligned}} }

is called the discrete logarithm to the base . ${\ textstyle g}$

The well-known basic change formula remains valid: If there is another generator, then is ${\ displaystyle h}$

{\ textstyle \ log _ {h} x = \ log _ {g} x \ cdot \ log _ {h} g \ mod n}

.

Furthermore, the following relationship applies to the discrete logarithm, which corresponds to the functional equation of the logarithm:

{\ textstyle \ log _ {g} x + \ log _ {g} y = \ log _ {g} (x \ circ y) \ mod n}

.

Prime residual class group

The special case when the cyclic group is a prime remainder class group , especially modulo prime numbers, is of practical use in cryptography .

Let be a prime number and a primitive root modulo , i.e. a generator of the prime residue class group . The discrete logarithm (also called index ) of a number that is too prime to the base is defined as the uniquely determined number with: ${\ textstyle p}$ ${\ displaystyle g}$ ${\ textstyle p}$ ${\ textstyle (\ mathbb {Z} / p \ mathbb {Z}) ^ {\ times}}$ ${\ textstyle p}$ ${\ displaystyle x}$ ${\ displaystyle g}$ ${\ textstyle a \ in \ {1,2, \ dotsc, p-1 \}}$

{\ textstyle g ^ {a} \ equiv x \ mod {p}}

and is denoted by or (for notation see congruence (number theory) and modulo ). ${\ textstyle a = \ log _ {g} x}$ ${\ textstyle a = \ operatorname {ind} _ {g} x}$

Algorithms for computing the discrete logarithm

So far, no fast algorithms for calculating the discrete logarithm are known. Their runtime would be polynomial to the length of the input. However, there are algorithms that find the solution more specifically than just trying it out . However, due to the mentioned runtime behavior and the orders of magnitude customary in cryptography (several hundred decimal places in number and base), they play practically no role. The most popular algorithms include:

example

The prime number and the associated prime remainder class group serve as an example . The table of values of the discrete exponentiation is now determined for the primitive root. ${\ textstyle p = 11}$ ${\ textstyle G = (\ mathbb {Z} / 11 \ mathbb {Z}) ^ {\ times} = \ {1,2, \ dotsc, 10 \}}$ ${\ textstyle g = 2}$

{\ textstyle {\ begin {array} {lcrlrl} 2 ^ {1} & = & 2 & \ equiv & 2 & \ mod {11} \\ 2 ^ {2} & = & 4 & \ equiv & 4 & \ mod {11} \\ 2 ^ {3} & = & 8 & \ equiv & 8 & \ mod {11} \\ 2 ^ {4} & = & 16 & \ equiv & 5 & \ mod {11} \\ 2 ^ {5} & = & 32 & \ equiv & 10 & \ mod {11} \\ 2 ^ {6} & = & 64 & \ equiv & 9 & \ mod {11} \\ 2 ^ {7} & = & 128 & \ equiv & 7 & \ mod {11} \\ 2 ^ {8} & = & 256 & \ equiv & 3 & \ mod {11} \\ 2 ^ {9} & = & 512 & \ equiv & 6 & \ mod {11} \\ 2 ^ {10} & = & 1024 & \ equiv & 1 & \ mod {11} \ end {array}}}

${\ textstyle a}$	1	2	3	4th	5	6th	7th	8th	9	10
${\ textstyle 2 ^ {a} \ mod 11}$	2	4th	8th	5	10	9	7th	3	6th	1

The fact that it is actually a primitive root modulo 11 can be seen from the discrete powers that differ in pairs. In other words, the entire prime residue class group can be generated using the discrete powers of . The table of values of the discrete logarithm is obtained by swapping the lines and sorting. ${\ displaystyle g}$ ${\ displaystyle g}$

${\ textstyle x}$	1	2	3	4th	5	6th	7th	8th	9	10
${\ textstyle \ log _ {2} x}$	10	1	8th	2	4th	9	7th	3	6th	5

literature

Erich Härtter: probability calculation , statistics and mathematical basics. Terms, definitions and formulas . Vandenhoeck & Ruprecht Verlag, Göttingen 1987, ISBN 3-525-40731-9 .