This C++ Program demonstrates the implementation of Solovay-Strassen Primality Test.
Here is source code of the C++ Program to demonstrate the implementation of Solovay-Strassen Primality Test. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.
/*
* C++ Program to Implement Solovay-Strassen Primality Test
*/
#include <cstring>
#include <iostream>
#include <cstdlib>
#define ll long long
using namespace std;
/*
* modular exponentiation
*/
ll modulo(ll base, ll exponent, ll mod)
{
ll x = 1;
ll y = base;
while (exponent > 0)
{
if (exponent % 2 == 1)
x = (x * y) % mod;
y = (y * y) % mod;
exponent = exponent / 2;
}
return x % mod;
}
/*
* calculates Jacobian(a/n) n>0 and n is odd
*/
int calculateJacobian(ll a,ll n)
{
if (!a)
return 0;
int ans = 1;
ll temp;
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;
}
/*
* Solovay-Strassen Primality Test
* Iterations determine the accuracy of the test
*/
bool Solovoy(ll p, int iteration)
{
if (p < 2)
return false;
if (p != 2 && p % 2 == 0)
return false;
for (int i = 0; i < iteration; i++)
{
ll a = rand() % (p - 1) + 1;
ll jacobian = (p + calculateJacobian(a, p)) % p;
ll mod = modulo(a, (p - 1) / 2, p);
if (!jacobian || mod != jacobian)
{
return false;
}
}
return true;
}
//Main
int main()
{
int iteration = 50;
ll num;
cout<<"Enter integr to test primality: ";
cin>>num;
if (Solovoy(num, iteration))
cout<<num<<" is prime"<<endl;
else
cout<<num<<" is not prime"<<endl;
return 0;
}
$ g++ solovay_strassen.cpp $ a.out Enter integr to test primality: 219891801103773 219891801103773 is not prime ------------------ (program exited with code: 1) Press return to continue
Sanfoundry Global Education & Learning Series – 1000 C++ Programs.
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.
Next Steps:
- Get Free Certificate of Merit in C++ Programming
- Participate in C++ Programming Certification Contest
- Become a Top Ranker in C++ Programming
- Take C++ Programming Tests
- Chapterwise Practice Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
- Chapterwise Mock Tests: Chapter 1, 2, 3, 4, 5, 6, 7, 8, 9, 10
Related Posts:
- Apply for C++ Internship
- Buy Computer Science Books
- Apply for Information Technology Internship
- Buy Programming Books
- Practice Programming MCQs