Welcome, guest | Sign In | My Account | Store | Cart

Very simple implementation of Miller-Rabin Primality Test with Tkinter

Python, 49 lines
 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
from Tkinter import *
import tkMessageBox
import tkSimpleDialog
import math
import random
import string

#-----------------------------------------------
def millerTest(a, i, n):
	if i == 0:
		return 1
	x = millerTest(a, i / 2, n)
	if x == 0:
		return 0
	y = (x * x) % n
	if ((y == 1) and (x != 1) and (x != (n - 1))):
		return 0
	if (i % 2) != 0:
		y = (a * y) % n
	return y

#-----------------------------------------------
class MainApp:

	def __init__(self):
		self.root = Tk()
		self.initGui()
		self.root.title("Miller-Rabin")
		self.root.resizable(0, 0)
		self.root.update()
		self.root.mainloop()
		
	def initGui(self):
		body = Frame(self.root)
		body.pack(padx = 5, pady = 5)
		Label(body , text = "Number:").grid(row = 0, sticky = W)
		self.ent1 = Entry(body)
		self.ent1.grid(row = 0, column = 1)
		Button(body, text = "Check Primality", command = self.checkPrimality).grid(row = 1, sticky = E, column = 1, pady = 5)
	
	def checkPrimality(self):
		n = string.atoi(self.ent1.get())
		if millerTest(random.randint(2, n - 2), n - 1, n) == 1:
			tkMessageBox.showinfo(message = "%d is prime" % n)
		else:
			tkMessageBox.showinfo(message = "%d is NOT prime" % n)
	
#-----------------------------------------------
if __name__ == "__main__" : MainApp()
   

Very simple Gui + simple test

3 comments

deep zorro 14 years, 7 months ago  # | flag

Very effective! but I don't understand the function millerTest, could u pls explain it for a while?

greg p 14 years, 4 months ago  # | flag

Now there's a Web GUI too. I put your code into a web based GUI so you can now check primality from any computer :-)

http://www.utilitymill.com/utility/Miller_Rabin_Primality_Test

a 11 years, 7 months ago  # | flag

string.atoi() is deprecated. you should use int() instead