def binary_digits(n):
# initialize bit list
	bits = []
while n>0:
		# calculate last binary digit of current value of n
		last_bit = n%2
		# append to bit list
		bits.append(last_bit)
		# updata n
		n = n/2
return  bits
import time
start = time.time()
def mypow1(a,b,c):
	return_value = 1
	for i in range(1,b+1):
		return_value = (return_value*a) % c
	return return_value
end = time.time()
time_elapsed = int(end - start)
print time_elapsed
from binary_digits import binary_digits
import math
import time
start = time.time()
def mypow2(a, b, c):
    return_value = 1
    multiplier = a
    # temp = binary_digits(b)
    # digits = temp[::-1]
    digits = binary_digits(b)
    for digit in digits:
        if digit == 1:
            return_value = (return_value * multiplier) % c
        else:
            return_value = return_value
        multiplier = (multiplier * multiplier) % c
return return_value
# end = time.time()
# time_elapsed = int(end - start)
# print time_elapsed
#print mypow2(2,63,2017)
# -*- coding: utf-8 -*-       #设置python文件的编码为utf-8，这样就可以写入中文注释
from binary_digits import *
from mypow2 import *
from math import *
def extended_hcf(a, b):
    # initialize
    p1, q1, h1 = 1, 0, a
    p2, q2, h2 = 0, 1, b
# loop while h2 > 0
    while h2 > 0:
        r = h1 / h2
        p3, q3, h3 = p1 - r*p2, q1 - r*q2, h1 - r*h2
        p1, q1, h1, p2, q2, h2 = p2, q2, h2, p3, q3, h3
return (p1, q1, h1)
#n=pow(5,15)
#e=pow(3,11)
#print extended_hcf(n, e)
def mrf(n,a):
    s=1
    k=1
    slist=[]
    dlist=[]
    list=[]
    while k<n:
        k = 2**s
        d = divmod((n-1), k)[0]
        flag = divmod((n-1), k)[1]
        if not flag and (d % 2) == 1:
            dlist.append(d)
            slist.append(s)
        s=s+1
    for r in range(0,slist[0]):
        temp = mypow2(a,int(dlist[0])*(2**r),n)
        list.append(temp)
    return (slist,dlist,list)
def miller_rabin_test(n,a):
    flag = 0
    slist = mrf(n,a)[0]
    dlist = mrf(n,a)[1]
    list  = mrf(n,a)[2]
    Test  = []
    print slist
    print dlist
    print list
    if mypow2(a,int(dlist[0]),n)==1:
        flag = 1
        return bool(flag)
    for iter in range(0, slist[0]):
        Test.append(mypow2(a, int(dlist[0])*(2**iter), n))  ###？pow 出问题
        print Test
        if mypow2(a, int(dlist[0])*(2**iter), n) == n-1:
            flag=1
            break
    print Test
    return bool(flag)
print miller_rabin_test(2017 ,7)