Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Cryptography
3.
Discrete Logarithm
4.
Pollard Rho Method
5.
Algorithm
6.
Implementation 
6.1.
Code
6.2.
Output
7.
Frequently Asked Questions
7.1.
What is cryptography?
7.2.
What is a discrete logarithm?
7.3.
What is the maximum time for a discrete logarithm?
7.4.
What is the pollard rho algorithm?
7.5.
What are the different algorithms for solving discrete logarithms?
8.
Conclusion
Last Updated: Mar 27, 2024

The Pollard Rho but for Discrete Logarithm Algorithms

Author Ayushi Goyal
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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. 

Introduction

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

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.

Types

There are mainly three types of cryptography techniques.

  1. Public key or symmetric key cryptography
  2. Secret key or asymmetric key cryptography
  3. 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 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.

Discrete logarithm

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 = xSo, 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 xa yb =  xA yB, 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 - 

 

Function 1

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

ai ← g(xi-1ai-1)

bi ← h(xi-1bi-1)

 

Ai ← g(f(x2i-2), g(x2i-2a2i-2))

Bi ← h(f(x2i-2), h(x2i-2b2i-2))

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

Function 2
function 3

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

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 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 -. 

  1. What is Cryptography?
  2. Polyalphabetic: Hill Cipher
  3. Cryptanalysis of Vigenere Cipher
  4. Cipher-Permutate It, Keeping Plaintext
  5. Difference between Public Key and Private Key
     

Please refer to our guided paths on Coding Ninjas Studio to learn more about DSA, Competitive Programming, JavaScript, System Design, etc. And also, enroll in our courses and refer to the mock test and problems available. Have a look at the interview experiences and interview bundle for placement preparations.

Keep learning, and Keep Growing!

Do upvote our blogs if you find them engaging and knowledgeable.

Previous article
Algorithms: It’s Shank’s not Sharks
Next article
Pohlig and Hellman joined forces for this Algorithm
Live masterclass