C++ Program to Implement Solovay-Strassen Primality Test

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.

  1. /* 
  2.  * C++ Program to Implement Solovay-Strassen Primality Test
  3.  */
  4. #include <cstring>
  5. #include <iostream>
  6. #include <cstdlib>
  7. #define ll long long
  8. using namespace std;
  9. /* 
  10.  * modular exponentiation
  11.  */
  12. ll modulo(ll base, ll exponent, ll mod)
  13. {
  14.     ll x = 1;
  15.     ll y = base;
  16.     while (exponent > 0)
  17.     {
  18.         if (exponent % 2 == 1)
  19.             x = (x * y) % mod;
  20.         y = (y * y) % mod;
  21.         exponent = exponent / 2;
  22.     }
  23.     return x % mod;
  24. }
  25. /* 
  26.  * calculates Jacobian(a/n) n>0 and n is odd 
  27.  */
  28. int calculateJacobian(ll a,ll n)
  29. {
  30.     if (!a) 
  31.         return 0;
  32.     int ans = 1;
  33.     ll temp;
  34.     if (a < 0)
  35.     {
  36.         a = -a;
  37.         if (n % 4 == 3) 
  38.             ans=-ans; 
  39.     }
  40.     if (a == 1) 
  41.         return ans;
  42.     while (a)
  43.     {
  44.         if (a < 0)
  45.         {
  46.             a = -a;
  47.             if (n % 4 == 3) 
  48.                 ans = -ans;  
  49.         }
  50.         while (a % 2 == 0)
  51.         {
  52.             a = a / 2;
  53.             if (n % 8 == 3 || n % 8 == 5) 
  54.                 ans = -ans;    
  55.         }
  56.         swap(a, n);
  57.         if (a % 4 == 3 && n % 4 == 3) 
  58.             ans = -ans;
  59.         a = a % n;
  60.         if (a > n / 2) 
  61.             a = a - n; 
  62.     }
  63.     if (n == 1) 
  64.         return ans;
  65.     return 0; 
  66. }
  67.  
  68. /* 
  69.  * Solovay-Strassen Primality Test
  70.  * Iterations determine the accuracy of the test 
  71.  */
  72. bool Solovoy(ll p, int iteration)
  73. {
  74.     if (p < 2) 
  75.         return false;
  76.     if (p != 2 && p % 2 == 0) 
  77.         return false;
  78.     for (int i = 0; i < iteration; i++)
  79.     {
  80.         ll a = rand() % (p - 1) + 1;
  81.         ll jacobian = (p + calculateJacobian(a, p)) % p;
  82.         ll mod = modulo(a, (p - 1) / 2, p);
  83.         if (!jacobian || mod != jacobian)
  84.         { 
  85.             return false;
  86.         }
  87.     }
  88.     return true;
  89. }
  90. //Main
  91. int main()
  92. {
  93.     int iteration = 50;
  94.     ll num;
  95.     cout<<"Enter integr to test primality: ";
  96.     cin>>num;
  97.     if (Solovoy(num, iteration))
  98.         cout<<num<<" is prime"<<endl;
  99.     else
  100.         cout<<num<<" is not prime"<<endl;
  101.     return 0;
  102. }

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

If you find any mistake above, kindly email to [email protected]

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & discussions at Telegram SanfoundryClasses.