Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
Miller-Rabin primality testing with Python.
def miller_rabin(n, k=10):
if n == 2:
return True
if not n & 1:
return False
def check(a, s, d, n):
x = pow(a, d, n)
if x == 1:
return True
for i in xrange(s - 1):
if x == n - 1:
return True
x = pow(x, 2, n)
return x == n - 1
s = 0
d = n - 1
while d % 2 == 0:
d >>= 1
s += 1
for i in xrange(k):
a = randrange(2, n - 1)
if not check(a, s, d, n):
return False
return True
# benchmark of 10000 iterations of miller_rabin(100**10-1); Which is not prime.
# 10000 calls, 11111 per second.
# 74800 function calls in 0.902 seconds
@deckar01

This comment has been minimized.

Copy link

deckar01 commented Sep 22, 2017

from random import randrange
@MaLiN2223

This comment has been minimized.

Copy link

MaLiN2223 commented Apr 14, 2018

It is important to notice that this is non deterministic version

@AaronM04

This comment has been minimized.

Copy link

AaronM04 commented Aug 17, 2018

Lines 2-3 should be:

	if n == 2 or n == 3:
		return True

This avoids the exception due to randrange(2, 2)

@phoenix2021

This comment has been minimized.

Copy link

phoenix2021 commented Mar 12, 2019

Thanks a lot

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.