# miller-rabin

## 430 days ago by voloch

#n-1 = 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(100001)
 1 10 100 1000 10000 26273 26364 27263 27274 27373 35455 36264 36363 36374 37273 37364 44455 44546 45355 45445 45454 45456 45465 45555 46455 53546 54446 54536 54545 54547 54556 54646 55455 55546 62637 62728 63627 63638 63737 64546 72628 72727 72738 73637 73728 90001 99001 99901 99991 100000 ---- 100001 50 1 10 100 1000 10000 26273 26364 27263 27274 27373 35455 36264 36363 36374 37273 37364 44455 44546 45355 45445 45454 45456 45465 45555 46455 53546 54446 54536 54545 54547 54556 54646 55455 55546 62637 62728 63627 63638 63737 64546 72628 72727 72738 73637 73728 90001 99001 99901 99991 100000 ---- 100001 50
for n in range(21,30): print Mod(10^n,100001)
 10 100 1000 10000 100000 99991 99901 99001 90001 10 100 1000 10000 100000 99991 99901 99001 90001
socat = 143319364394905942617148968085785991039146683740268996579566827015580969124702493833109074343879894586653465192222251909074832038151585448034731101690454685781999248641772509287801359980318348021809541131200479989220793925941518568143721972993251823166164933334796625008174851430377966394594186901123322297453 for n in range(2,300): if millerrabinliar(socat,n): print n if n == 199: print "done"
 done done
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 ---