# C++ Program to Implement Miller Rabin Primality Test

This C++ Program demonstrates the implementation of Miller Rabin Primality Test.

Here is source code of the C++ Program to demonstrate the implementation of Miller Rabin 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 Miller Rabin Primality Test`
3. ` */`
4. `#include <iostream>`
5. `#include <cstring>`
6. `#include <cstdlib>`
7. `#define ll long long`
8. `using namespace std;`
9. ` `
10. `/* `
11. ` * calculates (a * b) % c taking into account that a * b might overflow `
12. ` */`
13. `ll mulmod(ll a, ll b, ll mod)`
14. `{`
15. `    ll x = 0,y = a % mod;`
16. `    while (b > 0)`
17. `    {`
18. `        if (b % 2 == 1)`
19. `        {    `
20. `            x = (x + y) % mod;`
21. `        }`
22. `        y = (y * 2) % mod;`
23. `        b /= 2;`
24. `    }`
25. `    return x % mod;`
26. `}`
27. `/* `
28. ` * modular exponentiation`
29. ` */`
30. `ll modulo(ll base, ll exponent, ll mod)`
31. `{`
32. `    ll x = 1;`
33. `    ll y = base;`
34. `    while (exponent > 0)`
35. `    {`
36. `        if (exponent % 2 == 1)`
37. `            x = (x * y) % mod;`
38. `        y = (y * y) % mod;`
39. `        exponent = exponent / 2;`
40. `    }`
41. `    return x % mod;`
42. `}`
43. ` `
44. `/*`
45. ` * Miller-Rabin primality test, iteration signifies the accuracy`
46. ` */`
47. `bool Miller(ll p,int iteration)`
48. `{`
49. `    if (p < 2)`
50. `    {`
51. `        return false;`
52. `    }`
53. `    if (p != 2 && p % 2==0)`
54. `    {`
55. `        return false;`
56. `    }`
57. `    ll s = p - 1;`
58. `    while (s % 2 == 0)`
59. `    {`
60. `        s /= 2;`
61. `    }`
62. `    for (int i = 0; i < iteration; i++)`
63. `    {`
64. `        ll a = rand() % (p - 1) + 1, temp = s;`
65. `        ll mod = modulo(a, temp, p);`
66. `        while (temp != p - 1 && mod != 1 && mod != p - 1)`
67. `        {`
68. `            mod = mulmod(mod, mod, p);`
69. `            temp *= 2;`
70. `        }`
71. `        if (mod != p - 1 && temp % 2 == 0)`
72. `        {`
73. `            return false;`
74. `        }`
75. `    }`
76. `    return true;`
77. `}`
78. `//Main`
79. `int main()`
80. `{`
81. `    int iteration = 5;`
82. `    ll num;`
83. `    cout<<"Enter integer to test primality: ";`
84. `    cin>>num;`
85. `    if (Miller(num, iteration))`
86. `        cout<<num<<" is prime"<<endl;`
87. `    else`
88. `        cout<<num<<" is not prime"<<endl;`
89. `    return 0;`
90. `}`

```\$ g++ miller_rabin.cpp
\$ a.out

Enter integer to test primality: 127
127 is prime

------------------
(program exited with code: 1)

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.