1.
Introduction
2.
Solovay-Strassen Algorithm,
2.1.
C++ Code for Solovay-Strassen Algorithm
3.
3.1.
What is cryptography?
3.2.
What is a primality test?
3.3.
What are the Legendre and Jacobi symbols?
3.4.
3.5.
What is the Solovay-Strassen algorithm?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

# What is Solovay-Strassen Algorithm?

Aashna Luthra
0 upvote
Master Python: Predicting weather forecasts
Speaker
Ashwin Goyal
Product Manager @

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

## 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:

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;
}
``````

Output:

Time complexity: O(klog3n)

Space complexity: O(1)

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

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

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.