Cryptography is the technique used for securing communication. It uses encryption and decryption algorithms to protect data. Encryption is the process of converting plain text (human-readable) text into cipher text. Decryption is the process of converting non-human readable text back into plain text. These algorithms are called Cipher.

This article will discuss the pollard rho method for finding discrete logarithms. We also discuss the algorithm along with its implementation. But, before that, let’s discuss the terms individually.

Cryptography

It is the study of encrypting and decrypting data using mathematics. It allows you to store sensitive information or send it through insecure networks. Cryptography can be powerful or weak. The time and resources required to determine its strength. Strong cryptography produces ciphertext that is extremely difficult to decode.

Cryptography is a word used in computing to describe secured information systems that transform messages in difficult hard-to-decipher ways using mathematical concepts and a sequence of rule-based computations known as algorithms. These proposed approaches are used for encryption keys generation, digital signature, data privacy verification, online surfing, and private communications, including banking transactions and email.

There are mainly three types of cryptography techniques.

Public key or symmetric key cryptography

Secret key or asymmetric key cryptography

Hash functions

Get the tech career you deserve, faster!

Connect with our expert counsellors to understand how to hack your way to success

User rating 4.7/5

1:1 doubt support

95% placement record

Akash Pal

Senior Software Engineer

326% Hike After Job Bootcamp

Himanshu Gusain

Programmer Analyst

32 LPA After Job Bootcamp

After Job Bootcamp

Discrete Logarithm

Mathematically, for two real numbers, 'x' and 'y', the logarithm is log_{y}x, which means y^{m} = x, where 'm' is a number. An integer 'z' that solves the equation y^{z} = x mod p is known as the discrete logarithm of 'x' to the base 'y'. The difficulty is finding the value in O(p) time complexity.

The discrete logarithm is computed very quickly in some cases. But, there are not many known methods for its computation. The algorithms that exist depend on integer factorization. Some of these algorithms are-

Baby-step giant-step

Index calculus algorithm

Function field sieve

Pohlig–Hellman algorithm

Number field sieve

Pollard's rho algorithm for logarithms

Pollard's kangaroo algorithm

Our major focus in this article is Pollard’s rho algorithm for logarithms. So, let’s dive right into it.

Pollard Rho Method

Pollard rho algorithm was introduced in 1978 by John Pollard. The main aim of this algorithm is to solve discrete logarithm problems. As in discrete logarithm problems, we are given an equation : y^{z} = x. So, this algorithm aims to compute the value of 'z', such that 'x' belongs to the cyclic group 'G' of 'y'.

A cyclic group is generally a group of elements generated by a single integer. For example, numerous of values will be generated for 'x' for different values of 'z' on 'y'. So, the group of all those values of 'x' is known as the cyclic group.

Algorithm

The algorithm computes integers a, b, A, and B such that x^{a}y^{b} =^{ }x^{A}y^{B}, where r = x^{ai}y^{bi}. Then we can easily compute the value of ‘z’ using equation (B - b)z = (A - a) (mod p).

To define such functions, divide group ‘G’ into approximately three disjoint subsets of equal size. Let these subsets be G0, G1, and G2. According to the algorithm, x, and y belongs to the set G, and G is a combination of G0, G1, and G2.

X,Y ∈ G

G = G0 ∪ G1 ∪ G2

To calculate the value of ‘r’, the function F is defined as -

To calculate the value of a,b,A and B, the equations used are -

So, we need two more functions, g and h. These functions are defined as -

Implementation

Code

#include <iostream>
using namespace std;
const int p = 1018,P = p + 1;
const int x = 2;
const int y = 5;
void pollard_rho(int& r, int& a, int& b) {
switch (r % 3)
{
case 0:
r = r * r % p;
a = a*2 % p;
b = b*2 % p;
break;
case 1:
r = r * x % P;
a = (a+1) % P;
break;
case 2:
r = r * y % P;
b = (b+1) % p;
break;
}
}
int main() {
int r = 5, a = 5, b = 5;
int R = x, A = a, B = b;
printf(" P r a b R A B\n");
// Start loop for each value of P
for (int i = 1; i < p; ++i)
{
pollard_rho(r, a, b);
pollard_rho(R, A, B);
pollard_rho(R, A, B);
printf("%3d %4d %3d %3d %4d %3d %3d\n", i, r, a, b, R, A, B);
if (r == R)
break;
}
return 0;
}

Output

Frequently Asked Questions

What is cryptography?

Cryptography is a method of encrypting and decrypting messages and information to establish a secure information exchange between the sender and the receiver.

What is a discrete logarithm?

Mathematically, for two real numbers, ‘x’ and ‘y’, the logarithm is log_{y}x, which means y^{m} = x, where ‘m’ is a number. An integer ‘z’ that solves the equation y^{z} = x mod p is known as the discrete logarithm of ‘x’ to the base ‘y’.

What is the maximum time for a discrete logarithm?

For solving the equation y^{z} = x mod p, the maximum time available is O(P).

What is the pollard rho algorithm?

Pollard rho algorithm was introduced in 1978 by John Pollard. The main aim of this algorithm is to solve discrete logarithm problems. .

What are the different algorithms for solving discrete logarithms?

Other than the pollard rho algorithm, discrete logarithms can be solved using other algorithms. These are - The baby-step giant-step, Index calculus algorithm, Function field sieve, Pohlig–Hellman algorithm, Number field sieve, and Pollard's kangaroo algorithm.

Conclusion

In this article, we have discussed the pollard rho algorithm for solving discrete logarithms. We also discussed cryptography, discrete logarithms, and the pollard rho algorithm. Then we discussed the algorithms used by the algorithm for solving discrete logarithm equations. Using this algorithm, we implemented the pollard rho algorithm.

Do not stop learning! We recommend you read these articles -.