1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
|
/* Source:
* http://en.literateprograms.org/Miller-Rabin_primality_test_%28C%29
*
*/
#include <stdio.h>
#include <stdlib.h>
#define COMPOSITE 0
#define PRIME 1
unsigned short modular_exponent_16(unsigned short base, unsigned short power,
unsigned short modulus)
{
unsigned long result = 1;
int i;
for (i = 15; i >= 0; i--)
{
result = (result*result) % modulus;
if (power & (1 << i))
result = (result*base) % modulus;
}
return (unsigned short) result; /* will not truncate since modulus is a unsigned short */
}
int miller_rabin_pass_16(unsigned short a, unsigned short n)
{
unsigned short a_to_power, s, d, i;
s = 0;
d = n - 1;
while ((d % 2) == 0)
{
d /= 2;
s++;
}
a_to_power = modular_exponent_16(a, d, n);
if (a_to_power == 1)
return PRIME;
for (i = 0; i < s-1; i++)
{
if (a_to_power == n-1)
return PRIME;
a_to_power = modular_exponent_16(a_to_power, 2, n);
}
if (a_to_power == n-1)
return PRIME;
return COMPOSITE;
}
int miller_rabin_16(unsigned short n)
{
if (n <= 1)
return COMPOSITE;
if (n == 2)
return PRIME;
if (miller_rabin_pass_16( 2, n) == PRIME &&
(n <= 7 || miller_rabin_pass_16( 7, n) == PRIME) &&
(n <= 61 || miller_rabin_pass_16(61, n) == PRIME))
return PRIME;
else
return COMPOSITE;
}
int main(int argc, char* argv[])
{
unsigned short n = (unsigned short) atoi(argv[1]);
puts(miller_rabin_16(n) == PRIME ? "PRIME" : "COMPOSITE");
return 0;
}
|
