-
Notifications
You must be signed in to change notification settings - Fork 0
/
multiplicative_inverse_table.py
67 lines (52 loc) · 1.3 KB
/
multiplicative_inverse_table.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
## Ex: Multiplicative inverse of 1700 in Z200
from tabulate import tabulate
def multiplicative_inverse(a, b):
d = {
-1 : {
'ri' : a,
'qi' : None,
'xi' : 1,
'yi' : 0
},
0 : {
'ri' : b,
'qi' : None,
'xi' : 0,
'yi' : 1
}
}
ri = None
n = 0
while ri != 0:
n+=1
ri = d[n-2]['ri'] % d[n-1]['ri']
qi = d[n-2]['ri'] // d[n-1]['ri']
xi = d[n-2]['xi'] - qi * d[n-1]['xi']
yi = d[n-2]['yi'] - qi * d[n-1]['yi']
d[n] = {
'ri' : ri,
'qi' : qi,
'xi' : xi,
'yi' : yi,
}
#For table
list=[]
list.append([])
list[0].extend(["ri","qi","xi","yi"])
i=1
for key,value in d.items():
list.append([])
list[i] = [value[data] for data in value]
i += 1
print(tabulate(list,headers='firstrow',tablefmt='fancy_grid'))
#Multiplicative inverse
# if d[n-1]['xi'] < 0:
# print(d[n-1]['xi'])
# print(b)
def main():
multiplicative_inverse(15,26)
if __name__ == '__main__':
main()
## Test
# d = multiplicative_inverse(15,26)
# print(d)