Python3.x-RSA_Encryption_Algorithm/Prime.py at master · w01ke/Python3.x-RSA_Encryption_Algorithm · GitHub

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
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
# coding:utf-8
importmath
importrandom


# 扩展欧几里得算法求模反元素
defex_euclid(a, b, list):
ifb==0:
list[0] =1
list[1] =0
list[2] =a
else:
ex_euclid(b, a%b, list)
temp=list[0]
list[0] =list[1]
list[1] =temp-a//b*list[1]


# 求模反元素
defmod_inverse(a, b):
list= [0, 0, 0]
ifa<b:
a, b=b, a
ex_euclid(a, b, list)
iflist[1] <0:
list[1] =a+list[1]
returnlist[1]


# 快速幂模运算，把b拆分为二进制，遍历b的二进制，当二进制位为0时不计入计算
defquick_pow_mod(a, b, c):
a=a%c
ans=1
whileb!=0:
ifb&1:
ans= (ans*a) %c
b>>=1
a= (a%c) * (a%c)
returnans


# n为要检验的大数，a < n,k = n - 1
defmiller_rabin_witness(a, n):
ifn==1:
returnFalse
ifn==2:
returnTrue
k=n-1
q=int(math.floor(math.log(k, 2)))
whileq>0:
m=k//2**q
ifk%2**q==0andm%2==1:
break
q=q-1
ifquick_pow_mod(a, n-1, n) !=1:
returnFalse
b1=quick_pow_mod(a, m, n)
foriinrange(1, q+1):
ifb1==n-1orb1==1:
returnTrue
b2=b1**2%n
b1=b2
ifb1==1:
returnTrue
returnFalse


# Miller-Rabin素性检验算法,检验8次
defprime_test_miller_rabin(p, k):
whilek>0:
a=random.randint(1, p-1)
ifnotmiller_rabin_witness(a, p):
returnFalse
k=k-1
returnTrue


# 判断 num 是否与 prime_arr 中的每一个数都互质
defprime_each(num, prime_arr):
forprimeinprime_arr:
remainder=num%prime
ifremainder==0:
returnFalse
returnTrue


# return a prime array from begin to end
defget_con_prime_array(begin, end):
array= []
foriinrange(begin, end):
flag=judge_prime(i)
ifflag:
array.append(i)
returnarray


# judge whether a number is prime
defjudge_prime(number):
temp=int(math.sqrt(number))
foriinrange(2, temp+1):
ifnumber%i==0:
returnFalse
returnTrue


# 根据 count 的值生成若干个与质数数组都互质的大数
defget_rand_prime_arr(count):
arr=get_con_prime_array(2, 100000)
prime= []
whilelen(prime) <count:
num=random.randint(pow(10, 100), pow(10, 101))
ifnum%2==0:
num=num+1
whileTrue:
ifprime_each(num, arr) andprime_test_miller_rabin(num, 8):
ifnumnotinprime:
prime.append(num)
break
num=num+2
returnprime