-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathinit_ntt.py
More file actions
68 lines (47 loc) · 8.88 KB
/
init_ntt.py
File metadata and controls
68 lines (47 loc) · 8.88 KB
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
from operator import index
import queue
q = queue.Queue()
q.put(128)
indexes = []
while not q.empty():
a = q.get()
q.put(a//2)
q.put((a+256)//2)
indexes.append(a)
if len(indexes) == 255:
break
# print(indexes)
# indexes = [128, 64, 192, 32, 160, 96, 224, 16, 144, 80, 208, 48, 176, 112, 240, 8, 136, 72, 200, 40, 168, 104, 232, 24, 152, 88, 216, 56, 184, 120, 248, 4, 132, 68, 196, 36, 164, 100, 228, 20, 148, 84, 212, 52, 180, 116, 244, 12, 140, 76, 204, 44, 172, 108, 236, 28, 156, 92, 220, 60, 188, 124, 252, 2, 130, 66, 194, 34, 162, 98, 226, 18, 146, 82, 210, 50, 178, 114, 242, 10, 138, 74, 202, 42, 170, 106, 234, 26, 154, 90, 218, 58, 186, 122, 250, 6, 134, 70, 198, 38, 166, 102, 230, 22, 150, 86, 214, 54, 182, 118, 246, 14, 142, 78, 206, 46, 174, 110, 238, 30, 158, 94, 222, 62, 190, 126, 254, 1, 129, 65, 193, 33, 161, 97, 225, 17, 145, 81, 209, 49, 177, 113, 241, 9, 137, 73, 201, 41, 169, 105, 233, 25, 153, 89, 217, 57, 185, 121, 249, 5, 133, 69, 197, 37, 165, 101, 229, 21, 149, 85, 213, 53, 181, 117, 245, 13, 141, 77, 205, 45, 173, 109, 237, 29, 157, 93, 221, 61, 189, 125, 253, 3, 131, 67, 195, 35, 163, 99, 227, 19, 147, 83, 211, 51, 179, 115, 243, 11, 139, 75, 203, 43, 171, 107, 235, 27, 155, 91, 219, 59, 187, 123, 251, 7, 135, 71, 199, 39, 167, 103, 231, 23, 151, 87, 215, 55, 183, 119, 247, 15, 143, 79, 207, 47, 175, 111, 239, 31, 159, 95, 223, 63, 191, 127, 255]
tmp = [1]
for i in range(1, 512):
tmp.append(tmp[i-1]*1753 % 8380417)
zetas = []
for i in range(255):
zetas.append(tmp[indexes[i]])
print(zetas)
# zetas = [4808194, 3765607, 3761513, 5178923, 5496691, 5234739, 5178987, 7778734, 3542485, 2682288, 2129892, 3764867, 7375178, 557458, 7159240, 5010068, 4317364, 2663378, 6705802, 4855975, 7946292, 676590, 7044481, 5152541, 1714295, 2453983, 1460718, 7737789, 4795319, 2815639, 2283733, 3602218, 3182878, 2740543, 4793971, 5269599, 2101410, 3704823, 1159875, 394148, 928749, 1095468, 4874037, 2071829, 4361428, 3241972, 2156050, 3415069, 1759347, 7562881, 4805951, 3756790, 6444618, 6663429, 4430364, 5483103, 3192354, 556856, 3870317, 2917338, 1853806, 3345963, 1858416, 3073009, 1277625, 5744944, 3852015, 4183372, 5157610, 5258977, 8106357, 2508980, 2028118, 1937570, 4564692, 2811291, 5396636, 7270901, 4158088, 1528066, 482649, 1148858, 5418153, 7814814, 169688, 2462444, 5046034, 4213992, 4892034, 1987814, 5183169, 1736313, 235407, 5130263, 3258457, 5801164, 1787943, 5989328, 6125690, 3482206, 4197502, 7080401, 6018354, 7062739, 2461387, 3035980, 621164, 3901472, 7153756, 2925816, 3374250, 1356448, 5604662, 2683270, 5601629, 4912752, 2312838, 7727142, 7921254, 348812, 8052569, 1011223, 6026202, 4561790, 6458164, 6143691, 1744507, 1753, 6444997, 5720892, 6924527, 2660408, 6600190, 8321269, 2772600, 1182243, 87208, 636927, 4415111, 4423672, 6084020, 5095502, 4663471, 8352605, 822541, 1009365, 5926272, 6400920, 1596822, 4423473, 4620952, 6695264, 4969849, 2678278, 4611469, 4829411, 635956, 8129971, 5925040, 4234153, 6607829, 2192938, 6653329, 2387513, 4768667, 8111961, 5199961, 3747250, 2296099, 1239911, 4541938, 3195676, 2642980, 1254190, 8368000, 2998219, 141835, 8291116, 2513018, 7025525, 613238, 7070156, 6161950, 7921677, 6458423, 4040196, 4908348, 2039144, 6500539, 7561656, 6201452, 6757063, 2105286, 6006015, 6346610, 586241, 7200804, 527981, 5637006, 6903432, 1994046, 2491325, 6987258, 507927, 7192532, 7655613, 6545891, 5346675, 8041997, 2647994, 3009748, 5767564, 4148469, 749577, 4357667, 3980599, 2569011, 6764887, 1723229, 1665318, 2028038, 1163598, 5011144, 3994671, 8368538, 7009900, 3020393, 3363542, 214880, 545376, 7609976, 3105558, 7277073, 508145, 7826699, 860144, 3430436, 140244, 6866265, 6195333, 3123762, 2358373, 6187330, 5365997, 6663603, 2926054, 7987710, 8077412, 3531229, 4405932, 4606686, 1900052, 7598542, 1054478, 7648983]
inv_zetas = []
for i in range(255):
inv_zetas.append(tmp[512-indexes[i]])
print(inv_zetas)
# inv_zetas = [3572223, 4618904, 4614810, 3201430, 3145678, 2883726, 3201494, 1221177, 7822959, 1005239, 4615550, 6250525, 5698129, 4837932, 601683, 6096684, 5564778, 3585098, 642628, 6919699, 5926434, 6666122, 3227876, 1335936, 7703827, 434125, 3524442, 1674615, 5717039, 4063053, 3370349, 6522001, 5034454, 6526611, 5463079, 4510100, 7823561, 5188063, 2897314, 3950053, 1716988, 1935799, 4623627, 3574466, 817536, 6621070, 4965348, 6224367, 5138445, 4018989, 6308588, 3506380, 7284949, 7451668, 7986269, 7220542, 4675594, 6279007, 3110818, 3586446, 5639874, 5197539, 4778199, 6635910, 2236726, 1922253, 3818627, 2354215, 7369194, 327848, 8031605, 459163, 653275, 6067579, 3467665, 2778788, 5697147, 2775755, 7023969, 5006167, 5454601, 1226661, 4478945, 7759253, 5344437, 5919030, 1317678, 2362063, 1300016, 4182915, 4898211, 2254727, 2391089, 6592474, 2579253, 5121960, 3250154, 8145010, 6644104, 3197248, 6392603, 3488383, 4166425, 3334383, 5917973, 8210729, 565603, 2962264, 7231559, 7897768, 6852351, 4222329, 1109516, 2983781, 5569126, 3815725, 6442847, 6352299, 5871437, 274060, 3121440, 3222807, 4197045, 4528402, 2635473, 7102792, 5307408, 731434, 7325939, 781875, 6480365, 3773731, 3974485, 4849188, 303005, 392707, 5454363, 1716814, 3014420, 2193087, 6022044, 5256655, 2185084, 1514152, 8240173, 4949981, 7520273, 553718, 7872272, 1103344, 5274859, 770441, 7835041, 8165537, 5016875, 5360024, 1370517, 11879, 4385746, 3369273, 7216819, 6352379, 6715099, 6657188, 1615530, 5811406, 4399818, 4022750, 7630840, 4231948, 2612853, 5370669, 5732423, 338420, 3033742, 1834526, 724804, 1187885, 7872490, 1393159, 5889092, 6386371, 1476985, 2743411, 7852436, 1179613, 7794176, 2033807, 2374402, 6275131, 1623354, 2178965, 818761, 1879878, 6341273, 3472069, 4340221, 1921994, 458740, 2218467, 1310261, 7767179, 1354892, 5867399, 89301, 8238582, 5382198, 12417, 7126227, 5737437, 5184741, 3838479, 7140506, 6084318, 4633167, 3180456, 268456, 3611750, 5992904, 1727088, 6187479, 1772588, 4146264, 2455377, 250446, 7744461, 3551006, 3768948, 5702139, 3410568, 1685153, 3759465, 3956944, 6783595, 1979497, 2454145, 7371052, 7557876, 27812, 3716946, 3284915, 2296397, 3956745, 3965306, 7743490, 8293209, 7198174, 5607817, 59148, 1780227, 5720009, 1455890, 2659525, 1935420, 8378664]
n = 8380417 # 2^23-2^13 + 1
m = (1<<23)//n
print(m)
a = 12332442
q = a * m >> 23
a = a - q*n
if a > n:
a -= n
print("barrett: {}, direct: {}".format(a, 12332442%n))
def zetas_to_mont(zetas):
mont_zetas = []
for z in zetas:
z = (z << 32) % n
if z > (n-1) // 2:
z -= n
mont_zetas.append(z)
return mont_zetas
mont_zetas = zetas_to_mont(zetas=zetas)
print(mont_zetas)
mont_zetas = [25847, -2608894, -518909, 237124, -777960, -876248, 466468, 1826347, 2353451, -359251, -2091905, 3119733, -2884855, 3111497, 2680103, 2725464, 1024112, -1079900, 3585928, -549488, -1119584, 2619752, -2108549, -2118186, -3859737, -1399561, -3277672, 1757237, -19422, 4010497, 280005, 2706023, 95776, 3077325, 3530437, -1661693, -3592148, -2537516, 3915439, -3861115, -3043716, 3574422, -2867647, 3539968, -300467, 2348700, -539299, -1699267, -1643818, 3505694, -3821735, 3507263, -2140649, -1600420, 3699596, 811944, 531354, 954230, 3881043, 3900724, -2556880, 2071892, -2797779, -3930395, -1528703, -3677745, -3041255, -1452451, 3475950, 2176455, -1585221, -1257611, 1939314, -4083598, -1000202, -3190144, -3157330, -3632928, 126922, 3412210, -983419, 2147896, 2715295, -2967645, -3693493, -411027, -2477047, -671102, -1228525, -22981, -1308169, -381987, 1349076, 1852771, -1430430, -3343383, 264944, 508951, 3097992, 44288, -1100098, 904516, 3958618, -3724342, -8578, 1653064, -3249728, 2389356, -210977, 759969, -1316856, 189548, -3553272, 3159746, -1851402, -2409325, -177440, 1315589, 1341330, 1285669, -1584928, -812732, -1439742, -3019102, -3881060, -3628969, 3839961, 2091667, 3407706, 2316500, 3817976, -3342478, 2244091, -2446433, -3562462, 266997, 2434439, -1235728, 3513181, -3520352, -3759364, -1197226, -3193378, 900702, 1859098, 909542, 819034, 495491, -1613174, -43260, -522500, -655327, -3122442, 2031748, 3207046, -3556995, -525098, -768622, -3595838, 342297, 286988, -2437823, 4108315, 3437287, -3342277, 1735879, 203044, 2842341, 2691481, -2590150, 1265009, 4055324, 1247620, 2486353, 1595974, -3767016, 1250494, 2635921, -3548272, -2994039, 1869119, 1903435, -1050970, -1333058, 1237275, -3318210, -1430225, -451100, 1312455, 3306115, -1962642, -1279661, 1917081, -2546312, -1374803, 1500165, 777191, 2235880, 3406031, -542412, -2831860, -1671176, -1846953, -2584293, -3724270, 594136, -3776993, -2013608, 2432395, 2454455, -164721, 1957272, 3369112, 185531, -1207385, -3183426, 162844, 1616392, 3014001, 810149, 1652634, -3694233, -1799107, -3038916, 3523897, 3866901, 269760, 2213111, -975884, 1717735, 472078, -426683, 1723600, -1803090, 1910376, -1667432, -1104333, -260646, -3833893, -2939036, -2235985, -420899, -2286327, 183443, -976891, 1612842, -3545687, -554416, 3919660, -48306, -1362209, 3937738, 1400424, -846154, 1976782]