Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Solovay-Strassen Algorithm,
2.1.
C++ Code for Solovay-Strassen Algorithm
3.
Frequently Asked Questions
3.1.
What is cryptography?
3.2.
What is a primality test?
3.3.
What are the Legendre and Jacobi symbols?
3.4.
What is quadratic residue?
3.5.
What is the Solovay-Strassen algorithm?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

What is Solovay-Strassen Algorithm?

Author Aashna Luthra
0 upvote

Introduction

Welcome Ninjas! Do you want to know how to quickly determine, with high probability, whether a number is prime or not? This is implemented by the Solovay-Strassen algorithm.

Are you interested to know more about this algorithm? Great! You are at the right place.

introductory image

Solovay-Strassen Algorithm,

A pair of big prime numbers must be created to implement the RSA cryptosystem. We will explore one approach to achieve this, the Solovay-Strassen Algorithm. Due to all the critical analysis, determining with perfect certainty whether a number is prime may take some time. Our actual goal is for a quick method. Therefore, we compromise on certainty to achieve speed. In other words, rather than depending only on perfect certainty, we use a method that instantly verifies if a number is prime. We must look at certain ideas from number theory in order to explain the approach.

Let's assume n is a prime number then:

mathematical expression

As n cannot possibly be a prime, therefore (i.e., n is a composite number). However, because there are composite numbers n, (1) can be met for some a. With base a, these numbers are referred to as Euler pseudoprimes. However, it can be shown that there are only a maximum of n/2 values smaller than n, for which n is an Euler pseudoprime with base a for every given composite number n. The Solovay-Strassen algorithm is built on this. This is how the algorithm works:

  • Let n denote the integer being checked for primality.
  • Pick an integer at random, with a<n.
  • If a/n ≠ a(n-1)/2 mod n, then ground to a stop and state that n is composite.
  • Otherwise, carry on doing the first two steps again (where k is a preselected integer).

C++ Code for Solovay-Strassen Algorithm

#include <bits/stdc++.h>
using namespace std;

/*modulo function for performing binary exponentiation */
long long calculateModulo(long long base, long long expo, long long mod){
	long long m = 1;
	long long n = base;
	while (expo > 0){
		if (expo % 2 == 1)
			m = (m * n) % mod;

		n = (n * n) % mod;
		expo = expo / 2;
	}
	return m % mod;
}

/* Calculate the *jacobi symbol for a given number */
int calculateJacobiSymbol(long long a, long long n){
	if (!a)
                       /*0n= 0 */
		return 0;  

	int res = 1;
	if (a < 0){
                 /*an= -(an) * -(1n) */
		a = -a; 
		if (n % 4 == 3)
                                   /* -(1n)=-1 if n= 3 (mod 4) */
			res= -res; 	
          }

	if (a == 1)
                       /* (1n) = 1 */
		return res;

	while (a){
		if (a < 0){
                                   /*an= -(an) * -(1n) */
			a = -a;
			if (n % 4 == 3)
                                                /* -(1n)=-1 if n= 3 (mod 4) */
				res = -res;
		}

		while (a % 2 == 0){
			a = a / 2;
			if (n % 8 == 3 || n % 8 == 5)
				res= -res;

		}

		swap(a, n);

		if (a % 4 == 3 && n % 4 == 3)
			res= -res;
		a = a % n;

		if (a > n / 2)
			a = a - n;

	}

	if (n == 1)
		return res;

	return 0;
}

/* Solovay-Strassen Primality Test */
bool solovoyStrassenAlgo(long long p, int iterations){
	if (p < 2)
		return false;
	if (p != 2 && p % 2 == 0)
		return false;

	for (int i = 0; i < iterations; i++){
		/*Generating a random number ‘a’ */
		long long a = rand() % (p - 1) + 1;
		long long jacobi = (p + calculateJacobiSymbol(a, p)) % p;
		long long mod = calculateModulo(a, (p - 1) / 2, p);

		if (!jacobi || mod != jacobi)
			return false;
	}
	return true;
}

int main(){
	int iterations = 40;
	long long number1 = 21;
	long long number2 = 17;

	if (solovoyStrassenAlgo(number1 , iterations))
		cout<< number1<<" is probable prime"<<endl;
	else
		cout<< number1<<" is composite"<<endl;

	if (solovoyStrassenAlgo(number2 , iterations))
		cout<< number2<<" is probable prime"<<endl;
	else
		cout<< number2<<" is composite"<<endl;

	return 0;
}
You can also try this code with Online C++ Compiler
Run Code


Output: 

output


Time complexity: O(klog3n) 

Space complexity: O(1)

Frequently Asked Questions

What is cryptography?

The use of codes to secure information and communications in such a way that only the intended receiver can decode and process them is known as cryptography.

What is a primality test?

A primality test is used to determine whether an input integer is prime. These tests can sometimes be deterministic. They are perfect for deciding if a number is prime or composite.

What are the Legendre and Jacobi symbols?

The Legendre symbol is a function that stores information about whether an integer is a quadratic residue modulo an odd prime. The Jacobi symbol is used to simplify computations involving quadratic residues.

What is quadratic residue?

If m and n are coprime integers, then m is called a quadratic residue modulo n if the congruence x2m(mod n)has a solution.

What is the Solovay-Strassen algorithm?

The Solovay–Strassen algorithm is a type of primality test which is probabilistic and is used to determine if a number is probably prime or composite.

Conclusion

In this article, we explored the Solovay-Strassen algorithm. We explored how the Solovay-Strassen algorithm is implemented. Check out more articles on cryptography as follows:


Refer to our guided paths on Coding Ninjas Studio to learn more about DSA, System Design, Competitive Programming, JavaScript, etc. Enroll in our courses and refer to the problems available and mock tests. Take a look at the interview bundle and interview experiences for placement preparations.

Happy Learning Ninja!

Live masterclass