-
Notifications
You must be signed in to change notification settings - Fork 1
/
ntt_fromR.py
91 lines (86 loc) · 5.64 KB
/
ntt_fromR.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
import ntt
import json
import time
Len=[8,16,32,64,128,256,512,1024,2048,4096,8192,16384,32768,65536,131072]
Primes=[113,115792089237316195423570985008687907853269984665640564039457584007913129637873,
115792089237316195423570985008687907853269984665640564039457584007913129636801,
115792089237316195423570985008687907853269984665640564039457584007913129636801,
115792089237316195423570985008687907853269984665640564039457584007913129635457,
115792089237316195423570985008687907853269984665640564039457584007913129607681,
115792089237316195423570985008687907853269984665640564039457584007913129607681,
1606938044258990275541962092341162602522202993782792835297281,
115792089237316195423570985008687907853269984665640564039457584007913129461761,
115792089237316195423570985008687907853269984665640564039457584007913129172993,
115792089237316195423570985008687907853269984665640564039457584007913129172993,
115792089237316195423570985008687907853269984665640564039457584007913126920193,
2037035976334486086268445688409378161051468393665936250636140449354381299763336706178908161,
2037035976334486086268445688409378161051468393665936250636140449354381299763336706177892353,
2135987035920910082395021706169552114602704522356652769947041607822219725780640550022962063736833]
G=[3,21,21,7,14,14,17,3,5,5,5,7,3,3,5]
W=[18,111631467676984398667335374000770145103933448276474029826861642673272833963082,
61564226408844285440839285786349609218130544814944526994086477601177658749278,
81935540147743287569595753552990576696362777472267730857667504939936024849618,
91170141105073899547981930648308993603853306285937430424976477296731306054334,
15708606027314919182172787703297741273850535825986009804848210667018260880261,
33237221508024116229589036146826233600929365121793224404567006713723969953911,
1434356156435145496244722803431900791032286202821828147418984,
63540838781496461220816358160078141041184179050497342724817951168620586697763,
15509384003381570599629987132205606235150174359826996727314588125855310328659,
25133251670451185231426344419964958947927332720991278511886330943333482712954,
48268024184090406204552669607243172351613601631957894966972042240077595762455,
1981954346943524807557239944865006706282615432034635354549839215713305664395133015635456087,
255453916006749145705554152189433435708896877084778108205342427278941085195694645573514698,
1112225229508435524512344497914210498809987905889897633818900952286269329043189880863555612895717]
Inv_W=[44,95491701939787783842804801121993865397654678743734107460462393771310698665647,
14352436843288370756829869005573506932522362276688548257485320352002835319209,
62892232488306180704111955726624356283223010632387729863360038676442428890163,
74617868801387775053539490766464698026550495075777446366514898818780219762498,
13868795121166213445530776440016103808108592816062879198885163286366532864581,
110859567440002879494961048339626890678895648700881402044340171696425633801612,
1203745758939828332217036953616990186340140894893888367743845,
90289433802154956706057573109440369585442036636363262555556580120598543329883,
21861149690056766619999951991678670952283712223678074390943578332757181356925,
49072410160240151341757778422903690290128844704330943680519698627182085130938,
20156023685761413501013067524878709675678100528950462782526586000840609710652,
876083208576290984072439742436788642271124879220068514346599382871681217068777930632586646,
1474657800099070887974174855844346785758665342966052193836639675246968569796074002531960855,
1525680669204487905316664361660865987506438064471172450598417789819020549260814728309162207838676]
Inv_L=[99,108555083659983933209597798445644913612440610624038028786991485007418559035506,
112173586448650064316584391727166410732855297644839296413224534507665844335651,
113982837842983129870077688367927159293062641155239930226341059257789486986226,
114887463540149662646824336688307533573166312910440247132899321632851308310180,
115339776388732929035197660848497720713218148788040405586178452820382218945151,
115565932813024562229384322928592814283244066726840484812818018414147674276416,
1605368768825143605351003144985360685918177404921676826669061,
115735550131243287125024319488664134460763505180940544232797692609471765629016,
115763819684279741274297652248676021157016744923290554136127638308692447256691,
115777954460797968348934318628681964505143364794465559087792611158302788214842,
115785021849057081886252651818684936179206674730053061563625097583107956441255,
2036973810929934862938176265628359808446455836647086582171460391357269654826210139506966666,
2037004893632210474603310977018868984748962115156511416403800420355825477294773422841921621,
2135970739633099406506331558604044839577416110609503442457036518698624890730242443329312596558002]
filepath = '~/testNTT.txt'
vec = []
with open(filepath) as fp:
line = fp.readline()
while line:
line = line.split()
a = list(map(int, line))
vec.append(a)
line = fp.readline()
L = len(vec[0])
ind=Len.index(L)
p=Primes[ind]
w=W[ind]
inv_w=Inv_W[ind]
inv_L=Inv_L[ind]
start=time.time()
Ivec1 = ntt.transform_fast(vec[0],w,p)
Ivec2 = ntt.transform_fast(vec[1],w,p)
Ivec3 = [(x * y) % p for (x, y) in zip(Ivec1, Ivec2)]
conv = ntt.inverse_transform(Ivec3, inv_w, inv_L, p)
end=time.time()
T=end-start
conv.append(T)
with open('~/outNTT.txt', 'w') as outNTT:
outNTT.writelines("%s\n" % i for i in conv)