Do you think IIT Guwahati certified course can help you in your career?
Introduction
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
Discrete Logarithm
Mathematically, for two real numbers, 'x' and 'y', the logarithm is logyx, which means ym = x, where 'm' is a number. An integer 'z' that solves the equation yz = 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 : yz = 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 xayb =xAyB, where r = xaiybi. 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 -
ai ← g(xi-1, ai-1)
bi ← h(xi-1, bi-1)
Ai ← g(f(x2i-2), g(x2i-2, a2i-2))
Bi ← h(f(x2i-2), h(x2i-2, b2i-2))
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;
}
You can also try this code with Online C++ Compiler
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 logyx, which means ym = x, where ‘m’ is a number. An integer ‘z’ that solves the equation yz = 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 yz = 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 -.
85+ registered 