Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction 
2.
Greatest Common Divisor
3.
Fermat's Theorem
4.
Dixon’s Random Squares Algorithm
4.1.
Algorithm
4.2.
Code Implementation in C++
4.2.1.
Output
4.3.
Code Implementation in Java
4.3.1.
Output
4.4.
Code Implementation in Python
4.4.1.
Output
5.
Frequently Asked Questions
5.1.
What is the use case of Dixon’s Random Squares Algorithm?
5.2.
What are some prerequisites to understanding Dixon’s Random Squares Algorithm?
5.3.
What is the RSA algorithm in cryptography?
5.4.
What is the full form of RSA and AES?
6.
Conclusion
Last Updated: Mar 27, 2024
Medium

Dixon’s Random Squares Algorithm

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

Introduction 

This article will look into Dixon’s Random Squares Algorithm and cover some prerequisites like Greatest Common Divisor and Fermat's theorem. Before reading this, you don’t need to know anything, so don’t worry and buckle up! We will go through everything. We got you covered.

introductory image

Greatest Common Divisor

Two integers, X and Y's greatest common divisor (GCD), is the greatest integer that divides both X and Y. GCD is also known as Highest Common Factor or HCF.

We use the Euclidean Algorithm technique for quickly determining the GCD of two integers.

Eg. GCD(8, 12) = 4.

The euclidean algorithm works based on the 2 observations listed below.

When we subtract a smaller number from a larger one, GCD does not change (we reduce the larger number). So, if we continue to deduct the larger of two values, we get GCD.

Instead of subtracting, divide the smaller integer, and the algorithm will stop when the remainder is zero.

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

Fermat's Theorem

As Dixon’s random squares algorithm is a modified version of Fermat's theorem. Refer to this amazing article to understand Fermat's theorem.

Dixon’s Random Squares Algorithm

The algorithm makes use of the property of square congruence modulo N. We locate a congruence within it by applying Fermat's factorization technique. This is done by matching to and using random or pseudo-random values (x) to x^2 congruent to y^2 mod n.

Algorithm

  • First, pick a bound B and locate the factor base (P) of all primes that are smaller than or equal to B.
     
  • The second step is to look for a positive integer z such that z^2mod(n) is B-Smooth. If none of a positive integer's prime factors is larger than B, it is said to be B-smooth.
     
  • After producing enough of these relations (often a small number more than the size of P), we combine the relations together using a linear algebraic technique, such as Gaussian Elimination. Until we have created an adequate number of smooth squares, repeat this step.
     
  • We arrive at the following equation after multiplying all of these relationships: x^2 congruent to y^2 mod n.

Now, we will implement Dixon’s Random Squares Algorithm. 

Code Implementation in C++

Implementation of the Dixon’s Random Squares Algorithm in C++: 

/* implementation of Dixon’s Random Squares Algorithm in C++ to identify a prime factor of a composite. */

#include<bits/stdc++.h>

using namespace std;

#define ll long long

int getGCD(int a, int b) {
  /* because, gcd(0, b) = b. */
  if (a == 0)
    return b;
  /* using the euclidean algorithm for finding GCD*/
  return getGCD(b % a, a);
}
/* Function implementing Dixon Factorization Algorithm to find factors  */
void dixonFactor(int num) {
  /* Factor base for the number provided */
  vector < int > base {
    2,
    3,
    5,
    7
  };


  /* Beginning with the root of the provided integer N's ceiling, */
  int begin = int(sqrt(num));

  /* Storing the related squares */
  vector < vector < int >> mp;

  /* For every number from the square root Till N */
  int len = base.size();
  for (int i = begin; i < num; i++) {
    vector < int > t;

    /* Finding the related squares */
    for (int j = 0; j < len; j++) {
      int L = ((int) pow(i, 2)) % num;
      int R = ((int) pow(base[j], 2)) % num;

      /* Add the two integers to the array if they are the associated squares. */
      if (L == R) {
        t.push_back(i);
        t.push_back(base[j]);
        mp.push_back(t);
      }
    }
  }

  vector < int > temp;
  len = mp.size();
  for (int i = 0; i < len; i++) {
    int fact = getGCD(mp[i][0] - mp[i][1], num);

    /*Adding it to the final factor array if we discover a factor other than 1 */
    if (fact != 1)
      temp.push_back(fact);
  }
  set < int > s(temp.begin(), temp.end());
  for (auto i = s.begin(); i != s.end(); i++)
    cout << ( * i) << " ";
}

int main() {
  int n;
  cout << "Enter a number:";
  cin >> n;
  dixonFactor(n);
  return 0;
}

Output

output

Code Implementation in Java

