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 r2 ≡ 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, αmj) concerning only the second coordinates, getting a list L1.
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 L2.
6. Search for a pair (j, y) ∈ L1 and a pair (i, y) ∈ L2
That is, find two pairs having identical second coordinates.
7. logαβ ← (mj + i) mod x
Proof
Suppose f (j, y) ∈ L1 and (i, y) ∈ L2, 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 ≤ m2−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 log3525 in (Z809 ∗, ·). Keep in mind that 809 is a prime integer and 3 is a primitive element in Z809 ∗, so we have n = 808, α = 3, β = 525, and m = Γ√ 808⅂ = 29. Then
α29 mod 809 = 99.
Firstly, we will compute the ordered pairs (j, 99j 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, L1.
The second list contains some ordered pairs (i, 525 × (3i)−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 L2.
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 log3525.
log3525 = (29 × 10 + 19) mod 808
= 309
As a final verification, we can calculate that 3309 ≡ 525 (mod 809).