-
Notifications
You must be signed in to change notification settings - Fork 1
/
ntt.c
159 lines (141 loc) · 28.6 KB
/
ntt.c
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
/*
* Implementors: EagleSign Team
* This implementation is highly inspired from Dilithium and
* Falcon Signatures' implementations
*/
#include <stdint.h>
#include <stdio.h>
#include "params.h"
#include "reduce.h"
#include "ntt.h"
/* ===================================================================== */
/*
* GMb = Table for NTT, binary case:
* GMb[x] = R*(g^rev(x)) mod Q
* where g is a 1-th primitive root of 1 modulo Q
* and rev() is the bit-reversal function over LOG_N bits.
*********************************************************
* iGMb = Table for inverse NTT, binary case:
* iGMb[x] = R*((1/g)^rev(x)) mod Q
*********************************************************/
#if N == 512
// const S_Q_SIZE GMb[N] = {-3593, -2336, 2361, 3040, 806, 1734, -1575, 900, 2085, -3386, 338, -3485, 971, 2737, -1, -2194, 3361, 274, 2781, 2800, -2896, -1637, -440, 2446, 1314, 2541, -1710, -3412, 1905, 1106, 1414, -808, 192, -1207, -3196, 729, -2773, -610, 873, 2793, 3014, -625, 76, -2238, -2645, 3706, -3818, 3279, -2653, 1516, 2716, -1552, 3712, 2268, 2219, -1268, 1159, 435, 70, -40, -617, -1842, -1091, 2818, -1964, 25, -1232, 704, 1642, 159, -769, 2634, -2347, -3048, 2423, 810, 2893, 2736, 970, 543, -3426, 3055, -1539, 3074, -2126, -2077, -3336, 809, 466, 831, -396, -871, 3271, 2520, 3319, 298, -1896, 3278, -3004, -478, 1460, 263, -1900, 2183, 2881, -549, 3090, -2863, 196, -112, 1218, -696, 275, -3449, 63, -36, 1749, -3194, -1750, 1000, -2804, 505, 1229, 395, -628, -2933, -1708, 976, -1442, 824, -1280, 2926, 2504, 1861, -1996, -1054, 3447, -3067, -2171, -954, -3578, -150, -289, 3457, 3523, 2376, -2796, 2695, 285, 3129, 3417, 242, 3377, -3027, -2606, -2900, -2487, -2968, 1553, -3082, 1721, -3178, -1924, 3294, -2573, 373, -1176, 672, 3093, 3719, -1079, -1578, 3695, 3375, 2662, 2868, 1383, 307, 1462, -3030, -2572, 2567, 3768, 2236, -3013, 2819, -2813, 3802, -1650, -2349, -378, 216, 798, -456, -2722, 3750, -1684, -135, 508, 807, -2355, 2443, 1276, 3660, -1152, -439, 3814, 3307, 735, -420, 727, -2610, 66, -1135, 3702, 3371, -3584, 2048, 771, 1754, 556, -1415, -934, 1631, -2593, 2579, -203, 116, -515, -803, -3749, 1045, 3061, 2640, 2014, 2141, 2877, -1644, -1324, -1438, 2665, 1769, 2845, -2723, -1485, -1346, 1196, -2878, 3830, 6, 1855, -1060, 2852, -2727, -2028, -2133, 367, -1307, 1732, -2087, -1660, -1246, -3732, -62, -2960, -3795, -1935, 2203, 1145, 443, -17, 1107, 3370, -3023, 1191, 1514, -3146, 2895, 201, 3177, -705, -2889, 1654, 3444, 1661, 3440, 995, 1626, 3264, 2524, -565, -2969, -1055, -2689, -521, 1395, -2529, -2944, 1292, 359, 1121, 1554, -3458, 1976, 985, 2729, 86, -3341, 1656, 151, -682, 1487, -3340, -286, 1190, -680, -2808, -590, -3185, 1820, -2664, 425, 2099, -3394, -2810, 2703, 2289, -1308, -1494, 1951, 2786, -1592, 3095, 426, 1128, 1550, 3206, -1832, -3120, -1509, 2263, 3096, -2945, -1609, 241, -1235, 949, 555, 1840, -3246, 2656, -2615, -1508, 1959, 2699, -445, 1777, -3210, -1576, -1294, 2891, -1652, -1237, -2585, 3332, -1904, -2337, 3530, -3006, 2815, 1071, -612, -991, -531, 974, 1638, -1582, 904, -2150, -966, -2995, -3775, 1688, 1230, -1471, -1354, 1283, 3656, -3518, 913, -3208, -2556, -2849, 1628, 1498, -856, 622, -2550, 2768, -2679, -1557, 1987, -1446, -271, -2836, -574, -3359, -3567, 3642, 2308, 1784, -3214, 3807, 3311, 3358, 1373, -1467, -259, -1984, 2231, 2345, -1340, 3051, 3743, -1186, 1775, -2981, -3783, 1367, 3608, -832, 2670, 468, -2462, 1811, 2257, 2362, -2447, 2608, -393, 2546, 1837, -1735, 3186, 2674, -1528, 1255, 3672, -1796, -71, -188, 2302, 2096, -2295, 955, -1643, -1630, 3126, -1351, 772, 3459, 218, 3390, 2452, -2867, 541, -3003, 1716, 1122, 3748, 1486, 3540, 520, -3589, -2255, -906, 1771, -1012, -516, -2997, 2005, -2243, -3451, 1972, -1074, 1711, -2285, 2403, -1730, -1206, 3514, -2008, 2823, 2776, 535, -1403, -781, -651, 2279, -205, -2202, 161, -2711, -2840, 3662, 102, 811, -2658, 2398, -273, -3752, 2144};
// const S_Q_SIZE iGMb[N] = {-3593, 527, 1629, 2910, 836, -1463, 2430, -412, 1922, 477, 221, -2307, 3249, 75, 2112, -3696, 1366, 1450, 2427, -2327, -848, 1484, 1541, 3064, 770, 2493, -2613, -1188, 894, 2276, -121, 2132, -11, -1901, 3000, 2431, 3718, -2666, -108, 189, -1963, 1515, 1185, 3687, 2928, 2557, -1118, -1884, 2841, 789, -1132, 1981, -133, 2153, -1434, -1331, -3448, -1647, -908, 1589, -2088, 3654, -336, 588, 2989, 530, 1099, -3, 3610, -2477, -2774, 1014, -778, -2479, 2700, 2956, 1810, 673, 1439, -598, 1709, 2770, -343, -1320, -1567, 822, 719, 662, 3325, -58, -2555, 2551, -2424, -3439, 3318, -1966, 3793, -877, -3804, -1024, 693, -3133, 3025, 467, -1843, 1305, -120, 210, 773, -3273, 2155, -1851, 2143, -1830, 698, 2619, -2320, -3621, 2187, -1907, 3266, -1875, 967, 228, 2156, -3773, 3437, -254, 3549, -450, 2690, -867, -1326, -1520, -2862, 1168, -2093, -2098, -3162, 1693, 782, 2472, 1097, -3840, 2317, 1706, 726, 2570, 316, -553, 404, -707, 800, -1400, -1019, -137, -1565, -3022, -1223, 220, -2206, 20, -973, 3623, 571, 921, -1409, -3295, -2638, 776, 3725, -758, 648, -1134, 634, 2731, -2834, 1119, 2016, -3528, -2233, -1853, 2201, 1909, -889, 3476, 2947, -3237, 923, 305, 2444, 3404, -3179, 3643, -953, 3588, -838, -2374, -488, 854, 1087, 18, -3180, -2116, 1282, 1597, -500, 875, -818, -2409, 3135, -3566, -32, 56, 348, -609, 2058, 239, -1258, -1639, 3367, 3709, 2749, 950, 3043, -3405, 2432, 3425, 720, -1260, -149, 2181, -219, -1537, -2419, 2313, -2788, -2802, 3436, 1668, 2426, -405, 2421, 1524, 1879, -1368, 3569, -485, 3493, -352, 3299, 3828, 2240, 3761, -1317, -3456, -1115, 31, -356, 623, 501, -2797, -2568, -3187, 2824, 2739, 13, -1943, -2068, 3619, 3287, -3832, 984, -1722, -3020, -2396, -2309, -1720, -813, 3343, -1762, -757, -1961, -2329, -3562, 2393, 2252, 3740, 903, 340, -1179, 143, 2026, 295, -910, -2248, 1240, -2170, 1877, 2476, 3335, 3765, 3097, 341, -2092, 3661, 3548, 1472, 444, -777, -988, 1729, 249, -2356, -3668, -1262, 329, -2496, 3143, -3580, -276, 483, -839, -452, 1116, -1953, -615, -844, 3117, 306, -293, 2433, -1249, -3575, -819, -487, 1456, -2548, -472, 826, -544, 952, -1765, -2672, -3419, -3618, 1657, 2861, 3472, 1605, 647, 788, -2036, 3563, 2939, -3223, -3122, 1623, -2533, -1328, -3723, -3086, -2718, 916, -1310, -1548, -3036, -2368, 2837, 796, 2752, 2865, 1219, -213, -775, -564, -2067, 1697, 2316, 3628, -325, 2489, 654, 2696, -2954, 1329, 3321, -51, -78, -3704, -1072, 1876, 2136, -3738, -186, -3515, 46, 3760, 1420, -2485, -1671, 1004, 1850, 603, -3596, -1388, -3139, 3573, 2758, -986, 2651, -2719, -2803, 2985, 2639, -2698, 3033, 453, -3220, -2046, -3581, 506, -2342, 258, -607, -858, -2040, 3570, -2221, -1874, -1770, -743, -1974, -386, -3496, -1563, -1035, -109, -1226, -1695, 1755, -1151, 1077, -3805, -1753, -2693, -3019, 3363, -187, -1593, -2767, 2922, 1758, 764, -1836, 3213, -2647, 2712, -2898, 1231, 3690, -2617, -3644, -1304, 2211, -1949, 3799, 2953, -2261, -1804, -1335, 416, 2832, 2725, -74, -3711, 2909, 670, 1969, 2315, 179, 1607, 2854, -1154, 946, 2185, 3154, -1679, -2272, -3705, 1665, 2847, -164, 287, -2057, -2161, 1950, 428, 3757, -814, 1466, 1275, -2501, -1384, -1150, -1828, 2905, 677, -3031, 3384, 1278, 1604};
const S_Q_SIZE GMb[N] = {-3593, 3593, 3777, -3777, -3182, 3182, 3625, -3625, -3696, 3696, -1100, 1100, 2456, -2456, 2194, -2194, 121, -121, -2250, 2250, 834, -834, -2495, 2495, -2319, 2319, 2876, -2876, -1701, 1701, 1414, -1414, 2816, -2816, -2088, 2088, -2237, 2237, 1986, -1986, -1599, 1599, 1993, -1993, 3706, -3706, -2006, 2006, -1525, 1525, -2557, 2557, 1296, -1296, 1483, -1483, -2830, 2830, 3364, -3364, 617, -617, 1921, -1921, -3689, 3689, -1738, 1738, 3266, -3266, -3600, 3600, 810, -810, 1887, -1887, -638, 638, -7, 7, -438, 438, -679, 679, -1305, 1305, -1760, 1760, 396, -396, -3174, 3174, -3555, 3555, -1881, 1881, 3772, -3772, -2535, 2535, -2440, 2440, -2555, 2555, 1535, -1535, -549, 549, 3153, -3153, 2310, -2310, -1399, 1399, 1321, -1321, 514, -514, -2956, 2956, -103, 103, 2804, -2804, -2043, 2043, -1431, 1431, -1054, 1054, 1698, -1698, -3456, 3456, 1166, -1166, 2426, -2426, 3831, -3831, 915, -915, -2, 2, -3417, 3417, -194, 194, 2919, -2919, 2789, -2789, 3405, -3405, 2385, -2385, -2113, 2113, -2732, 2732, 2175, -2175, 373, -373, 3692, -3692, -730, 730, -1756, 1756, 3135, -3135, -2391, 2391, 660, -660, -1497, 1497, 2572, -2572, -3145, 3145, 1350, -1350, -2224, 2224, -3588, 3588, -1681, 1681, 2883, -2883, -1390, 1390, 1598, -1598, 3750, -3750, 2762, -2762, 2835, -2835, 2764, -2764, -2233, 2233, 3816, -3816, -1533, 1533, 1464, -1464, -727, 727, 1521, -1521, 1386, -1386, -3428, 3428, -921, 921, -2743, 2743, -2160, 2160, 2649, -2649, -859, 859, 2579, -2579, 1532, -1532, 1919, -1919, -486, 486, 404, -404, -1056, 1056, 783, -783, 1799, -1799, -2665, 2665, 3480, -3480, 2133, -2133, -3310, 3310, -1168, 1168, -17, 17, 3744, -3744, 2422, -2422, 2001, -2001, 1278, -1278, 929, -929, -1348, 1348, -2230, 2230, -179, 179, -1242, 1242, -2059, 2059, -1070, 1070, 2161, -2161, 1649, -1649, 2072, -2072, 3177, -3177, -2071, 2071, 1121, -1121, -436, 436, 236, -236, 715, -715, 670, -670, -658, 658, -1476, 1476, -2378, 2378, 2767, -2767, 3542, -3542, -226, 226, 1203, -1203, 1181, -1181, -151, 151, -3794, 3794, 1712, -1712, -222, 222, 2786, -2786, -451, 451, -3547, 3547, 1779, -1779, -1151, 1151, -434, 434, 3568, -3568, -3693, 3693, 3581, -3581, -1586, 1586, 1509, -1509, 2918, -2918, 2339, -2339, -1407, 1407, 3434, -3434, -3550, 3550, 2340, -2340, 2891, -2891, 2998, -2998, -3314, 3314, 3461, -3461, -2719, 2719, -2247, 2247, -2589, 2589, 1144, -1144, 1072, -1072, 1295, -1295, -2815, 2815, -3770, 3770, 3450, -3450, 3781, -3781, -2258, 2258, 796, -796, 3163, -3163, -3208, 3208, -589, 589, 2963, -2963, -124, 124, 3214, -3214, 3334, -3334, -3366, 3366, -3745, 3745, 3723, -3723, 1931, -1931, -429, 429, -402, 402, -3408, 3408, 83, -83, -1526, 1526, 826, -826, -1338, 1338, 2345, -2345, -2303, 2303, 2515, -2515, -642, 642, -1837, 1837, -2965, 2965, -791, 791, 370, -370, 293, -293, 3312, -3312, 2083, -2083, -1689, 1689, -777, 777, 2070, -2070, 2262, -2262, -893, 893, 2386, -2386, -188, 188, -1519, 1519, -2874, 2874, -1404, 1404, 1012, -1012, 2130, -2130, 1441, -1441, 2532, -2532, -3335, 3335, -1084, 1084, -3343, 3343, 2937, -2937, 509, -509, -1403, 1403, 2812, -2812, 3763, -3763, 592, -592, 2005, -2005, 3657, -3657, 2460, -2460, -3677, 3677, 3752, -3752, 692, -692, 1669, -1669, 2167, -2167, -3287, 3287};
const S_Q_SIZE iGMb[N] = {-3593, 3593, -3777, 3777, -3625, 3625, 3182, -3182, -2194, 2194, -2456, 2456, 1100, -1100, 3696, -3696, -1414, 1414, 1701, -1701, -2876, 2876, 2319, -2319, 2495, -2495, -834, 834, 2250, -2250, -121, 121, -1921, 1921, -617, 617, -3364, 3364, 2830, -2830, -1483, 1483, -1296, 1296, 2557, -2557, 1525, -1525, 2006, -2006, -3706, 3706, -1993, 1993, 1599, -1599, -1986, 1986, 2237, -2237, 2088, -2088, -2816, 2816, 1431, -1431, 2043, -2043, -2804, 2804, 103, -103, 2956, -2956, -514, 514, -1321, 1321, 1399, -1399, -2310, 2310, -3153, 3153, 549, -549, -1535, 1535, 2555, -2555, 2440, -2440, 2535, -2535, -3772, 3772, 1881, -1881, 3555, -3555, 3174, -3174, -396, 396, 1760, -1760, 1305, -1305, 679, -679, 438, -438, 7, -7, 638, -638, -1887, 1887, -810, 810, 3600, -3600, -3266, 3266, 1738, -1738, 3689, -3689, 1168, -1168, 3310, -3310, -2133, 2133, -3480, 3480, 2665, -2665, -1799, 1799, -783, 783, 1056, -1056, -404, 404, 486, -486, -1919, 1919, -1532, 1532, -2579, 2579, 859, -859, -2649, 2649, 2160, -2160, 2743, -2743, 921, -921, 3428, -3428, -1386, 1386, -1521, 1521, 727, -727, -1464, 1464, 1533, -1533, -3816, 3816, 2233, -2233, -2764, 2764, -2835, 2835, -2762, 2762, -3750, 3750, -1598, 1598, 1390, -1390, -2883, 2883, 1681, -1681, 3588, -3588, 2224, -2224, -1350, 1350, 3145, -3145, -2572, 2572, 1497, -1497, -660, 660, 2391, -2391, -3135, 3135, 1756, -1756, 730, -730, -3692, 3692, -373, 373, -2175, 2175, 2732, -2732, 2113, -2113, -2385, 2385, -3405, 3405, -2789, 2789, -2919, 2919, 194, -194, 3417, -3417, 2, -2, -915, 915, -3831, 3831, -2426, 2426, -1166, 1166, 3456, -3456, -1698, 1698, 1054, -1054, 3287, -3287, -2167, 2167, -1669, 1669, -692, 692, -3752, 3752, 3677, -3677, -2460, 2460, -3657, 3657, -2005, 2005, -592, 592, -3763, 3763, -2812, 2812, 1403, -1403, -509, 509, -2937, 2937, 3343, -3343, 1084, -1084, 3335, -3335, -2532, 2532, -1441, 1441, -2130, 2130, -1012, 1012, 1404, -1404, 2874, -2874, 1519, -1519, 188, -188, -2386, 2386, 893, -893, -2262, 2262, -2070, 2070, 777, -777, 1689, -1689, -2083, 2083, -3312, 3312, -293, 293, -370, 370, 791, -791, 2965, -2965, 1837, -1837, 642, -642, -2515, 2515, 2303, -2303, -2345, 2345, 1338, -1338, -826, 826, 1526, -1526, -83, 83, 3408, -3408, 402, -402, 429, -429, -1931, 1931, -3723, 3723, 3745, -3745, 3366, -3366, -3334, 3334, -3214, 3214, 124, -124, -2963, 2963, 589, -589, 3208, -3208, -3163, 3163, -796, 796, 2258, -2258, -3781, 3781, -3450, 3450, 3770, -3770, 2815, -2815, -1295, 1295, -1072, 1072, -1144, 1144, 2589, -2589, 2247, -2247, 2719, -2719, -3461, 3461, 3314, -3314, -2998, 2998, -2891, 2891, -2340, 2340, 3550, -3550, -3434, 3434, 1407, -1407, -2339, 2339, -2918, 2918, -1509, 1509, 1586, -1586, -3581, 3581, 3693, -3693, -3568, 3568, 434, -434, 1151, -1151, -1779, 1779, 3547, -3547, 451, -451, -2786, 2786, 222, -222, -1712, 1712, 3794, -3794, 151, -151, -1181, 1181, -1203, 1203, 226, -226, -3542, 3542, -2767, 2767, 2378, -2378, 1476, -1476, 658, -658, -670, 670, -715, 715, -236, 236, 436, -436, -1121, 1121, 2071, -2071, -3177, 3177, -2072, 2072, -1649, 1649, -2161, 2161, 1070, -1070, 2059, -2059, 1242, -1242, 179, -179, 2230, -2230, 1348, -1348, -929, 929, -1278, 1278, -2001, 2001, -2422, 2422, -3744, 3744, 17, -17};
#elif N == 1024
const S_Q_SIZE GMb[N] = {4091, -4401, -1229, -1081, -5329, 4342, -6014, -2530, 1591, -5890, -2812, 5266, 586, 5825, -4751, -2579, 1134, -5882, 1711, 965, -5190, -4615, 3743, -5847, -1875, -4189, 1885, 1688, 1364, -1960, -2125, -3109, -79, -6049, 997, 117, 4783, 4407, 1549, -5217, 2829, -5831, 4431, -3412, -5145, 2564, 5664, 4042, -100, 432, -1538, 1237, -4679, 1534, 3983, -4426, 2181, -5981, -3569, -5719, 4843, 1690, 14, 3872, 5569, -2921, -126, 2019, -4746, 2315, 4673, -4949, 1553, 1156, -3888, -900, 1020, 2967, -1517, -5244, 3316, -1053, 5285, -711, -1652, -2203, -2796, -6109, -3012, 6130, 3323, 883, -1820, 489, 1502, 2851, -1228, -2560, 2742, -48, 4970, -1808, -2211, 1195, 730, 1762, 3854, 2030, 5892, -1367, -3269, 5274, -3110, 3604, 3782, -2083, 3180, 3467, 4668, 2446, -4676, -2903, 834, -4586, -5453, 3403, 5351, -13, 3580, 1739, -1469, -2502, -2080, 4070, -39, -3764, -1888, 2749, -4951, -1715, 6040, 943, -2959, 1477, -5424, -2621, 3585, -5656, -144, 4063, 3684, -4609, -4101, -5387, 3533, -2482, 6090, 727, -2190, -5286, -5344, 1949, -2558, -1730, 6057, 378, -4418, -3526, -3388, -3060, -3443, 4551, -2700, -625, -4659, -3468, 5680, 4956, -6038, -3901, -2133, -3566, 2341, 3159, 1467, 5460, -3736, -4506, 2649, 2320, -3253, -6101, 737, 3698, 4699, 5753, -3243, 3687, 16, 914, 5186, -1758, 4552, 1964, 3509, -3853, -4773, 5381, -1556, 3281, -5252, 1060, 2895, -5133, -3402, 5357, -5880, -4092, 2962, -5914, 5064, -5655, 5625, 278, 932, -2060, -3362, -4647, 351, -2991, 237, 5858, -4597, 3146, -163, -4703, 2053, -1004, 3802, 5204, 4602, 1748, -989, 340, 3711, 4614, 300, -1296, 5070, -2240, -673, -42, -4868, -1582, 5746, 5654, 3835, 5553, 1224, -3813, -3052, 3845, 250, -1080, 4225, -5963, -2609, -35, 4136, 2778, 692, -3481, -5879, -5571, -2184, -1871, 3759, -4933, -928, -3856, -5852, 3652, -5947, -3311, 5391, 2272, -5813, -4873, -3871, -1465, -303, 5733, 876, -5259, 2167, 2436, 3442, -3072, -4083, 4858, 5964, 2746, -5111, 1434, -4900, -3410, -1628, -832, 4220, 1432, -1457, 4328, -3732, 1867, -2835, 2416, 3816, -3213, 686, 5393, 2523, 4339, 6115, 619, 937, 2834, -4514, 3279, 2363, -4801, 6112, 5056, 824, -2085, -599, 1113, 2727, -2441, 896, 2028, 5075, 2654, -1825, -4405, -120, 5434, 3070, -5889, -3157, -617, -136, 4520, 1273, -2550, -821, -2352, -2250, -2569, 2262, -2890, -1097, 315, 4511, 1158, 6061, -5538, -424, 357, -4922, 4550, 983, -3755, -3937, -2163, -4759, -3036, 4367, 5221, 3999, -3512, 3161, -5299, 4130, -637, 3374, -812, 1753, 292, -3608, 2806, -1911, -101, 5800, -478, 3181, 1988, 1024, -2949, 2477, -1361, 4582, -5539, 3619, 5503, 5233, 2463, -3819, -4639, -4325, -5894, 1071, 1272, 3474, -1244, 3291, -945, -3787, -2811, -2452, 1253, 1857, -6056, 4720, -728, 6034, -2472, 3339, 1797, 2879, -6047, 5200, 2114, -4327, -2936, -926, 5475, 6084, -2688, 4108, -4966, -1851, -2818, 1271, 408, -5378, 3079, 360, -4013, -754, -3133, -3240, -750, 850, -3672, 784, -4370, -3955, -119, 1846, -2076, -105, -4462, -386, 5600, -2510, 1012, 721, 2784, -5613, -5737, 5348, 4424, -5473, -3884, -2330, 5150, 2356, 5552, 5267, 1333, -3488, -2628, -4981, 5788, 4910, 909, -676, 4395, -4051, -5603, 4302, 3044, 2285, -40, 1963, -3073, 4296, -371, 695, 4371, -2496, 4884, 2411, -2059, 2650, 841, 3890, -2058, -5041, -3784, -1093, -5601, 4059, 6060, 3686, 4722, -436, 5816, -5231, -5421, -1152, -4363, 4894, -5, 4102, 3908, 3610, -5764, -4351, -4307, -312, -5534, 537, 4562, 1623, -4062, -836, -4745, 906, -473, -2741, -1431, -2586, 2815, -553, -5476, -5310, 819, -3386, -6018, -1446, 348, -4775, -3950, -5850, 694, 852, 5659, 2781, 3716, -700, 3024, 1523, -3630, 4114, -1551, 3303, 5885, 2978, -5000, -405, -3166, -2966, -459, 98, 2526, 2116, 4131, -882, 1844, 3645, 3916, -4156, 2224, -1418, -4197, -2638, 5989, -5149, -3809, 1670, 159, -1366, 4918, 128, -4977, 725, -3132, 5006, -5896, 3494, 6043, -1317, -6108, -451, 3423, -1775, -4621, 3693, -5631, -5384, -336, -2077, -367, -3188, -3924, 5110, 45, 2400, 1921, 4377, 2720, 1695, 51, 2808, 650, 1896, -2292, -2318, -309, -4191, 4833, 4135, 4257, 5838, 4765, -1304, -757, 590, -91, 482, -116, 2006, -5225, -2271, 3912, -273, -1770, -927, -5335, 2210, 284, 5413, -5688, 3865, -1950, -1101, -6058, 517, -2725, -1008, 3863, 1210, 4604, -4129, -842, 153, -5085, 5763, 5089, -3041, -135, -541, 1354, -5617, 179, 5532, 2646, 5941, -104, 862, 3158, 477, -5010, 5678, -4375, 4254, 302, 2893, -2175, -5399, -2729, -2642, -384, 4098, -2465, -2020, 1353, -1574, 5325, -6035, 3951, 1807, -5840, 5159, 1308, -3974, 3404, 1877, 1231, 112, -5891, -565, -17, -5003, 1459, -15, -2393, 3456, 800, 1397, -1611, 103, -4869, -4313, 936, 764, 632, -4293, -4066, -3844, -4531, -1419, -2718, 2508, 1946, -5765, -2131, 1044, 4338, 2457, 3641, 1659, 4139, 4688, -2556, -1141, 3946, 2082, 5261, 2036, -439, -4653, -53, 5366, 2380, 1399, -4569, 2100, 3217, -1377, -3391, -4711, -294, 2791, 1215, 3355, 2711, 2267, 2004, -3721, -2113, 3214, 2337, 1750, 4729, 4997, -4874, -5974, -245, 4374, -5132, 4844, 211, -4286, -2130, -2999, -808, 1735, 2336, 5793, -2414, -4097, 986, -4762, 1401, 870, 3615, -3824, 2756, -2519, 2034, -2121, 3264, 6132, 54, 2880, 4763, -484, 3074, -4003, -2861, 4881, -5356, 1090, -2251, 2567, 708, 893, -5824, 4962, -2265, 2090, 5718, -1546, 780, 4733, 4623, 2134, 2087, 4802, 884, 5372, 5795, 5938, 4333, -5730, -4740, 5269, -1625, 4252, 3260, 5917, -1475, 5768, -2306, -4193, -4498, -5489, -4798, -6017, 1907, -1342, -6000, -486, 6032, -840, 1171, -3088, -4356, 2479, -4319, -952, -5227, -3378, -5561, -5747, -4175, -3461, -5694, 3545, 4348, 4610, 2205, -5290, -4183, 5560, -1899, -2968, 2499, 2413, -5017, -5408, -1707, -2981, -2852, 3554, 3326, 5991, -320, 3415, -6, -2451, -226, 4332, -4459, -960, -5684, -18, 2044, -678, -4936, -1088, -707, 3733, -3346, -2311, 1627, -5121, 3935, 5050, 2762, -4793, -1906, 755, 1654, -236, 4952, -2155, 4394, -5697, -4391, -4792, -3385, -260, 3581, -1541, 5674, -1931, 4901, -4875, -3518, 710, -5525, -3827, -5096, 5371, -5015, -1205, 290, -4425, -5462, -467, 2509, -5711, 4026, 5807, 1458, 5721, 5762, 4178, 2105, -668, 4852, -3392, 2856, -779, -3025, 2520, -3513, -5278, 2647, 1898, -5250, 5950, -1126, 5488, -6012, -3107, -833, 633, -2243, -735, 5633, -2702, 2333, -5281, -5205, 5047, -5090, -2424, -3292, 569, -5899, -1444, -2610, -4021, -817, 4203, 1997, 2, -2958, 162, -6107, 2000, 3649, -2497, -5926, -4732, -6102, -3779, -2354, 5536, -3270, 3706, -280, 1452, 3067, 5494, -2597, 4865, 6019, -5183, -2679, 4588, -2124, -6028, 5887, 2652, -2117, 1580, -1910, 4638, -2340};
const S_Q_SIZE iGMb[N] = {4091, 4401, 1081, 1229, 2530, 6014, -4342, 5329, 2579, 4751, -5825, -586, -5266, 2812, 5890, -1591, 3109, 2125, 1960, -1364, -1688, -1885, 4189, 1875, 5847, -3743, 4615, 5190, -965, -1711, 5882, -1134, -3872, -14, -1690, -4843, 5719, 3569, 5981, -2181, 4426, -3983, -1534, 4679, -1237, 1538, -432, 100, -4042, -5664, -2564, 5145, 3412, -4431, 5831, -2829, 5217, -1549, -4407, -4783, -117, -997, 6049, 79, 13, -5351, -3403, 5453, 4586, -834, 2903, 4676, -2446, -4668, -3467, -3180, 2083, -3782, -3604, 3110, -5274, 3269, 1367, -5892, -2030, -3854, -1762, -730, -1195, 2211, 1808, -4970, 48, -2742, 2560, 1228, -2851, -1502, -489, 1820, -883, -3323, -6130, 3012, 6109, 2796, 2203, 1652, 711, -5285, 1053, -3316, 5244, 1517, -2967, -1020, 900, 3888, -1156, -1553, 4949, -4673, -2315, 4746, -2019, 126, 2921, -5569, -5654, -5746, 1582, 4868, 42, 673, 2240, -5070, 1296, -300, -4614, -3711, -340, 989, -1748, -4602, -5204, -3802, 1004, -2053, 4703, 163, -3146, 4597, -5858, -237, 2991, -351, 4647, 3362, 2060, -932, -278, -5625, 5655, -5064, 5914, -2962, 4092, 5880, -5357, 3402, 5133, -2895, -1060, 5252, -3281, 1556, -5381, 4773, 3853, -3509, -1964, -4552, 1758, -5186, -914, -16, -3687, 3243, -5753, -4699, -3698, -737, 6101, 3253, -2320, -2649, 4506, 3736, -5460, -1467, -3159, -2341, 3566, 2133, 3901, 6038, -4956, -5680, 3468, 4659, 625, 2700, -4551, 3443, 3060, 3388, 3526, 4418, -378, -6057, 1730, 2558, -1949, 5344, 5286, 2190, -727, -6090, 2482, -3533, 5387, 4101, 4609, -3684, -4063, 144, 5656, -3585, 2621, 5424, -1477, 2959, -943, -6040, 1715, 4951, -2749, 1888, 3764, 39, -4070, 2080, 2502, 1469, -1739, -3580, 5601, 1093, 3784, 5041, 2058, -3890, -841, -2650, 2059, -2411, -4884, 2496, -4371, -695, 371, -4296, 3073, -1963, 40, -2285, -3044, -4302, 5603, 4051, -4395, 676, -909, -4910, -5788, 4981, 2628, 3488, -1333, -5267, -5552, -2356, -5150, 2330, 3884, 5473, -4424, -5348, 5737, 5613, -2784, -721, -1012, 2510, -5600, 386, 4462, 105, 2076, -1846, 119, 3955, 4370, -784, 3672, -850, 750, 3240, 3133, 754, 4013, -360, -3079, 5378, -408, -1271, 2818, 1851, 4966, -4108, 2688, -6084, -5475, 926, 2936, 4327, -2114, -5200, 6047, -2879, -1797, -3339, 2472, -6034, 728, -4720, 6056, -1857, -1253, 2452, 2811, 3787, 945, -3291, 1244, -3474, -1272, -1071, 5894, 4325, 4639, 3819, -2463, -5233, -5503, -3619, 5539, -4582, 1361, -2477, 2949, -1024, -1988, -3181, 478, -5800, 101, 1911, -2806, 3608, -292, -1753, 812, -3374, 637, -4130, 5299, -3161, 3512, -3999, -5221, -4367, 3036, 4759, 2163, 3937, 3755, -983, -4550, 4922, -357, 424, 5538, -6061, -1158, -4511, -315, 1097, 2890, -2262, 2569, 2250, 2352, 821, 2550, -1273, -4520, 136, 617, 3157, 5889, -3070, -5434, 120, 4405, 1825, -2654, -5075, -2028, -896, 2441, -2727, -1113, 599, 2085, -824, -5056, -6112, 4801, -2363, -3279, 4514, -2834, -937, -619, -6115, -4339, -2523, -5393, -686, 3213, -3816, -2416, 2835, -1867, 3732, -4328, 1457, -1432, -4220, 832, 1628, 3410, 4900, -1434, 5111, -2746, -5964, -4858, 4083, 3072, -3442, -2436, -2167, 5259, -876, -5733, 303, 1465, 3871, 4873, 5813, -2272, -5391, 3311, 5947, -3652, 5852, 3856, 928, 4933, -3759, 1871, 2184, 5571, 5879, 3481, -692, -2778, -4136, 35, 2609, 5963, -4225, 1080, -250, -3845, 3052, 3813, -1224, -5553, -3835, 2340, -4638, 1910, -1580, 2117, -2652, -5887, 6028, 2124, -4588, 2679, 5183, -6019, -4865, 2597, -5494, -3067, -1452, 280, -3706, 3270, -5536, 2354, 3779, 6102, 4732, 5926, 2497, -3649, -2000, 6107, -162, 2958, -2, -1997, -4203, 817, 4021, 2610, 1444, 5899, -569, 3292, 2424, 5090, -5047, 5205, 5281, -2333, 2702, -5633, 735, 2243, -633, 833, 3107, 6012, -5488, 1126, -5950, 5250, -1898, -2647, 5278, 3513, -2520, 3025, 779, -2856, 3392, -4852, 668, -2105, -4178, -5762, -5721, -1458, -5807, -4026, 5711, -2509, 467, 5462, 4425, -290, 1205, 5015, -5371, 5096, 3827, 5525, -710, 3518, 4875, -4901, 1931, -5674, 1541, -3581, 260, 3385, 4792, 4391, 5697, -4394, 2155, -4952, 236, -1654, -755, 1906, 4793, -2762, -5050, -3935, 5121, -1627, 2311, 3346, -3733, 707, 1088, 4936, 678, -2044, 18, 5684, 960, 4459, -4332, 226, 2451, 6, -3415, 320, -5991, -3326, -3554, 2852, 2981, 1707, 5408, 5017, -2413, -2499, 2968, 1899, -5560, 4183, 5290, -2205, -4610, -4348, -3545, 5694, 3461, 4175, 5747, 5561, 3378, 5227, 952, 4319, -2479, 4356, 3088, -1171, 840, -6032, 486, 6000, 1342, -1907, 6017, 4798, 5489, 4498, 4193, 2306, -5768, 1475, -5917, -3260, -4252, 1625, -5269, 4740, 5730, -4333, -5938, -5795, -5372, -884, -4802, -2087, -2134, -4623, -4733, -780, 1546, -5718, -2090, 2265, -4962, 5824, -893, -708, -2567, 2251, -1090, 5356, -4881, 2861, 4003, -3074, 484, -4763, -2880, -54, -6132, -3264, 2121, -2034, 2519, -2756, 3824, -3615, -870, -1401, 4762, -986, 4097, 2414, -5793, -2336, -1735, 808, 2999, 2130, 4286, -211, -4844, 5132, -4374, 245, 5974, 4874, -4997, -4729, -1750, -2337, -3214, 2113, 3721, -2004, -2267, -2711, -3355, -1215, -2791, 294, 4711, 3391, 1377, -3217, -2100, 4569, -1399, -2380, -5366, 53, 4653, 439, -2036, -5261, -2082, -3946, 1141, 2556, -4688, -4139, -1659, -3641, -2457, -4338, -1044, 2131, 5765, -1946, -2508, 2718, 1419, 4531, 3844, 4066, 4293, -632, -764, -936, 4313, 4869, -103, 1611, -1397, -800, -3456, 2393, 15, -1459, 5003, 17, 565, 5891, -112, -1231, -1877, -3404, 3974, -1308, -5159, 5840, -1807, -3951, 6035, -5325, 1574, -1353, 2020, 2465, -4098, 384, 2642, 2729, 5399, 2175, -2893, -302, -4254, 4375, -5678, 5010, -477, -3158, -862, 104, -5941, -2646, -5532, -179, 5617, -1354, 541, 135, 3041, -5089, -5763, 5085, -153, 842, 4129, -4604, -1210, -3863, 1008, 2725, -517, 6058, 1101, 1950, -3865, 5688, -5413, -284, -2210, 5335, 927, 1770, 273, -3912, 2271, 5225, -2006, 116, -482, 91, -590, 757, 1304, -4765, -5838, -4257, -4135, -4833, 4191, 309, 2318, 2292, -1896, -650, -2808, -51, -1695, -2720, -4377, -1921, -2400, -45, -5110, 3924, 3188, 367, 2077, 336, 5384, 5631, -3693, 4621, 1775, -3423, 451, 6108, 1317, -6043, -3494, 5896, -5006, 3132, -725, 4977, -128, -4918, 1366, -159, -1670, 3809, 5149, -5989, 2638, 4197, 1418, -2224, 4156, -3916, -3645, -1844, 882, -4131, -2116, -2526, -98, 459, 2966, 3166, 405, 5000, -2978, -5885, -3303, 1551, -4114, 3630, -1523, -3024, 700, -3716, -2781, -5659, -852, -694, 5850, 3950, 4775, -348, 1446, 6018, 3386, -819, 5310, 5476, 553, -2815, 2586, 1431, 2741, 473, -906, 4745, 836, 4062, -1623, -4562, -537, 5534, 312, 4307, 4351, 5764, -3610, -3908, -4102, 5, -4894, 4363, 1152, 5421, 5231, -5816, 436, -4722, -3686, -6060, -4059};
#endif
/*
* Compute NTT on a ring element.
*/
void ntt(S_Q_SIZE *a, unsigned logn)
{
// To be revieweid (Add refference)
size_t n, t, m;
n = (size_t)1 << logn;
t = n;
for (m = 1; m < n; m <<= 1)
{
size_t ht, i, j1;
ht = t >> 1;
for (i = 0, j1 = 0; i < m; i++, j1 += t)
{
size_t j, j2;
S_DOUBLE_Q_SIZE s;
s = GMb[m + i];
j2 = j1 + ht;
for (j = j1; j < j2; j++)
{
S_DOUBLE_Q_SIZE u, v;
u = a[j];
v = montymul(a[j + ht], s);
a[j] = (S_Q_SIZE)add(u, v);
a[j + ht] = (S_Q_SIZE)sub(u, v);
}
}
t = ht;
}
}
/*
* Compute the inverse NTT on a ring element, binary case.
*/
void invntt_tomont(S_Q_SIZE *a, unsigned logn)
{
// To be revieweid (Add refference)
size_t n, t, m;
S_DOUBLE_Q_SIZE ni;
n = (size_t)1 << logn;
t = 1;
m = n;
while (m > 1)
{
size_t hm, dt, i, j1;
hm = m >> 1;
dt = t << 1;
for (i = 0, j1 = 0; i < hm; i++, j1 += dt)
{
size_t j, j2;
S_DOUBLE_Q_SIZE s;
j2 = j1 + t;
s = iGMb[hm + i];
for (j = j1; j < j2; j++)
{
S_DOUBLE_Q_SIZE u, v, w;
u = a[j];
v = a[j + t];
a[j] = (S_Q_SIZE)add(u, v);
w = sub(u, v);
a[j + t] = (S_Q_SIZE)montymul(w, s);
}
}
t = dt;
m = hm;
}
ni = R;
for (m = n; m > 1; m >>= 1)
{
ni = rshift1(ni);
}
for (m = 0; m < n; m++)
{
a[m] = (S_Q_SIZE)montymul(a[m], ni);
}
}
/*************************************************
* Name: fqmul
*
* Description: Multiplication followed by Montgomery reduction
*
* Arguments: - int16_t a: first factor
* - int16_t b: second factor
*
* Returns 16-bit integer congruent to a*b*R^{-1} mod q
**************************************************/
static int16_t fqmul(int16_t a, int16_t b)
{
return reduce((int32_t)a * b);
}
/*************************************************
* Name: basemul
*
* Description: Multiplication of polynomials in Zq[X]/(X^2-zeta)
* used for multiplication of elements in Rq in NTT domain
*
* Arguments: - int16_t r[2]: pointer to the output polynomial
* - const int16_t a[2]: pointer to the first factor
* - const int16_t b[2]: pointer to the second factor
* - int16_t zeta: integer defining the reduction polynomial
**************************************************/
void basemul(int16_t r[2],
const int16_t a[2],
const int16_t b[2],
int16_t zeta)
{
r[0] = fqmul(a[1], b[1]);
r[0] = fqmul(r[0], zeta);
r[0] += fqmul(a[0], b[0]);
r[1] = fqmul(a[0], b[1]);
r[1] += fqmul(a[1], b[0]);
}