-
Notifications
You must be signed in to change notification settings - Fork 0
/
test.py
144 lines (135 loc) · 6.53 KB
/
test.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
def intToBitString(a, bit = 256):
"""
Converts an integer to a binary string representation (without '0b')
:param a: The integer to convert (integer)
:param bit: The size of the representation in bit (integer)
:return: Binary string representation (String)
"""
str = bin(a)[2:]
return (bit-len(str))*"0" + str
def bitStringtoSigned(str, block_size = 32):
"""
Inserts each :block_size: step a zero in order to represent
a string of :block_size: signed integer in binary format from the
original string (loss of information)
:param str: Original string of the integer in binary format (String)
:param block_size: step for the insertion of 0 (Integer)
:return: string of block_size signed integer in binary format (String)
"""
signed_str = ""
cpt = 0
reverse_str = str[::-1]
for i in range(0, len(str), block_size-1):
cpt += 1
signed_str += reverse_str[i:i+block_size-1] + '0'
signed_str = signed_str[::-1]
signed_str = signed_str[cpt:]
return signed_str
def bitStringToIntArray(str, block_size = 32):
"""
Converts a string of an integer in binary format (:block_size:bits signed, e.g. "0111 0010")
into an array of integer of block_size-1 bit-size
:param str: Original string to convert into an array of integer (String)
:param block_size: Size of blocks (Integer)
:return: Representation of an integer array of the given string representation (Integer array)
"""
int_array = []
signed_str = bitStringtoSigned(str, block_size)
for i in range(0, len(signed_str), block_size):
tmpStr = signed_str[i:i+block_size]
int_array.append(int(tmpStr, 2))
return int_array
def convertBigIntToIntArray(big_int, bit = 256, block_size = 32):
"""
Converts a big integer into an array representation. Each array is coded
on 2^:block_size:-1 bits and the representation has a total length of :bit: bits
e.g. [0, 0, 0, 0, 0, 0, 500, 2]
:param big_int: The integer you want to convert (Integer)
:param bit: The length in bits of the representation (Integer)
:param block_size: The initial size of each integer in the final array in bits (Integer)
:return: An array representation of the integer (Integer Array)
"""
str = intToBitString(big_int, bit)
int_array = bitStringToIntArray(str)
return int_array
def convertIntArraytoBigInt(int_array, block_size = 32):
"""
Converts an integer array (of :block_size: bits, signed) into an integer
(e.g. [0, 0, 0, 0, 0, 0, 1, 0] --> 2147483648)
:param int_array: The integer array you want to convert (Integer array)
:param block_size: Size, in bits, of the length of each integer in the array (Integer)
:return: Integer representation of the array (Integer)
"""
bin_str = ""
for i in range(len(int_array)):
bin_str += intToBitString(int_array[i], block_size)[1:]
big_int = int(bin_str, 2)
return big_int
def mul(a_int_array, b_int_array, bit_a = 256, bit_b = 256, block_size = 32):
"""
Multiplies two integers in an integer array representation.
:param a_int_array: integer array representation of the first integer (Integer array)
:param b_integer_array: integer array representation of the second integer (Integer array)
:param bit_a: length in bits of the first integer (Integer)
:param bit_b: length in bits of the second integer (Integer)
:param block_size: length in bits of each integer in the array representation (Integer)
:return: result of the multiplication between the first integer and the second, in integer array representation (Integer array)
"""
a_big_int = convertIntArraytoBigInt(a_int_array, block_size)
b_big_int = convertIntArraytoBigInt(b_int_array, block_size)
res = a_big_int * b_big_int
res_array = convertBigIntToIntArray(res, bit = bit_a + bit_b, block_size = block_size)
return res_array
def add_mod(a_int_array, b_int_array, mod_int_array, block_size = 32):
"""
Modular addition between two big integers
:param a_int_array: integer array representation of the first integer (Integer array)
:param b_integer_array: integer array representation of the second integer (Integer array)
:param mod_integer_array: integer array representation of the modulues integer (Integer array)
:param block_size: length in bits of each integer in the array representation (Integer)
:return: result of the modular addition between the first integer and the second, in integer array representation (Integer array)
"""
a_big_int = convertIntArraytoBigInt(a_int_array, block_size)
b_big_int = convertIntArraytoBigInt(b_int_array, block_size)
mod_big_int = convertIntArraytoBigInt(mod_int_array, block_size)
res = (a_big_int + b_big_int) % mod_big_int
res_array = convertBigIntToIntArray(res, block_size = block_size)
return res_array
def sub_mod(a_int_array, b_int_array, mod_int_array, block_size = 32):
"""
Modular subtraction between two big integers
:param a_int_array: integer array representation of the first integer (Integer array)
:param b_integer_array: integer array representation of the second integer (Integer array)
:param mod_integer_array: integer array representation of the modulues integer (Integer array)
:param block_size: length in bits of each integer in the array representation (Integer)
:return: result of the modular subtraction between the first integer and the second, in integer array representation (Integer array)
"""
a_big_int = convertIntArraytoBigInt(a_int_array, block_size)
b_big_int = convertIntArraytoBigInt(b_int_array, block_size)
mod_big_int = convertIntArraytoBigInt(mod_int_array, block_size)
res = (a_big_int - b_big_int) % mod_big_int
res_array = convertBigIntToIntArray(res, block_size = block_size)
return res_array
if __name__ == "__main__":
max = 2147483647 # 2^31 (signed)
A = [0, max, 0, 0, 0, 0, 0, max]
B = [0, max, 0, 0, 0, 0, 0, max]
P = [max, max, 0, 0, 0, 0, 0, 0]
print()
print("A =", A)
print("B =", B)
print("P =", P)
print()
A_big_int = convertIntArraytoBigInt(A)
B_big_int = convertIntArraytoBigInt(B)
P_big_int = convertIntArraytoBigInt(P)
add_mod_ = add_mod(A, B, P)
sub_mod_ = sub_mod(A, B, P)
mul_ = mul(A, B)
print("add_mod(A, B) =", add_mod(A, B, P))
print()
print("sub_mod(A, B) =", sub_mod(A, B, P))
print()
print("mul(A, B) =", mul(A, B))
# print(convertBigIntToIntArray(2**52))
# print("A mod 2^52 =", convertBigIntToIntArray(A_big_int % (2**52)))