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