Dixon’s Random Squares Algorithm

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

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

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

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 -

• The Pollard p-1 Algorithm
• What is the Rabin Cryptosystem?
• RSA Algorithm

You may refer to our Guided Path on Code Studios for enhancing your skill set on DSA, Competitive Programming, System 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!