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.

advertisement
advertisement

Here’s the list of Best Books in C Programming, Data Structures and Algorithms.

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.