The Solovay-Strassen primality test is a probabilistic technique used to ascertain the primality status of a specific number. In contrast to deterministic approaches such as the Sieve of Eratosthenes, which offer certainty in determining primality but can be computationally demanding for larger numbers, Solovay-Strassen strikes a balance between effectiveness and precision.
At its essence, the algorithm utilizes Euler's lemma and the Jacobi symbol to determine the primality of a specified integer n. Euler's lemma specifies that for an odd prime p and an integer a, a is a quadratic residue modulo p if and only if a^((p-1)/2) ≡1(mod p). The Jacobi symbol, which extends the concept of the Legendre symbol, aids in identifying whether an integer is a quadratic residue modulo an odd prime.
In the Solovay-Strassen approach, when dealing with an odd integer n, the procedure chooses random integers a and calculates two quantities: the Jacobi symbol x=(a/n) and y= a^((n-1)/2) mod n. In the case of a prime n, there will be numerous random a values where both x and y match. Conversely, if n is a composite number, it's highly likely that x and y will not be equal.
By carrying out this procedure repeatedly for a set number of cycles and selecting varied random values each time, the Solovay-Strassen test offers a probabilistic evaluation of primality. The accuracy of the test is directly impacted by the quantity of iterations, where a larger number of iterations results in a stronger assurance in determining primality.
Developed in C++, the Solovay-Strassen algorithm provides a flexible solution for assessing primality, particularly in situations where probabilistic approaches are deemed appropriate and computational speed is of utmost importance. Despite the possibility of incorrectly identifying composite numbers as prime (producing false positives), its capacity to effectively manage extensive numerical values renders it a beneficial inclusion among the array of primality assessment algorithms.
Program:
#include <bits/stdc++.h>
using namespace std;
long long modulo(long long base, long long exponent, long long mod) {
long long x = 1;
long long y = base;
while (exponent > 0) {
if (exponent % 2 == 1)
x = (x * y) % mod;
y = (y * y) % mod;
exponent = exponent / 2;
}
return x % mod;
}
int calculateJacobian(long long a, long long n) {
if (!a)
return 0;
int ans = 1;
if (a < 0) {
a = -a;
if (n % 4 == 3)
ans = -ans;
}
if (a == 1)
return ans;
while (a) {
if (a < 0) {
a = -a;
if (n % 4 == 3)
ans = -ans;
}
while (a % 2 == 0) {
a = a / 2;
if (n % 8 == 3 || n % 8 == 5)
ans = -ans;
}
swap(a, n);
if (a % 4 == 3 && n % 4 == 3)
ans = -ans;
a = a % n;
if (a > n / 2)
a = a - n;
}
if (n == 1)
return ans;
return 0;
}
bool solovoyStrassen(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++) {
long long a = rand() % (p - 1) + 1;
long long jacobian = (p + calculateJacobian(a, p)) % p;
long long mod = modulo(a, (p - 1) / 2, p);
if (!jacobian || mod != jacobian)
return false;
}
return true;
}
int main() {
int iterations = 20;
long long num1 = 5;
long long num2 = 19;
if (solovoyStrassen(num1, iterations))
printf("%d is prime\n",num1);
else
printf("%d is composite\n",num1);
if (solovoyStrassen(num2, iterations))
printf("%d is prime\n",num2);
else
printf("%d is composite\n",num2);
return 0;
}
Output:
5 is prime
19 is prime
Explanation:
The modulo operation is a useful function that efficiently computes modular exponentiation through binary exponentiation. This function evaluates (base^exponent) % mod to avoid potential overflow issues.
The calculateJacobian function determines the Jacobi symbol of a given number a with respect to n, indicating if a is a quadratic residue modulo n.
The solovoyStrassen function is responsible for executing the primality test. It requires multiple values for \( p \) and several iterations as parameters. In each iteration, a random number \( a \) is chosen within the range of 1 to \( p-1 \). Subsequently, it calculates the Jacobi symbol of \( a \) with respect to \( p \) and performs modular exponentiation of \( a \) raised to the power of \( (p-1)/2 \) modulo \( p \). If the Jacobi symbol equals zero or the modular exponentiation result differs from the Jacobi symbol, the number \( p \) is considered composite. Conversely, if this condition is met for all iterations, the number \( p \) is likely to be prime.
In the primary function, the script evaluates a pair of numerical values, num1 and num2, through the Solovay-Strassen algorithm with a set number of iterations. It then displays the primality status of each number, indicating if it is a prime or composite number.
Finally, the Solovay-Strassen algorithm utilizes the characteristics of Jacobi symbols and modular exponentiation to offer a probabilistic assessment of primality. Although it can detect non-prime numbers with a high degree of certainty, there is a possibility of incorrectly categorizing prime numbers as non-prime, rendering it suitable for scenarios where probabilistic outcomes are deemed satisfactory. Modifying the quantity of iterations impacts the precision of the test, where more iterations boost confidence in the outcomes but prolong the computational duration.
Complexity Analysis:
Time Complexity:
The primary element impacting time complexity is the quantity of loops (k) in the Solovay-Strassen examination. Each loop involves modular exponentiation, which operates at a time complexity of O(log n), with n representing the modulus.
Therefore, the total time complexity can be expressed as O(k * log n).
Space Complexity:
The space complexity is mainly determined by the storage needed for input numbers and temporary variables utilized in computations.
To store input numbers a and n, along with temporary variables such as results of exponentiation and Jacobi symbols, the space complexity remains at O(1) or constant. This means that the space needed does not grow with the size of the input.
Nevertheless, when handling input numbers with significant sizes through arbitrary-precision arithmetic, the memory requirements will vary based on how the arithmetic operations are carried out, usually falling between O(log n) and O(n) in terms of space complexity, with n denoting the quantity of digits in the input.
