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