## Introduction

Cryptography is a method to achieve confidentiality among mutually trusted people and organizations. The messages are sent via an unsecured network with no proper security. If we do not use Cryptography to encrypt the messages, it may hamper the confidentiality of the text.

In this blog, we will detail several aspects of one of the most important algorithms for discrete logarithms- Shank’s Algorithm. We will also see an example of Shank’s Algorithm to understand it better.

## Shank’s Algorithm

Shank’s Algorithm is the first non-trivial algorithm that performs a time-memory trade-off. It is used in modular arithmetic to solve for r in the form r^{2} ≡ n (mod p)

where p is prime, and r is the square root of n modulo p.

Shank’s Algorithm constructs two lists of size √n and then search for a collision. This is because collision helps the required discrete logarithm to be calculated. It solves ECDLP problems comparatively faster than brute or naive approaches. However, its time complexity is exponential such,

O(√m) = O(√n) = O(√p)

Also, it requires O(√p) storage.

### The Shank’s Algorithm Function

SHANK’S(G, x, α, β)

1. m ← Γ√ x⅂

2. for j ← 0 to m−1

do calculate α^{mj}

3. Sort the m-ordered pairs (j, α^{m}j) concerning only the second coordinates, getting a list L_{1}.

4. for i ← 0 to m−1

do calculate βα^{−i}

5. Sort the m-ordered pairs (i, βα^{−i}) concerning only the second coordinates, getting a list L_{2}.

6. Search for a pair (j, y) ∈ L_{1} and a pair (i, y) ∈ L_{2}

That is, find two pairs having identical second coordinates.

7. log_{α}β ← (mj + i) mod x

### Proof

Suppose f (j, y) ∈ L_{1} and (i, y) ∈ L_{2}, then

α^{mj} = y = βα^{−i},

So

α^{mj+i} = β.

Conversely, for any β ∈〈α〉, we have 0 ≤ log_{α}β ≤ x−1. If we divide log_{α}β by the calculated integer m, we can express log_{α}β in the form

log_{α}β = mj + i,

where 0 ≤ j, i ≤ m−1. The equation j ≤ m − 1 stands because

log_{α}β ≤ n−1 ≤ m^{2}−1 = m(m−1) + m−1.

Therefore, the search in step 6 will be successful. However, if β ∉〈α〉, then step 6 will not be successful. Here is a small example to illustrate Shank’s Algorithm.

### Example

Here is a simple example to illustrate Shank’s Algorithm.

Suppose we wish to find log_{3}525 in (Z^{809 ∗}, ·). Keep in mind that 809 is a prime integer and 3 is a primitive element in Z^{809 ∗}, so we have n = 808, α = 3, β = 525, and m = Γ√ 808⅂ = 29. Then

α^{29} mod 809 = 99.

Firstly, we will compute the ordered pairs (j, 99^{j} mod 809) for 0 ≤ j ≤ 28. Then, obtain the list containing following pairs:

(0, 1) (2, 93) (3, 308) (5, 329) (4, 559)

(6, 211) (7, 664) (8, 207) (10, 644) (1, 99)

(9, 268) (11, 654) (12, 26) (13, 147) (15, 727)

(14, 800)(16, 781) (17, 464) (18, 632) (20, 528)

(19, 275) (21, 496) (22, 564) (23, 15) (25, 586)

(24, 676) (26, 575) (27, 295) (28, 81)

This list is then ordered as required to produce the first list, L_{1}.

The second list contains some ordered pairs (i, 525 × (3^{i})^{−1} mod 809), while 0 ≤ j ≤ 28.

The list we obtain is as follows:

(0, 525) (1, 175) (2, 328) (3, 379) (5, 132)

(4, 396) (6, 44) (7, 554) (8, 724) (10, 440)

(9, 511)(11, 686) (12, 768) (13, 256) (15, 388)

(14, 355)(16, 399) (17, 133) (18, 314) (20, 754)

(19, 644) (21, 521) (22, 713) (23, 777) (25, 356)

(24, 259) (26, 658) (27, 489) (28, 163)

After sorting this list, we get L_{2}.

If we proceed simultaneously through both the two sorted lists searching for a common second coordinate, we came to know that (10, 644) is present in L1 and (19, 644) is in L2. So, we can calculate log_{3}525.

log_{3}525 = (29 × 10 + 19) mod 808

= 309

As a final verification, we can calculate that 3^{309} ≡ 525 (mod 809).