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 : :
|