Implementation of Dixon’s Random Squares Algorithm in Java to identify a prime factor of a composite.

import java.util.*;

class ClassName {
  static int gcd(int a, int b) {
    a = Math.abs(a);
    b = Math.abs(b);
    
    /* because, gcd(0, b) = b. */
    if (a == 0) return b;
    /* using the euclidean algorithm for finding GCD */
    return gcd(b % a, a);
  }
  
  /* Function implementing Dixon Factorization Algorithm to find factors  */
  static void dixonFactor(int n) {
    /* Factor base for the number provided */
    int[] base = {
      2,
      3,
      5,
      7
    };

    /* Beginning with the root of the provided integer N's ceiling, */
    int start = (int)(Math.sqrt(n));

    /* For every number from the square root Till N */
    int length = base.length;

    /* Storing the related squares */
    ArrayList < ArrayList < Integer > > mp = new ArrayList < ArrayList < Integer > > ();
    
    /* For every number from the square root Till N */    
    for (int i = start; i < n; i++) {
      /* Finding the related squares */
      for (int j = 0; j < length; j++) {
        int L = ((int) Math.pow(i, 2)) % n;
        int R = ((int) Math.pow(base[j], 2)) % n;

        /* Add the two integers to the array if they are the associated squares. */
        if (L == R) {
          ArrayList < Integer > t = new ArrayList < Integer > ();
          t.add(i);
          t.add(base[j]);
          mp.add(t);
        }
      }
    }

    ArrayList < Integer > temp = new ArrayList < Integer > ();

    length = mp.size();
    for (int i = 0; i < length; i++) {
      int fact = gcd(mp.get(i).get(0) - mp.get(i).get(1), n);

      /* Adding it to the final factor array if we discover a factor other than 1 */

      if (fact != 1)
        temp.add(fact);
    }

    HashSet < Integer > st = new HashSet < Integer > ();
    for (int i = 0; i < temp.size(); i++)
      st.add(temp.get(i));

    for (int i: st) System.out.print(i + " ");
  }
  
  public static void main(String[] args) {
    Scanner scn = new Scanner(System.in);
    System.out.println("Enter the Number:");
    int n = scn.nextInt();
    dixonFactor(n);
  }
}

Output

output

Code Implementation in Python

Implementation of Dixon’s Random Squares Algorithm in Java to identify a prime factor of a composite.

from math import sqrt, gcd
import numpy as np

""" Function implementing Dixon Factorization Algorithm to find factors """
def dixonFactor(n):
    """Factor base for the number provided"""
    base = [2, 3, 5, 7]

    """Starting from the ceil of the root of the given number N """
    start = int(sqrt(n))
    """ Storing the related squares"""
    pairs = []

    """ For every number from the square root Till N """
    for i in range(start, n):
        """Finding the related squares"""
        for j in range(len(base)):
            L = i**2 % n
            R = base[j] ** 2 % n
            """  Add the two integers to the array if they are the associated squares. """
            if L == R:
                pairs.append([i, base[j]])
    new = []
    for i in range(len(pairs)):
        factor = gcd(pairs[i][0] - pairs[i][1], n)
        """Adding it to the final factor array if we discover a factor other than 1"""
        if factor != 1:
            new.append(factor)
    x = np.array(new)
    return np.unique(x)

if __name__ == "__main__":
    print(dixonFactor(1313))

Output

output

Frequently Asked Questions

What is the use case of Dixon’s Random Squares Algorithm?

Dixon’s Random Squares Algorithm is an excellent method for determining the prime factors of any integer.

What are some prerequisites to understanding Dixon’s Random Squares Algorithm?

Knowledge of the Greatest Common Divisor and Fermat's theorem helps us understand Dixon’s Random Squares Algorithm.

What is the RSA algorithm in cryptography?

The RSA algorithm (Rivest-Shamir-Adleman) is the foundation of a cryptosystem, which is a collection of cryptographic algorithms used for certain security services or objectives.

What is the full form of RSA and AES?

AES stands for Advanced Encryption Standard, and RSA is for Rivest, Shamir, and Adleman.

Conclusion

This article looked into Dixon’s Random Squares Algorithm and covered prerequisites like Greatest Common Divisor and Fermat's theorem.

If you want to explore more, here are some related articles -


You may refer to our Guided Path on Code Studios for enhancing your skill set on DSACompetitive ProgrammingSystem Design, etc. Check out essential interview questions, practice our available mock tests, look at the interview bundle for interview preparations, and so much more!

Happy Learning Ninjas!

Previous article
The Pollard Rho Algorithm
Next article
What are the Factoring Algorithms in Practice?
Live masterclass