**EC Cryptography Tutorials - Herong's Tutorial Examples** - v1.03, by Herong Yang

Examples of Discrete Logarithm Problem (DLP)

This section describes the Discrete Logarithm Problem (DLP) in several Abelian Group examples, including elliptic curve groups.

Let's now look at some examples of the Discrete Logarithm Problem (DLP).

**DLP Example 1**:
Arithmetic addition over the integer set of ..., -2, -1, 0, 1, 2, ...
is an Abelian Group. Its DLP is defined as:

Given P and (Q = nP), find the smallest n as: n = Q/P

This DLP is very easy to solve. For example:

If P = 2, Q = 10, then n = 10/2 = 5 If P = -7, Q = -7, then n = (-7)/(-7) = 1 If P = 6700417, Q = 6700417, then n = 6700417/6700417 = 1 ...

**DLP Example 2**:
Arithmetic multiplication over the rational number set of ..., -1, -1/2, -1/3, 0, 1/3, 1/2, 1, ...
is an Abelian Group. Its DLP is defined as:

Given P and (Q = P^{n}), find the smallest n as: n = log_{P}(Q)

This DLP is not so easy to solve, for certain values of P and Q. For example:

If P = 2, Q = 16, then n = log_{2}(16) = 4 If P = 7, Q = 13841287201, then n = log_{7}(13841287201) = ? If P = 1/3, Q = 1/27, then n = log_{1/3}(1/27) = 3 If P = 1/11, Q = 1/1771561, then n = log_{1/11}(1/1771561) = ? ...

**DLP Example 3**:
Modular 10 arithmetic addition over the integer set of 0, 1, 2, ..., 9
is an Abelian Group. Its DLP is defined as:

Given P and (Q = nP), find smallest n as: n = Q/P (mod 10)

This DLP is still easy to solve. For example:

If P = 2, Q = 2, then n = 2/2 = 1 (mod 10) If P = 7, Q = 3, then n = 3/7 = 9 (mod 10) ...

**DLP Example 4**:
Modular 11 arithmetic multiplication over the integer set of 1, 2, ..., 10
is an Abelian Group. Its DLP is defined as:

Given P and (Q = P^{n}), find the smallest n as: n = log_{P}(Q) (mod 11)

This DLP is not so easy to solve, for some values of P. For example:

If P = 2, Q = 6, then n = log_{2}(6) = 4 (mod 11) If P = 7, Q = 1, then n = log_{7}(1) = ? (mod 11) ...

**DLP Example 5**:
Modular 6700417 arithmetic multiplication over the integer set of 1, 2, ..., 6700416
is an Abelian Group. Its DLP is defined as:

Given P and (Q = P^{n}), find the smallest n as: n = log_{P}(Q) (mod 6700417)

This DLP is hard to solve now, for large values of P. For example:

If P = 131071, Q = 524287, then n = log_{131071}(6) = ?

**DLP Example 6**:
Points on the elliptic curve y^{2} = x^{3} - 7x + 10
with the addition operation defined by the rule of chord
is an Abelian Group. Its DLP is defined as:

Given P and Q on the curve, find the smallest n, such that: Q = nP

This DLP is hard to solve. For example:

Given P = (1,2), Q = (-1,-4), and Q = nP, what is n?

Table of Contents

Geometric Introduction to Elliptic Curves

Algebraic Introduction to Elliptic Curves

Abelian Group and Elliptic Curves

►Discrete Logarithm Problem (DLP)

Doubling or Squaring in Abelian Group

Scalar Multiplication or Exponentiation

What Is Discrete Logarithm Problem (DLP)

►Examples of Discrete Logarithm Problem (DLP)

Scalar Multiplication on Elliptic Curve as Trapdoor Function

Generators and Cyclic Subgroups

tinyec - Python Library for ECC

ECDH (Elliptic Curve Diffie-Hellman) Key Exchange

ECDSA (Elliptic Curve Digital Signature Algorithm)