# C Program to Implement Rabin-Miller Primality Test to Check if a Number is Prime

«
»
This C program implements the Rabin-Miller Primality Test to check if a given number is Prime. The Miller–Rabin primality test or Rabin–Miller primality test is a primality test: an algorithm which determines whether a given number is prime, similar to the Fermat primality test and the Solovay–Strassen primality test.

Here is the source code of the C program to check if a given number is prime or not. The C program is successfully compiled and run on a Linux system. The program output is also shown below.

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

```\$ gcc bubblesort.c -o bubblesort
\$ ./bubblesort

Enter integer to test Primality: 89
89 is prime```

Sanfoundry Global Education & Learning Series – 1000 C Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube 