-
Notifications
You must be signed in to change notification settings - Fork 0
/
main.py
144 lines (119 loc) · 5.4 KB
/
main.py
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
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
from generate_k_primes import kPrimes, k_Primes
import timeit
import matplotlib.pyplot as plt
from TD_MR import combinationTD_MR
from GCD_MR import combinationGCD_MR
from PGCD_MR import combinationPGCD_MR
from MGCD_MR import combinationMGCD_MR
from random import shuffle
def split(n, primes):
# using list comprehension
final = [primes[i * n:(i + 1) * n] for i in range((len(primes) + n - 1) // n )]
ans = []
for i in final:
k = 1
for j in i:
k = k*j
ans.append(k)
return ans
bits = [4,8,16,32, 64 ,128 ,256 ,512 ,1024]
time1 = [0,0,0,0,0,0,0,0]
time2 = [0,0,0,0,0,0,0,0]
time3 = [0,0,0,0,0,0,0,0]
time4 = [0,0,0,0,0,0,0,0]
k_primes = [9, 15, 25, 43, 74, 131,232,417]
bits2 = [32, 64, 128, 256, 512, 1024]
time = [0,0,0,0]
Primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83,
89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193,
197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313,
317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397, 401, 409, 419, 421, 431, 433, 439, 443, 449,
457, 461, 463, 467, 479, 487, 491, 499, 503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599,
601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691, 701, 709, 719, 727, 733, 739,
743, 751, 757, 761, 769, 773, 787, 797, 809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883,
887, 907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997, 1009, 1013, 1019, 1021, 1031, 1033,
1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097, 1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171,
1181, 1187, 1193, 1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297, 1301,
1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399, 1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453,
1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499, 1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583,
1597, 1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699, 1709, 1721, 1723,
1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789, 1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877,
1879, 1889, 1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999, 2003, 2011, 2017, 2027,
2029, 2039, 2053, 2063, 2069, 2081, 2083, 2087, 2089, 2099, 2111, 2113, 2129, 2131, 2137, 2141, 2143, 2153, 2161,
2179, 2203, 2207, 2213, 2221, 2237, 2239, 2243, 2251, 2267, 2269, 2273, 2281, 2287, 2293, 2297, 2309, 2311, 2333,
2339, 2341, 2347, 2351, 2357, 2371, 2377, 2381, 2383, 2389, 2393, 2399, 2411, 2417, 2423, 2437, 2441, 2447, 2459,
2467, 2473, 2477, 2503, 2521, 2531, 2539, 2543, 2549, 2551, 2557, 2579, 2591, 2593, 2609, 2617, 2621, 2633, 2647,
2657, 2659, 2663, 2671, 2677, 2683, 2687, 2689, 2693, 2699, 2707, 2711, 2713, 2719, 2729, 2731, 2741, 2749, 2753,
2767, 2777, 2789, 2791, 2797, 2801, 2803, 2819, 2833, 2837, 2843, 2851, 2857, 2861, 2879]
s = timeit.default_timer()
for i in range(0,100000):
j=0
t = timeit.default_timer()
if int((t-s)) >= 3600:
h = i
break
for n in k_primes:
primes = Primes[0:n]
pi_k = 1
for p in primes:
pi_k = pi_k * p
start = timeit.default_timer()
p = combinationTD_MR(1024, primes)
stop = timeit.default_timer()
#print(str(p)+' Time: ' + str(stop - start) )
time1[j] = time1[j] + (stop - start)
time[0] = time[0] + (stop - start)
start = timeit.default_timer()
p=combinationPGCD_MR(1024, pi_k)
stop = timeit.default_timer()
#print(str(p)+' Time: ' + str(stop - start) )
time2[j] = time2[j] + (stop - start)
time[1] = time[1] + (stop - start)
start = timeit.default_timer()
p=combinationGCD_MR(1024, primes)
stop = timeit.default_timer()
#print(str(p)+' Time: ' + str(stop - start) + '----------')
time3[j] = time3[j] + (stop - start)
time[2] = time[2] + (stop - start)
#splits = chunkify(primes, 3)
shuffle(primes)
#print(primes)
primes = split(3, primes)
start = timeit.default_timer()
combinationMGCD_MR(1024, primes)
stop = timeit.default_timer()
#print(str(n)+' Time: ' + str(stop - start) + '----------')
time4[j] = time4[j] + (stop - start)
time[3] = time[3] + (stop - start)
j = j + 1
print(i)
for i in range(0,8):
time1[i] = time1[i] / h
time2[i] = time2[i] / h
time3[i] = time3[i] / h
time4[i] = time4[i] / h
time[0] = time[0]/h
time[1] = time[1]/h
time[2] = time[2]/h
time[3] = time[3]/h
# plotting the points
plt.semilogx(k_primes,time1, label='TD_MR')
plt.semilogx(k_primes,time2, label='PGCD_MR')
plt.semilogx(k_primes,time3, label='GCD_MR')
plt.semilogx(k_primes,time4, label='MGCD_MR')
#plt.xticks([4,8,16,32, 64 ,128 ,256 ,512], (4,8,16,32, 64 ,128 ,256 ,512))
plt.xticks([9, 15, 25, 43, 74, 131, 232,417], (9, 15, 25, 43, 74, 131, 232,417))
# naming the x axis
plt.xlabel('Number of k small primes used')
# naming the y axis
plt.ylabel('Time in sec')
# giving a title to my graph
plt.title('Comparison of Running time of TD-MR, GCD-MR, PGCD-MR and MGCD-MR in generating 1024 bit prime number')
plt.legend()
# function to show the plot
plt.show()
plt.title('Comparison of Running time of TD-MR, GCD-MR, PGCD-MR and MGCD-MR in generating 1024 bit prime number using 10, 15, 25, 43, 74, 131 small primes')
plt.ylabel('Time in sec')
plt.bar([0,1,2,3], time)
plt.xticks([0,1,2,3], ('TD-MR','PGCD-MR','GCD-MR','MGCD-MR'))
plt.show()