miller-rabin

376 days ago by voloch

#n = m*2^r, m odd, and we test whether a^m=1 mod n or a^(m2^i) = -1 mod n, i=0,...r-1. If not then #a is a witness of compositeness of n and test returns False. If test returns True then a is liar #if n is not prime def millerrabinliar(n,a): r = 0 m = n-1 while m % 2 == 0: r += 1 m = m/2 if Mod(a,n)^m == Mod(1,n): return True for i in range(r): if Mod(a,n)^(m*2^i) == Mod(-1,n): return True return False #print millerrabinliar(561,2) def millerrabinliars(n): count = 0 for a in range(n): if gcd(a,n)==1 and millerrabinliar(n,a): print a count += 1 print "----" print n print count millerrabinliars(51) 
       
1
50
----
51
2
1
50
----
51
2
millerrabinliars(17) 
       
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
----
17
16
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
----
17
16
millerrabinliars(561) 
       
1
50
101
103
256
305
458
460
511
560
----
561
10
1
50
101
103
256
305
458
460
511
560
----
561
10
millerrabinliars(13*17) 
       
1
21
47
174
200
220
----
221
6
1
21
47
174
200
220
----
221
6
millerrabinliars(13*7) 
       
1
9
10
12
16
17
22
29
38
53
62
69
74
75
79
81
82
90
----
91
18
1
9
10
12
16
17
22
29
38
53
62
69
74
75
79
81
82
90
----
91
18
millerrabinliars(19*37) 
       
WARNING: Output truncated!  
full_output.txt



1
3
7
9
16
21
26
27
40
41
44
47
48
49
63
65
67
78
81
83
100
110
112
118
120
121
122
123
132
136
137
141
144
147
149
151
157
158
173
182
184
189
194
195
197
201
212
218
221
229
232
234
243
248
249
250
256
262
271

...

447
453
454
455
460
469
471
474
482
485
491
502
506
508
509
514
519
521
530
545
546
552
554
556
559
562
566
567
571
580
581
582
583
585
591
593
603
620
622
625
636
638
640
654
655
656
659
662
663
676
677
682
687
694
696
700
702
----
703
162
WARNING: Output truncated!  
full_output.txt



1
3
7
9
16
21
26
27
40
41
44
47
48
49
63
65
67
78
81
83
100
110
112
118
120
121
122
123
132
136
137
141
144
147
149
151
157
158
173
182
184
189
194
195
197
201
212
218
221
229
232
234
243
248
249
250
256
262
271

...

447
453
454
455
460
469
471
474
482
485
491
502
506
508
509
514
519
521
530
545
546
552
554
556
559
562
566
567
571
580
581
582
583
585
591
593
603
620
622
625
636
638
640
654
655
656
659
662
663
676
677
682
687
694
696
700
702
----
703
162
millerrabinliars(11*23) 
       
1
252
----
253
2
1
252
----
253
2
def millerrabinliarscount(n): count = 0 for a in range(n): if gcd(a,n)==1 and millerrabinliar(n,a): count += 1 print count for n in range(200,250): if n%2 == 1: print n millerrabinliarscount(n) print "---" 
       
201
2
---
203
2
---
205
6
---
207
2
---
209
2
---
211
210
---
213
2
---
215
2
---
217
18
---
219
2
---
221
6
---
223
222
---
225
2
---
227
226
---
229
228
---
231
10
---
233
232
---
235
2
---
237
2
---
239
238
---
241
240
---
243
2
---
245
2
---
247
18
---
249
2
---
201
2
---
203
2
---
205
6
---
207
2
---
209
2
---
211
210
---
213
2
---
215
2
---
217
18
---
219
2
---
221
6
---
223
222
---
225
2
---
227
226
---
229
228
---
231
10
---
233
232
---
235
2
---
237
2
---
239
238
---
241
240
---
243
2
---
245
2
---
247
18
---
249
2
---