Branch data     Line data    Source code

       1                 :            : #include "miller_rabin.h"
       2                 :            : 
       3                 :          0 : static inline cmph_uint64 int_pow(cmph_uint64 a, cmph_uint64 d, cmph_uint64 n)
       4                 :            : {
       5                 :          0 :         cmph_uint64 a_pow = a;
       6                 :          0 :         cmph_uint64 res = 1;
       7         [ #  # ]:          0 :         while(d > 0)
       8                 :            :         {
       9         [ #  # ]:          0 :                 if((d & 1) == 1)
      10                 :          0 :                         res =(((cmph_uint64)res) * a_pow) % n;
      11                 :          0 :                 a_pow = (((cmph_uint64)a_pow) * a_pow) % n;
      12                 :          0 :                 d /= 2;
      13                 :            :         };
      14                 :          0 :         return res;
      15                 :            : };
      16                 :            : 
      17                 :          0 : static inline cmph_uint8 check_witness(cmph_uint64 a_exp_d, cmph_uint64 n, cmph_uint64 s)
      18                 :            : {
      19                 :            :         cmph_uint64 i;
      20                 :          0 :         cmph_uint64 a_exp = a_exp_d;
      21   [ #  #  #  # ]:          0 :         if(a_exp == 1 || a_exp == (n - 1))
      22                 :          0 :                 return 1;
      23         [ #  # ]:          0 :         for(i = 1; i < s; i++)
      24                 :            :         {
      25                 :          0 :                 a_exp = (((cmph_uint64)a_exp) * a_exp) % n;
      26         [ #  # ]:          0 :                 if(a_exp == (n - 1))
      27                 :          0 :                         return 1;
      28                 :            :         };
      29                 :          0 :         return 0;
      30                 :            : };
      31                 :            : 
      32                 :          0 : cmph_uint8 check_primality(cmph_uint64 n)
      33                 :            : {
      34                 :            :         cmph_uint64 a, d, s, a_exp_d;
      35         [ #  # ]:          0 :         if((n % 2) == 0)
      36                 :          0 :                 return 0;
      37         [ #  # ]:          0 :         if((n % 3) == 0)
      38                 :          0 :                 return 0;
      39         [ #  # ]:          0 :         if((n % 5) == 0)
      40                 :          0 :                 return 0;
      41         [ #  # ]:          0 :         if((n % 7 ) == 0)
      42                 :          0 :                 return 0;
      43                 :            :         //we decompoe the number n - 1 into 2^s*d
      44                 :          0 :         s = 0;
      45                 :          0 :         d = n - 1;
      46                 :            :         do 
      47                 :            :         {
      48                 :          0 :                 s++;
      49                 :          0 :                 d /= 2;
      50         [ #  # ]:          0 :         }while((d % 2) == 0);
      51                 :            : 
      52                 :          0 :         a = 2;
      53                 :          0 :         a_exp_d = int_pow(a, d, n);
      54         [ #  # ]:          0 :         if(check_witness(a_exp_d, n, s) == 0)
      55                 :          0 :                 return 0;
      56                 :          0 :         a = 7;
      57                 :          0 :         a_exp_d = int_pow(a, d, n);
      58         [ #  # ]:          0 :         if(check_witness(a_exp_d, n, s) == 0)
      59                 :          0 :                 return 0;
      60                 :          0 :         a = 61;
      61                 :          0 :         a_exp_d = int_pow(a, d, n);
      62         [ #  # ]:          0 :         if(check_witness(a_exp_d, n, s) == 0)
      63                 :          0 :                 return 0;
      64                 :          0 :         return 1;
      65                 :            : };
      66                 :            : 
      67                 :            :