-
Notifications
You must be signed in to change notification settings - Fork 1
/
decoding_AddChains.py
171 lines (147 loc) · 5.11 KB
/
decoding_AddChains.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
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
#!/usr/bin/env python3
import json
import click
import sys
def substring(s : str, start : str, end : str): return s[s.find(start)+len(start):s.rfind(end)]
def rewrite_line(line : str):
SPECIAL_SQR = (line[:2] == '2*')
if '(' in line and ')' in line:
string = substring(line, '(', ')')
second = line[len(string) + 2 + 2*SPECIAL_SQR:]
tmp = string
#string = ('fp_sqr(' * SPECIAL_SQR) + rewrite_line(string) + (')' * SPECIAL_SQR)
string = 'fp_exp(' + rewrite_line(string) + ',' + str(2**SPECIAL_SQR) + ')'
if ' << ' in second:
# Computing x ^ (2^e)
e = second.replace(' << ', '')
if ' + ' not in e:
e = int(e)
#string = ('fp_sqr(' * e) + string + (')' * e)
string = 'fp_exp(' + string + ',' + str(2**e) + ')'
else:
assert(' + ' in e)
if e.count(' + ') == 1:
e, y = e.split(' + ')
e = int(e)
if y == '1': y = '_1'
#string = 'fp_mul(' + ('fp_sqr(' * e) + string + (')' * e) + ',' + y + ')'
string = 'fp_mul(fp_exp(' + string + ',' + str(2**e) + ')' + ',' + y + ')'
else:
assert(e.count(' + ') == 2)
e, y, z = e.split(' + ')
e = int(e)
if y == '1': y = '_1'
if z == '1': z = '_1'
#string = 'fp_mul(fp_mul(' + ('fp_sqr(' * e) + string + (')' * e) + ',' + y + ')' + z + ')'
string = 'fp_mul(fp_mul(fp_exp(' + string + ',' + str(2**e) + ')' + ',' + y + '),' + z + ')'
else:
if (second != ''):
# Computing x * y
assert(' << ' not in second)
assert(' + ' in second)
if second.count(' + ') == 1:
y = second.replace(' + ', '')
if y == '1': y = '_1'
string = 'fp_mul(' + string + ',' + y + ')'
else:
assert(second.count(' + ') == 2)
xx, y, z = second.split(' + ')
if y == '1': y = '_1'
if z == '1': z = '_1'
string = 'fp_mul(fp_mul(' + string + ',' + y + '),' + z + ')'
return string
else:
# No more required recursion
assert( ('(' not in line) and (')' not in line) )
if SPECIAL_SQR:
assert(' << ' not in line)
if ' + ' in line:
if line.count(' + ') == 1:
x, y = line.split(' + ')
x = 'fp_sqr(' + x[2:] + ')'
if y == '1': y = '_1'
string = 'fp_mul(' + x + ',' + y + ')'
else:
assert(line.count(' + ') == 2)
x, y, z = line.split(' + ')
x = 'fp_sqr(' + x[2:] + ')'
if y == '1': y = '_1'
if z == '1': z = '_1'
string = 'fp_mul(fp_mul(' + x + ',' + y + '),' + z + ')'
else:
string = 'fp_sqr(' + line[2:] + ')'
elif ' << ' in line:
# Computing x ^ (2^e)
x, e = line.split(' << ')
if x == '1': x = '_1'
if ' + ' not in e:
e = int(e)
#string = ('fp_sqr(' * e) + x + (')' * e)
string = 'fp_exp(' + x + ',' + str(2**e) + ')'
else:
assert(' + ' in e)
if e.count(' + ') == 1:
e, y = e.split(' + ')
if y == '1': y = '_1'
e = int(e)
#string = 'fp_mul(' + ('fp_sqr(' * e) + x + (')' * e) + ',' + y + ')'
string = 'fp_mul(fp_exp(' + x + ',' + str(2**e) + '),' + y + ')'
else:
assert(e.count(' + ') == 2)
e, y, z = e.split(' + ')
if y == '1': y = '_1'
if z == '1': z = '_1'
e = int(e)
#string = 'fp_mul(fp_mul(' + ('fp_sqr(' * e) + x + (')' * e) + ',' + y + ')' + z + ')'
string = 'fp_mul(fp_mul(fp_exp(' + x + ',' + str(2**e) + '),' + y + '),'+ z + ')'
else:
# Computing x * y
assert(' << ' not in line)
assert(' + ' in line)
if line.count(' + ') == 1:
x, y = line.split(' + ')
if x == '1': x = '_1'
if y == '1': y = '_1'
string = 'fp_mul(' + x + ',' + y + ')'
else:
assert(line.count(' + ') == 2)
x, y, z = line.split(' + ')
if x == '1': x = '_1'
if y == '1': y = '_1'
if z == '1': z = '_1'
string = 'fp_mul(fp_mul(' + x + ',' + y + '),' + z + ')'
return string
def parse_file(filename : str):
defname = filename.split('/')[-1].replace('.log', '')
print("from src.fp import fp_mul, fp_sqr, fp_exp")
print("def %s(x):" % defname)
print("\t_1 = x")
dict_addchain = {}
with open(filename) as FILE:
for line in FILE:
if 'return' not in line:
key, value = line.split(" = ")
else:
key = 'return'
while key in line:
key = key + ' '
key = key[:-1]
value = line.split(key)[1]
if '2*1' in value:
value = '2*_1'
dict_addchain[key] = rewrite_line(value.replace('\n',''))
print('\t' + key + {True:' ', False:' = '}['return' in key] + dict_addchain[key])
return dict_addchain
@click.command()
@click.option('--k', default=None, type=str, help="Number of \\ell_i's.")
@click.option('--bits', default=None, type=str, help="Bitlength of the characteristic of the field.")
@click.option('--exponent', default=None, type=click.Choice(("inv", "novem", "quart", "quint", "sept", "sq", "tri")), help="sagemath or magma or raw output format).")
def main(k, bits, exponent):
original_stdout = sys.stdout # Save a reference to the original standard output
with open(f'radical/{exponent}_{bits}.py', 'w') as f:
sys.stdout = f # Change the standard output to the file we created.
formula = parse_file(f'crad_primes/p{bits}k{k}_addchains/{exponent}_{bits}.log')
sys.stdout = original_stdout # Reset the standard output to its original value
return formula
if __name__ == "__main__":
main()