travis: Enable caching for sonarcloud scan
[strongswan.git] / src / libstrongswan / math / libnttfft / ntt_fft_params.c
1 /*
2 * Copyright (C) 2014-2016 Andreas Steffen
3 * HSR Hochschule fuer Technik Rapperswil
4 *
5 * This program is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License as published by the
7 * Free Software Foundation; either version 2 of the License, or (at your
8 * option) any later version. See <http://www.fsf.org/copyleft/gpl.txt>.
9 *
10 * This program is distributed in the hope that it will be useful, but
11 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
12 * or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 * for more details.
14 */
15
16 #include "ntt_fft_params.h"
17
18 /**
19 * FFT twiddle factors in Montgomery form for q = 12289 and n = 1024
20 */
21 static const uint16_t wr_12289_1024[] = {
22 4075, 3051, 2031, 1207, 9987, 10092, 2948, 9273, 11973, 9094,
23 3202, 9430, 7377, 5092, 3728, 10626, 4536, 1062, 2882, 6039,
24 975, 10908, 6065, 2249, 11889, 4978, 10431, 7270, 12138, 4890,
25 6119, 4895, 6364, 4611, 4737, 10911, 6212, 9452, 8455, 8758,
26 11316, 1479, 11026, 11847, 2920, 7901, 6190, 8374, 4789, 1170,
27 8174, 7278, 241, 11809, 1058, 2686, 8724, 9650, 5868, 4885,
28 5874, 5179, 7991, 10600, 3262, 81, 3969, 10146, 5594, 3748,
29 11606, 3400, 6843, 3504, 11939, 7428, 7591, 3289, 1404, 7351,
30 3818, 2747, 11713, 8643, 5681, 8011, 11580, 2126, 5862, 4591,
31 3757, 12047, 431, 8830, 2555, 2305, 2344, 4255, 11871, 4096,
32
33 4080, 3296, 1747, 11869, 3998, 11567, 1489, 11516, 11279, 11955,
34 8212, 9140, 5456, 9275, 12071, 1607, 5009, 11950, 7967, 9424,
35 7083, 2975, 10596, 3066, 2766, 355, 5106, 4414, 7373, 4896,
36 6413, 7012, 11785, 12171, 6507, 11618, 3988, 11077, 2057, 2481,
37 10968, 9005, 11130, 4654, 6844, 3553, 2051, 2187, 8851, 3584,
38 3570, 2884, 6137, 5777, 426, 8585, 2839, 3932, 8333, 2780,
39 1041, 1853, 4774, 435, 9026, 12159, 5919, 7384, 5435, 8246,
40 10806, 1067, 3127, 5755, 11637, 4919, 7540, 790, 1843, 4284,
41 1003, 12280, 11848, 2969, 10302, 949, 9634, 5084, 3336, 3707,
42 9597, 3271, 522, 1000, 12133, 4645, 6403, 6522, 64, 3136,
43
44 6196, 8668, 6906, 6591, 3445, 9048, 948, 9585, 2683, 8577,
45 2447, 9302, 1105, 4989, 10970, 9103, 3643, 6461, 9364, 4143,
46 6383, 5542, 1200, 9644, 5574, 2768, 453, 9908, 6221, 9893,
47 5486, 10745, 10367, 4134, 5942, 8511, 11502, 10593, 2919, 7852,
48 3789, 1326, 3529, 875, 6008, 11745, 10211, 8779, 56, 2744,
49 11566, 1440, 9115, 4231, 10695, 7917, 6974, 9923, 6956, 9041,
50 605, 5067, 2503, 12046, 382, 6429, 7796, 1045, 2049, 2089,
51 4049, 1777, 1050, 2294, 1805, 2422, 8077, 2525, 835, 4048,
52 1728, 10938, 7535, 545, 2127, 5911, 6992, 10805, 1018, 726,
53 10996, 10377, 4624, 5374, 5257, 11813, 1254, 1, 49, 2401,
54
55 7048, 1260, 295, 2166, 7822, 2319, 3030, 1002, 12231, 9447,
56 8210, 9042, 654, 7468, 9551, 1017, 677, 8595, 3329, 3364,
57 5079, 3091, 3991, 11224, 9260, 11336, 2459, 9890, 5339, 3542,
58 1512, 354, 5057, 2013, 325, 3636, 6118, 4846, 3963, 9852,
59 3477, 10616, 4046, 1630, 6136, 5728, 10314, 1537, 1579, 3637,
60 6167, 7247, 11011, 11112, 3772, 493, 11868, 3949, 9166, 6730,
61 10256, 10984, 9789, 390, 6821, 2426, 8273, 12129, 4449, 9088,
62 2908, 7313, 1956, 9821, 1958, 9919, 6760, 11726, 9280, 27,
63 1323, 3382, 5961, 9442, 7965, 9326, 2281, 1168, 8076, 2476,
64 10723, 9289, 468, 10643, 5369, 5012, 12097, 2881, 5990, 10863,
65
66 3860, 4805, 1954, 9723, 9445, 8112, 4240, 11136, 4948, 8961,
67 8974, 9611, 3957, 9558, 1360, 5195, 8775, 12149, 5429, 7952,
68 8689, 7935, 7856, 3985, 10930, 7143, 5915, 7188, 8120, 4632,
69 5766, 12176, 6752, 11334, 2361, 5088, 3532, 1022, 922, 8311,
70 1702, 9664, 6554, 1632, 6234, 10530, 12121, 4057, 2169, 7969,
71 9522, 11885, 4782, 827, 3656, 7098, 3710, 9744, 10474, 9377,
72 4780, 729, 11143, 5291, 1190, 9154, 6142, 6022, 142, 6958,
73 9139, 5407, 6874, 5023, 347, 4714, 9784, 145, 7105, 4053,
74 1973, 10654, 5908, 6845, 3602, 4452, 9235, 10111, 3879, 5736,
75 10706, 8456, 8807, 1428, 8527, 12286, 12142, 5086, 3434, 8509,
76
77 11404, 5791, 1112, 5332, 3199, 9283, 174, 8526, 12237, 9741,
78 10327, 2174, 8214, 9238, 10258, 11082, 2302, 2197, 9341, 3016,
79 316, 3195, 9087, 2859, 4912, 7197, 8561, 1663, 7753, 11227,
80 9407, 6250, 11314, 1381, 6224, 10040, 400, 7311, 1858, 5019,
81 151, 7399, 6170, 7394, 5925, 7678, 7552, 1378, 6077, 2837,
82 3834, 3531, 973, 10810, 1263, 442, 9369, 4388, 6099, 3915,
83 7500, 11119, 4115, 5011, 12048, 480, 11231, 9603, 3565, 2639,
84 6421, 7404, 6415, 7110, 4298, 1689, 9027, 12208, 8320, 2143,
85 6695, 8541, 683, 8889, 5446, 8785, 350, 4861, 4698, 9000,
86 10885, 4938, 8471, 9542, 576, 3646, 6608, 4278, 709, 10163,
87
88 6427, 7698, 8532, 242, 11858, 3459, 9734, 9984, 9945, 8034,
89 418, 8193, 8209, 8993, 10542, 420, 8291, 722, 10800, 773,
90 1010, 334, 4077, 3149, 6833, 3014, 218, 10682, 7280, 339,
91 4322, 2865, 5206, 9314, 1693, 9223, 9523, 11934, 7183, 7875,
92 4916, 7393, 5876, 5277, 504, 118, 5782, 671, 8301, 1212,
93 10232, 9808, 1321, 3284, 1159, 7635, 5445, 8736, 10238, 10102,
94 3438, 8705, 8719, 9405, 6152, 6512, 11863, 3704, 9450, 8357,
95 3956, 9509, 11248, 10436, 7515, 11854, 3263, 130, 6370, 4905,
96 6854, 4043, 1483, 11222, 9162, 6534, 652, 7370, 4749, 11499,
97 10446, 8005, 11286, 9, 441, 9320, 1987, 11340, 2655, 7205,
98
99 8953, 8582, 2692, 9018, 11767, 11289, 156, 7644, 5886, 5767,
100 12225, 9153, 6093, 3621, 5383, 5698, 8844, 3241, 11341, 2704,
101 9606, 3712, 9842, 2987, 11184, 7300, 1319, 3186, 8646, 5828,
102 2925, 8146, 5906, 6747, 11089, 2645, 6715, 9521, 11836, 2381,
103 6068, 2396, 6803, 1544, 1922, 8155, 6347, 3778, 787, 1696,
104 9370, 4437, 8500, 10963, 8760, 11414, 6281, 544, 2078, 3510,
105 12233, 9545, 723, 10849, 3174, 8058, 1594, 4372, 5315, 2366,
106 5333, 3248, 11684, 7222, 9786, 243, 11907, 5860, 4493, 11244,
107 10240, 10200, 8240, 10512, 11239, 9995, 10484, 9867, 4212, 9764,
108 11454, 8241, 10561, 1351, 4754, 11744, 10162, 6378, 5297, 1484,
109
110 11271, 11563, 1293, 1912, 7665, 6915, 7032, 476, 11035, 12288,
111 12240, 9888, 5241, 11029, 11994, 10123, 4467, 9970, 9259, 11287,
112 58, 2842, 4079, 3247, 11635, 4821, 2738, 11272, 11612, 3694,
113 8960, 8925, 7210, 9198, 8298, 1065, 3029, 953, 9830, 2399,
114 6950, 8747, 10777, 11935, 7232, 10276, 11964, 8653, 6171, 7443,
115 8326, 2437, 8812, 1673, 8243, 10659, 6153, 6561, 1975, 10752,
116 10710, 8652, 6122, 5042, 1278, 1177, 8517, 11796, 421, 8340,
117 3123, 5559, 2033, 1305, 2500, 11899, 5468, 9863, 4016, 160,
118 7840, 3201, 9381, 4976, 10333, 2468, 10331, 2370, 5529, 563,
119 3009, 12262, 10966, 8907, 6328, 2847, 4324, 2963, 10008, 11121,
120
121 4213, 9813, 1566, 3000, 11821, 1646, 6920, 7277, 192, 9408,
122 6299, 1426, 8429, 7484, 10335, 2566, 2844, 4177, 8049, 1153,
123 7341, 3328, 3315, 2678, 8332, 2731, 10929, 7094, 3514, 140,
124 6860, 4337, 3600, 4354, 4433, 8304, 1359, 5146, 6374, 5101,
125 4169, 7657, 6523, 113, 5537, 955, 9928, 7201, 8757, 11267,
126 11367, 3978, 10587, 2625, 5735, 10657, 6055, 1759, 168, 8232,
127 10120, 4320, 2767, 404, 7507, 11462, 8633, 5191, 8579, 2545,
128 1815, 2912, 7509, 11560, 1146, 6998, 11099, 3135, 6147, 6267,
129 12147, 5331, 3150, 6882, 5415, 7266, 11942, 7575, 2505, 12144,
130 5184, 8236, 10316, 1635, 6381, 5444, 8687, 7837, 3054, 2178,
131
132 8410, 6553, 1583, 3833, 3482, 10861, 3762, 3, 147, 7203,
133 8855, 3780, 885, 6498, 11177, 6957, 9090, 3006, 12115, 3763,
134 52, 2548, 1962, 10115, 4075
135 };
136
137 /**
138 * FFT phase shift in forward transform for q = 12289 and n = 1024
139 */
140 static const uint16_t wf_12289_1024[] = {
141 3186, 10013, 8646, 11366, 5828, 3929, 2925, 8186, 8146, 7866,
142 5906, 4475, 6747, 10362, 11089, 3889, 2645, 6226, 6715, 10138,
143 9521, 5202, 11836, 9118, 2381, 4378, 6068, 5609, 2396, 4483,
144 6803, 10754, 1544, 10808, 1922, 1165, 8155, 7929, 6347, 7562,
145 3778, 1868, 787, 5509, 1696, 11872, 9370, 4145, 4437, 6481,
146 8500, 10344, 10963, 3007, 8760, 12164, 11414, 6164, 6281, 7100,
147 544, 3808, 2078, 2257, 3510, 12281, 12233, 11897, 9545, 5370,
148 723, 5061, 10849, 2209, 3174, 9929, 8058, 7250, 1594, 11158,
149 4372, 6026, 5315, 338, 2366, 4273, 5333, 464, 3248, 10447,
150 11684, 8054, 7222, 1398, 9786, 7057, 243, 1701, 11907, 9615,
151
152 5860, 4153, 4493, 6873, 11244, 4974, 10240, 10235, 10200, 9955,
153 8240, 8524, 10512, 12139, 11239, 4939, 9995, 8520, 10484, 11943,
154 9867, 7624, 4212, 4906, 9764, 6903, 11454, 6444, 8241, 8531,
155 10561, 193, 1351, 9457, 4754, 8700, 11744, 8474, 10162, 9689,
156 6378, 7779, 5297, 212, 1484, 10388, 11271, 5163, 11563, 7207,
157 1293, 9051, 1912, 1095, 7665, 4499, 6915, 11538, 7032, 68,
158 476, 3332, 11035, 3511, 12288, 12282, 12240, 11946, 9888, 7771,
159 5241, 12109, 11029, 3469, 11994, 10224, 10123, 9416, 4467, 6691,
160 9970, 8345, 9259, 3368, 11287, 5275, 58, 406, 2842, 7605,
161 4079, 3975, 3247, 10440, 11635, 7711, 4821, 9169, 2738, 6877,
162
163 11272, 5170, 11612, 7550, 3694, 1280, 8960, 1275, 8925, 1030,
164 7210, 1314, 9198, 2941, 8298, 8930, 1065, 7455, 3029, 8914,
165 953, 6671, 9830, 7365, 2399, 4504, 6950, 11783, 8747, 12073,
166 10777, 1705, 11935, 9811, 7232, 1468, 10276, 10487, 11964, 10014,
167 8653, 11415, 6171, 6330, 7443, 2945, 8326, 9126, 2437, 4770,
168 8812, 239, 1673, 11711, 8243, 8545, 10659, 879, 6153, 6204,
169 6561, 9060, 1975, 1536, 10752, 1530, 10710, 1236, 8652, 11408,
170 6122, 5987, 5042, 10716, 1278, 8946, 1177, 8239, 8517, 10463,
171 11796, 8838, 421, 2947, 8340, 9224, 3123, 9572, 5559, 2046,
172 2033, 1942, 1305, 9135, 2500, 5211, 11899, 9559, 5468, 1409,
173
174 9863, 7596, 4016, 3534, 160, 1120, 7840, 5724, 3201, 10118,
175 9381, 4222, 4976, 10254, 10333, 10886, 2468, 4987, 10331, 10872,
176 2370, 4301, 5529, 1836, 563, 3941, 3009, 8774, 12262, 12100,
177 10966, 3028, 8907, 904, 6328, 7429, 2847, 7640, 4324, 5690,
178 2963, 8452, 10008, 8611, 11121, 4113, 4213, 4913, 9813, 7246,
179 1566, 10962, 3000, 8711, 11821, 9013, 1646, 11522, 6920, 11573,
180 7277, 1783, 192, 1344, 9408, 4411, 6299, 7226, 1426, 9982,
181 8429, 9847, 7484, 3232, 10335, 10900, 2566, 5673, 2844, 7619,
182 4177, 4661, 8049, 7187, 1153, 8071, 7341, 2231, 3328, 11007,
183 3315, 10916, 2678, 6457, 8332, 9168, 2731, 6828, 10929, 2769,
184
185 7094, 502, 3514, 20, 140, 980, 6860, 11153, 4337, 5781,
186 3600, 622, 4354, 5900, 4433, 6453, 8304, 8972, 1359, 9513,
187 5146, 11444, 6374, 7751, 5101, 11129, 4169, 4605, 7657, 4443,
188 6523, 8794, 113, 791, 5537, 1892, 955, 6685, 9928, 8051,
189 7201, 1251, 8757, 12143, 11267, 5135, 11367, 5835, 3978, 3268,
190 10587, 375, 2625, 6086, 5735, 3278, 10657, 865, 6055, 5518,
191 1759, 24, 168, 1176, 8232, 8468, 10120, 9395, 4320, 5662,
192 2767, 7080, 404, 2828, 7507, 3393, 11462, 6500, 8633, 11275,
193 5191, 11759, 8579, 10897, 2545, 5526, 1815, 416, 2912, 8095,
194 7509, 3407, 11560, 7186, 1146, 8022, 6998, 12119, 11099, 3959,
195
196 3135, 9656, 6147, 6162, 6267, 7002, 12147, 11295, 5331, 450,
197 3150, 9761, 6882, 11307, 5415, 1038, 7266, 1706, 11942, 9860,
198 7575, 3869, 2505, 5246, 12144, 11274, 5184, 11710, 8236, 8496,
199 10316, 10767, 1635, 11445, 6381, 7800, 5444, 1241, 8687, 11653,
200 7837, 5703, 3054, 9089, 2178, 2957, 8410, 9714, 6553, 9004,
201 1583, 11081, 3833, 2253, 3482, 12085, 10861, 2293, 3762, 1756,
202 3, 21, 147, 1029, 7203, 1265, 8855, 540, 3780, 1882,
203 885, 6195, 6498, 8619, 11177, 4505, 6957, 11832, 9090, 2185,
204 3006, 8753, 12115, 11071, 3763, 1763, 52, 364, 2548, 5547,
205 1962, 1445, 10115, 9360, 4075, 3947, 3051, 9068, 2031, 1928,
206
207 1207, 8449, 9987, 8464, 10092, 9199, 2948, 8347, 9273, 3466,
208 11973, 10077, 9094, 2213, 3202, 10125, 9430, 4565, 7377, 2483,
209 5092, 11066, 3728, 1518, 10626, 648, 4536, 7174, 1062, 7434,
210 2882, 7885, 6039, 5406, 975, 6825, 10908, 2622, 6065, 5588,
211 2249, 3454, 11889, 9489, 4978, 10268, 10431, 11572, 7270, 1734,
212 12138, 11232, 4890, 9652, 6119, 5966, 4895, 9687, 6364, 7681,
213 4611, 7699, 4737, 8581, 10911, 2643, 6212, 6617, 9452, 4719,
214 8455, 10029, 8758, 12150, 11316, 5478, 1479, 10353, 11026, 3448,
215 11847, 9195, 2920, 8151, 7901, 6151, 6190, 6463, 8374, 9462,
216 4789, 8945, 1170, 8190, 8174, 8062, 7278, 1790, 241, 1687,
217
218 11809, 8929, 1058, 7406, 2686, 6513, 8724, 11912, 9650, 6105,
219 5868, 4209, 4885, 9617, 5874, 4251, 5179, 11675, 7991, 6781,
220 10600, 466, 3262, 10545, 81, 567, 3969, 3205, 10146, 9577,
221 5594, 2291, 3748, 1658, 11606, 7508, 3400, 11511, 6843, 11034,
222 3504, 12239, 11939, 9839, 7428, 2840, 7591, 3981, 3289, 10734,
223 1404, 9828, 7351, 2301, 3818, 2148, 2747, 6940, 11713, 8257,
224 8643, 11345, 5681, 2900, 8011, 6921, 11580, 7326, 2126, 2593,
225 5862, 4167, 4591, 7559, 3757, 1721, 12047, 10595, 431, 3017,
226 8830, 365, 2555, 5596, 2305, 3846, 2344, 4119, 4255, 5207,
227 11871, 9363, 4096, 4094, 4080, 3982, 3296, 10783, 1747, 12229,
228
229 11869, 9349, 3998, 3408, 11567, 7235, 1489, 10423, 11516, 6878,
230 11279, 5219, 11955, 9951, 8212, 8328, 9140, 2535, 5456, 1325,
231 9275, 3480, 12071, 10763, 1607, 11249, 5009, 10485, 11950, 9916,
232 7967, 6613, 9424, 4523, 7083, 425, 2975, 8536, 10596, 438,
233 3066, 9173, 2766, 7073, 355, 2485, 5106, 11164, 4414, 6320,
234 7373, 2455, 4896, 9694, 6413, 8024, 7012, 12217, 11785, 8761,
235 12171, 11463, 6507, 8682, 11618, 7592, 3988, 3338, 11077, 3805,
236 2057, 2110, 2481, 5078, 10968, 3042, 9005, 1590, 11130, 4176,
237 4654, 8000, 6844, 11041, 3553, 293, 2051, 2068, 2187, 3020,
238 8851, 512, 3584, 510, 3570, 412, 2884, 7899, 6137, 6092,
239
240 5777, 3572, 426, 2982, 8585, 10939, 2839, 7584, 3932, 2946,
241 8333, 9175, 2780, 7171, 1041, 7287, 1853, 682, 4774, 8840,
242 435, 3045, 9026, 1737, 12159, 11379, 5919, 4566, 7384, 2532,
243 5435, 1178, 8246, 8566, 10806, 1908, 1067, 7469, 3127, 9600,
244 5755, 3418, 11637, 7725, 4919, 9855, 7540, 3624, 790, 5530,
245 1843, 612, 4284, 5410, 1003, 7021, 12280, 12226, 11848, 9202,
246 2969, 8494, 10302, 10669, 949, 6643, 9634, 5993, 5084, 11010,
247 3336, 11063, 3707, 1371, 9597, 5734, 3271, 10608, 522, 3654,
248 1000, 7000, 12133, 11197, 4645, 7937, 6403, 7954, 6522, 8787,
249 64, 448, 3136, 9663, 6196, 6505, 8668, 11520, 6906, 11475,
250
251 6591, 9270, 3445, 11826, 9048, 1891, 948, 6636, 9585, 5650,
252 2683, 6492, 8577, 10883, 2447, 4840, 9302, 3669, 1105, 7735,
253 4989, 10345, 10970, 3056
254 };
255
256 /**
257 * FFT phase shift and scaling inverse transform for q = 12289 and n = 1024
258 */
259 static const uint16_t wi_12289_1024[] = {
260 12277, 5265, 9530, 3117, 5712, 816, 10650, 3277, 9246, 4832,
261 5957, 851, 10655, 10300, 3227, 461, 3577, 511, 73, 1766,
262 5519, 2544, 2119, 7325, 2802, 5667, 11343, 3376, 5749, 6088,
263 7892, 2883, 3923, 2316, 3842, 4060, 580, 3594, 2269, 9102,
264 6567, 9716, 1388, 5465, 7803, 8137, 2918, 3928, 9339, 10112,
265 11978, 10489, 3254, 3976, 568, 8859, 11799, 12219, 12279, 10532,
266 12038, 8742, 4760, 680, 8875, 4779, 7705, 8123, 2916, 10950,
267 6831, 4487, 641, 10625, 5029, 2474, 2109, 5568, 2551, 2120,
268 3814, 4056, 2335, 10867, 3308, 11006, 6839, 977, 10673, 8547,
269 1221, 1930, 7298, 11576, 8676, 2995, 3939, 7585, 11617, 12193,
270
271 5253, 2506, 358, 8829, 6528, 11466, 1638, 234, 1789, 10789,
272 6808, 11506, 8666, 1238, 3688, 4038, 4088, 584, 1839, 7285,
273 8063, 4663, 9444, 10127, 8469, 4721, 2430, 9125, 11837, 1691,
274 10775, 6806, 6239, 6158, 7902, 4640, 4174, 5863, 11371, 3380,
275 3994, 11104, 6853, 979, 3651, 11055, 6846, 978, 7162, 9801,
276 10178, 1454, 7230, 4544, 9427, 8369, 11729, 12209, 10522, 10281,
277 8491, 1213, 5440, 9555, 1365, 195, 3539, 11039, 1577, 5492,
278 11318, 5128, 11266, 3365, 7503, 4583, 7677, 8119, 4671, 5934,
279 7870, 6391, 913, 1886, 2025, 5556, 7816, 11650, 6931, 9768,
280 3151, 9228, 6585, 7963, 11671, 6934, 11524, 6913, 11521, 5157,
281
282 7759, 2864, 9187, 3068, 5705, 815, 1872, 2023, 289, 5308,
283 6025, 7883, 9904, 4926, 7726, 8126, 4672, 2423, 9124, 3059,
284 437, 1818, 7282, 6307, 901, 7151, 11555, 8673, 1239, 177,
285 5292, 756, 108, 1771, 253, 8814, 10037, 4945, 2462, 7374,
286 2809, 5668, 7832, 4630, 2417, 5612, 7824, 8140, 4674, 7690,
287 11632, 8684, 11774, 1682, 5507, 7809, 11649, 10442, 8514, 6483,
288 9704, 6653, 2706, 10920, 1560, 3734, 2289, 327, 7069, 4521,
289 4157, 4105, 2342, 10868, 12086, 12260, 3507, 501, 10605, 1515,
290 1972, 7304, 2799, 3911, 7581, 1083, 7177, 6292, 4410, 630,
291 90, 3524, 2259, 7345, 6316, 6169, 6148, 6145, 4389, 627,
292
293 10623, 12051, 12255, 8773, 6520, 2687, 3895, 2312, 5597, 11333,
294 1619, 5498, 2541, 363, 3563, 509, 7095, 11547, 12183, 3496,
295 2255, 9100, 1300, 7208, 8052, 6417, 7939, 9912, 1416, 5469,
296 6048, 864, 1879, 2024, 9067, 6562, 2693, 7407, 9836, 10183,
297 8477, 1211, 173, 7047, 8029, 1147, 3675, 525, 75, 7033,
298 8027, 8169, 1167, 7189, 1027, 7169, 9802, 6667, 2708, 3898,
299 4068, 9359, 1337, 191, 5294, 6023, 2616, 7396, 11590, 8678,
300 8262, 6447, 921, 10665, 12057, 3478, 4008, 11106, 12120, 3487,
301 9276, 10103, 6710, 11492, 8664, 8260, 1180, 10702, 5040, 720,
302 3614, 5783, 9604, 1372, 196, 28, 4, 10534, 5016, 11250,
303
304 10385, 12017, 8739, 3004, 9207, 6582, 6207, 7909, 4641, 663,
305 7117, 8039, 2904, 3926, 4072, 7604, 6353, 11441, 3390, 5751,
306 11355, 10400, 8508, 2971, 2180, 2067, 5562, 11328, 6885, 11517,
307 6912, 2743, 3903, 11091, 3340, 9255, 10100, 4954, 7730, 6371,
308 9688, 1384, 7220, 2787, 9176, 4822, 4200, 600, 7108, 2771,
309 3907, 9336, 8356, 8216, 8196, 4682, 4180, 9375, 6606, 7966,
310 1138, 10696, 1528, 5485, 11317, 8639, 10012, 6697, 7979, 4651,
311 2420, 7368, 11586, 10433, 3246, 7486, 2825, 10937, 3318, 474,
312 7090, 4524, 5913, 7867, 4635, 9440, 11882, 3453, 5760, 4334,
313 9397, 3098, 10976, 1568, 224, 32, 10538, 3261, 3977, 9346,
314
315 10113, 8467, 11743, 12211, 3500, 500, 1827, 261, 5304, 7780,
316 2867, 10943, 6830, 7998, 11676, 1668, 5505, 2542, 9141, 4817,
317 9466, 6619, 11479, 5151, 4247, 7629, 4601, 5924, 6113, 6140,
318 9655, 6646, 2705, 2142, 306, 7066, 2765, 395, 1812, 3770,
319 11072, 8604, 10007, 11963, 1709, 9022, 4800, 7708, 9879, 6678,
320 954, 5403, 4283, 4123, 589, 8862, 1266, 3692, 2283, 9104,
321 11834, 12224, 7013, 4513, 7667, 6362, 4420, 2387, 341, 7071,
322 9788, 6665, 9730, 1390, 10732, 10311, 1473, 1966, 3792, 7564,
323 11614, 10437, 1491, 213, 1786, 9033, 3046, 9213, 10094, 1442,
324 206, 1785, 255, 1792, 256, 10570, 1510, 7238, 1034, 7170,
325
326 6291, 7921, 11665, 3422, 4000, 2327, 2088, 5565, 795, 10647,
327 1521, 5484, 2539, 7385, 1055, 7173, 8047, 11683, 1669, 1994,
328 3796, 5809, 4341, 9398, 11876, 12230, 10525, 12037, 12253, 3506,
329 4012, 9351, 4847, 2448, 7372, 9831, 3160, 2207, 5582, 2553,
330 7387, 6322, 9681, 1383, 10731, 1533, 219, 5298, 4268, 7632,
331 6357, 9686, 8406, 4712, 9451, 10128, 4958, 5975, 11387, 8649,
332 11769, 6948, 11526, 12180, 1740, 10782, 6807, 2728, 7412, 4570,
333 4164, 4106, 11120, 12122, 8754, 11784, 3439, 5758, 11356, 6889,
334 9762, 11928, 1704, 1999, 10819, 12079, 12259, 7018, 11536, 1648,
335 1991, 2040, 2047, 2048, 10826, 12080, 8748, 8272, 8204, 1172,
336
337 1923, 7297, 2798, 7422, 6327, 4415, 7653, 6360, 11442, 12168,
338 7005, 8023, 9924, 8440, 8228, 2931, 7441, 1063, 3663, 5790,
339 9605, 10150, 1450, 8985, 11817, 10466, 10273, 12001, 3470, 7518,
340 1074, 1909, 7295, 9820, 4914, 702, 5367, 7789, 8135, 9940,
341 1420, 3714, 11064, 12114, 12264, 1752, 5517, 9566, 11900, 1700,
342 3754, 5803, 829, 1874, 7290, 2797, 10933, 5073, 7747, 8129,
343 6428, 6185, 11417, 1631, 233, 5300, 9535, 10140, 11982, 8734,
344 8270, 2937, 10953, 8587, 8249, 2934, 9197, 4825, 5956, 4362,
345 9401, 1343, 3703, 529, 10609, 12049, 6988, 6265, 895, 3639,
346 4031, 4087, 4095, 585, 10617, 8539, 4731, 4187, 9376, 3095,
347
348 9220, 10095, 10220, 1460, 10742, 12068, 1724, 5513, 11321, 6884,
349 2739, 5658, 6075, 4379, 11159, 10372, 8504, 4726, 9453, 3106,
350 7466, 11600, 10435, 8513, 9994, 8450, 9985, 3182, 10988, 8592,
351 2983, 9204, 4826, 2445, 5616, 6069, 867, 3635, 5786, 11360,
352 5134, 2489, 10889, 12089, 1727, 7269, 2794, 9177, 1311, 5454,
353 9557, 6632, 2703, 9164, 10087, 1441, 3717, 531, 3587, 2268,
354 324, 5313, 759, 1864, 5533, 2546, 7386, 9833, 8427, 4715,
355 11207, 1601, 7251, 4547, 11183, 12131, 1733, 10781, 10318, 1474,
356 10744, 5046, 4232, 11138, 10369, 6748, 964, 7160, 4534, 7670,
357 8118, 8182, 4680, 11202, 6867, 981, 8918, 1274, 182, 26,
358
359 7026, 8026, 11680, 12202, 10521, 1503, 7237, 4545, 5916, 9623,
360 8397, 11733, 10454, 3249, 9242, 6587, 941, 1890, 270, 10572,
361 6777, 9746, 6659, 6218, 6155, 6146, 878, 1881, 7291, 11575,
362 12187, 1741, 7271, 8061, 11685, 6936, 4502, 9421, 4857, 4205,
363 7623, 1089, 10689, 1527, 8996, 10063, 11971, 10488, 6765, 2722,
364 3900, 9335, 11867, 6962, 11528, 5158, 4248, 4118, 5855, 2592,
365 5637, 6072, 2623, 7397, 8079, 9932, 4930, 5971, 853, 3633,
366 519, 8852, 11798, 3441, 11025, 1575, 225, 8810, 11792, 12218,
367 3501, 9278, 3081, 9218, 4828, 7712, 8124, 11694, 12204, 3499,
368 4011, 573, 3593, 5780, 7848, 9899, 10192, 1456, 208, 7052,
369
370 2763, 7417, 11593, 10434, 12024, 8740, 11782, 10461, 3250, 5731,
371 7841, 9898, 1414, 202, 3540, 7528, 2831, 2160, 10842, 5060,
372 4234, 4116, 588, 84
373 };
374
375 /**
376 * Bit-reversed indices for n = 1024
377 */
378 static const uint16_t rev_1024[] = {
379 0, 512, 256, 768, 128, 640, 384, 896, 64, 576,
380 320, 832, 192, 704, 448, 960, 32, 544, 288, 800,
381 160, 672, 416, 928, 96, 608, 352, 864, 224, 736,
382 480, 992, 16, 528, 272, 784, 144, 656, 400, 912,
383 80, 592, 336, 848, 208, 720, 464, 976, 48, 560,
384 304, 816, 176, 688, 432, 944, 112, 624, 368, 880,
385 240, 752, 496, 1008, 8, 520, 264, 776, 136, 648,
386 392, 904, 72, 584, 328, 840, 200, 712, 456, 968,
387 40, 552, 296, 808, 168, 680, 424, 936, 104, 616,
388 360, 872, 232, 744, 488, 1000, 24, 536, 280, 792,
389
390 152, 664, 408, 920, 88, 600, 344, 856, 216, 728,
391 472, 984, 56, 568, 312, 824, 184, 696, 440, 952,
392 120, 632, 376, 888, 248, 760, 504, 1016, 4, 516,
393 260, 772, 132, 644, 388, 900, 68, 580, 324, 836,
394 196, 708, 452, 964, 36, 548, 292, 804, 164, 676,
395 420, 932, 100, 612, 356, 868, 228, 740, 484, 996,
396 20, 532, 276, 788, 148, 660, 404, 916, 84, 596,
397 340, 852, 212, 724, 468, 980, 52, 564, 308, 820,
398 180, 692, 436, 948, 116, 628, 372, 884, 244, 756,
399 500, 1012, 12, 524, 268, 780, 140, 652, 396, 908,
400
401 76, 588, 332, 844, 204, 716, 460, 972, 44, 556,
402 300, 812, 172, 684, 428, 940, 108, 620, 364, 876,
403 236, 748, 492, 1004, 28, 540, 284, 796, 156, 668,
404 412, 924, 92, 604, 348, 860, 220, 732, 476, 988,
405 60, 572, 316, 828, 188, 700, 444, 956, 124, 636,
406 380, 892, 252, 764, 508, 1020, 2, 514, 258, 770,
407 130, 642, 386, 898, 66, 578, 322, 834, 194, 706,
408 450, 962, 34, 546, 290, 802, 162, 674, 418, 930,
409 98, 610, 354, 866, 226, 738, 482, 994, 18, 530,
410 274, 786, 146, 658, 402, 914, 82, 594, 338, 850,
411
412 210, 722, 466, 978, 50, 562, 306, 818, 178, 690,
413 434, 946, 114, 626, 370, 882, 242, 754, 498, 1010,
414 10, 522, 266, 778, 138, 650, 394, 906, 74, 586,
415 330, 842, 202, 714, 458, 970, 42, 554, 298, 810,
416 170, 682, 426, 938, 106, 618, 362, 874, 234, 746,
417 490, 1002, 26, 538, 282, 794, 154, 666, 410, 922,
418 90, 602, 346, 858, 218, 730, 474, 986, 58, 570,
419 314, 826, 186, 698, 442, 954, 122, 634, 378, 890,
420 250, 762, 506, 1018, 6, 518, 262, 774, 134, 646,
421 390, 902, 70, 582, 326, 838, 198, 710, 454, 966,
422
423 38, 550, 294, 806, 166, 678, 422, 934, 102, 614,
424 358, 870, 230, 742, 486, 998, 22, 534, 278, 790,
425 150, 662, 406, 918, 86, 598, 342, 854, 214, 726,
426 470, 982, 54, 566, 310, 822, 182, 694, 438, 950,
427 118, 630, 374, 886, 246, 758, 502, 1014, 14, 526,
428 270, 782, 142, 654, 398, 910, 78, 590, 334, 846,
429 206, 718, 462, 974, 46, 558, 302, 814, 174, 686,
430 430, 942, 110, 622, 366, 878, 238, 750, 494, 1006,
431 30, 542, 286, 798, 158, 670, 414, 926, 94, 606,
432 350, 862, 222, 734, 478, 990, 62, 574, 318, 830,
433
434 190, 702, 446, 958, 126, 638, 382, 894, 254, 766,
435 510, 1022, 1, 513, 257, 769, 129, 641, 385, 897,
436 65, 577, 321, 833, 193, 705, 449, 961, 33, 545,
437 289, 801, 161, 673, 417, 929, 97, 609, 353, 865,
438 225, 737, 481, 993, 17, 529, 273, 785, 145, 657,
439 401, 913, 81, 593, 337, 849, 209, 721, 465, 977,
440 49, 561, 305, 817, 177, 689, 433, 945, 113, 625,
441 369, 881, 241, 753, 497, 1009, 9, 521, 265, 777,
442 137, 649, 393, 905, 73, 585, 329, 841, 201, 713,
443 457, 969, 41, 553, 297, 809, 169, 681, 425, 937,
444
445 105, 617, 361, 873, 233, 745, 489, 1001, 25, 537,
446 281, 793, 153, 665, 409, 921, 89, 601, 345, 857,
447 217, 729, 473, 985, 57, 569, 313, 825, 185, 697,
448 441, 953, 121, 633, 377, 889, 249, 761, 505, 1017,
449 5, 517, 261, 773, 133, 645, 389, 901, 69, 581,
450 325, 837, 197, 709, 453, 965, 37, 549, 293, 805,
451 165, 677, 421, 933, 101, 613, 357, 869, 229, 741,
452 485, 997, 21, 533, 277, 789, 149, 661, 405, 917,
453 85, 597, 341, 853, 213, 725, 469, 981, 53, 565,
454 309, 821, 181, 693, 437, 949, 117, 629, 373, 885,
455
456 245, 757, 501, 1013, 13, 525, 269, 781, 141, 653,
457 397, 909, 77, 589, 333, 845, 205, 717, 461, 973,
458 45, 557, 301, 813, 173, 685, 429, 941, 109, 621,
459 365, 877, 237, 749, 493, 1005, 29, 541, 285, 797,
460 157, 669, 413, 925, 93, 605, 349, 861, 221, 733,
461 477, 989, 61, 573, 317, 829, 189, 701, 445, 957,
462 125, 637, 381, 893, 253, 765, 509, 1021, 3, 515,
463 259, 771, 131, 643, 387, 899, 67, 579, 323, 835,
464 195, 707, 451, 963, 35, 547, 291, 803, 163, 675,
465 419, 931, 99, 611, 355, 867, 227, 739, 483, 995,
466
467 19, 531, 275, 787, 147, 659, 403, 915, 83, 595,
468 339, 851, 211, 723, 467, 979, 51, 563, 307, 819,
469 179, 691, 435, 947, 115, 627, 371, 883, 243, 755,
470 499, 1011, 11, 523, 267, 779, 139, 651, 395, 907,
471 75, 587, 331, 843, 203, 715, 459, 971, 43, 555,
472 299, 811, 171, 683, 427, 939, 107, 619, 363, 875,
473 235, 747, 491, 1003, 27, 539, 283, 795, 155, 667,
474 411, 923, 91, 603, 347, 859, 219, 731, 475, 987,
475 59, 571, 315, 827, 187, 699, 443, 955, 123, 635,
476 379, 891, 251, 763, 507, 1019, 7, 519, 263, 775,
477
478 135, 647, 391, 903, 71, 583, 327, 839, 199, 711,
479 455, 967, 39, 551, 295, 807, 167, 679, 423, 935,
480 103, 615, 359, 871, 231, 743, 487, 999, 23, 535,
481 279, 791, 151, 663, 407, 919, 87, 599, 343, 855,
482 215, 727, 471, 983, 55, 567, 311, 823, 183, 695,
483 439, 951, 119, 631, 375, 887, 247, 759, 503, 1015,
484 15, 527, 271, 783, 143, 655, 399, 911, 79, 591,
485 335, 847, 207, 719, 463, 975, 47, 559, 303, 815,
486 175, 687, 431, 943, 111, 623, 367, 879, 239, 751,
487 495, 1007, 31, 543, 287, 799, 159, 671, 415, 927,
488
489 95, 607, 351, 863, 223, 735, 479, 991, 63, 575,
490 319, 831, 191, 703, 447, 959, 127, 639, 383, 895,
491 255, 767, 511, 1023
492 };
493
494 const ntt_fft_params_t ntt_fft_12289_1024 = {
495 12289, 12287, 18, 3186, (1<<18)-1, 1024, 12277, 10,
496 wr_12289_1024, wf_12289_1024, wi_12289_1024, 1, rev_1024
497 };
498
499 /**
500 * FFT phase shift and scaling inverse transform for q = 12289 and n = 512
501 */
502 static const uint16_t wi_12289_512[] = {
503 12265, 6771, 11424, 9011, 6203, 11914, 9021, 6454, 7154, 146,
504 11038, 4238, 5604, 10397, 11498, 3495, 7846, 7684, 1160, 4538,
505 845, 2776, 3317, 5836, 6389, 11667, 6508, 1136, 11309, 12269,
506 11787, 9520, 5461, 3121, 5832, 1373, 1282, 10058, 4218, 5102,
507 7628, 4670, 6616, 1389, 9057, 2442, 2307, 5063, 7878, 10945,
508 10506, 716, 767, 3276, 3578, 1327, 5043, 7376, 8176, 3678,
509 3837, 6599, 4649, 4860, 11385, 9261, 189, 3515, 8348, 10453,
510 7988, 1417, 7302, 1403, 2035, 8067, 2171, 6565, 11169, 8755,
511 4693, 10880, 2730, 7078, 3154, 10347, 10243, 2717, 3065, 9342,
512 3451, 1826, 4050, 3343, 1573, 6302, 881, 11053, 10759, 10753,
513
514 3229, 6085, 11410, 3744, 578, 12050, 7519, 3163, 9344, 5959,
515 874, 2275, 1802, 10821, 2478, 10584, 216, 506, 7785, 4924,
516 5618, 3375, 4834, 3359, 9348, 10975, 11259, 11014, 11009, 4739,
517 7119, 5412, 3120, 4578, 1849, 8314, 4684, 11883, 7014, 8921,
518 3944, 5598, 2873, 2065, 8820, 180, 4518, 343, 7, 8778,
519 8957, 12221, 751, 7790, 11194, 3238, 5082, 7126, 1901, 12077,
520 4510, 2600, 3815, 3589, 2832, 12096, 3758, 5845, 5386, 7383,
521 4665, 346, 3769, 7350, 150, 3765, 2334, 2054, 7315, 5416,
522 8136, 2674, 10588, 5232, 10891, 4235, 1842, 11825, 8016, 11951,
523 6263, 1131, 5039, 2360, 10080, 7228, 6919, 392, 8, 10032,
524
525 8481, 5189, 6125, 125, 9282, 1945, 5808, 8144, 417, 6780,
526 10421, 4727, 4360, 11124, 1481, 1535, 7806, 6680, 7911, 3171,
527 7087, 2151, 6063, 8400, 1927, 7814, 4423, 4103, 8360, 923,
528 2276, 3056, 10345, 7735, 3669, 4840, 10883, 6492, 5650, 6636,
529 1891, 11826, 9270, 11475, 11520, 6505, 9663, 448, 8787, 7954,
530 7937, 11197, 7000, 3654, 10608, 5734, 1371, 11063, 11010, 5993,
531 6643, 10669, 8494, 9202, 12226, 7021, 5410, 612, 5530, 3624,
532 9855, 7725, 3418, 9600, 7469, 1908, 8566, 1178, 2532, 4566,
533 11379, 1737, 3045, 8840, 682, 7287, 7171, 9175, 2946, 7584,
534 10939, 2982, 3572, 6092, 7899, 412, 510, 512, 3020, 2068,
535
536 293, 11041, 8000, 4176, 1590, 3042, 5078, 2110, 3805, 3338,
537 7592, 8682, 11463, 8761, 12217, 8024, 9694, 2455, 6320, 11164,
538 2485, 7073, 9173, 438, 8536, 425, 4523, 6613, 9916, 10485,
539 11249, 10763, 3480, 1325, 2535, 8328, 9951, 5219, 6878, 10423,
540 7235, 3408, 9349, 12229, 10783, 3982, 4094, 9363, 5207, 4119,
541 3846, 5596, 365, 3017, 10595, 1721, 7559, 4167, 2593, 7326,
542 6921, 2900, 11345, 8257, 6940, 2148, 2301, 9828, 10734, 3981,
543 2840, 9839, 12239, 11034, 11511, 7508, 1658, 2291, 9577, 3205,
544 567, 10545, 466, 6781, 11675, 4251, 9617, 4209, 6105, 11912,
545 6513, 7406, 8929, 1687, 1790, 8062, 8190, 8945, 9462, 6463,
546
547 6151, 8151, 9195, 3448, 10353, 5478, 12150, 10029, 4719, 6617,
548 2643, 8581, 7699, 7681, 9687, 5966, 9652, 11232, 1734, 11572,
549 10268, 9489, 3454, 5588, 2622, 6825, 5406, 7885, 7434, 7174,
550 648, 1518, 11066, 2483, 4565, 10125, 2213, 10077, 3466, 8347,
551 9199, 8464, 8449, 1928, 9068, 3947, 9360, 1445, 5547, 364,
552 1763, 11071, 8753, 2185, 11832, 4505, 8619, 6195, 1882, 540,
553 1265, 1029, 21, 1756, 2293, 12085, 2253, 11081, 9004, 9714,
554 2957, 9089, 5703, 11653, 1241, 7800, 11445, 10767, 8496, 11710,
555 11274, 5246, 3869, 9860, 1706, 1038, 11307, 9761, 450, 11295,
556 7002, 6162, 9656, 3959, 12119, 8022, 7186, 3407, 8095, 416,
557
558 5526, 10897, 11759, 11275, 6500, 3393, 2828, 7080, 5662, 9395,
559 8468, 1176
560 };
561
562 /**
563 * Bit-reversed indices for n = 512
564 */
565 static const uint16_t rev_512[] = {
566 0, 256, 128, 384, 64, 320, 192, 448, 32, 288,
567 160, 416, 96, 352, 224, 480, 16, 272, 144, 400,
568 80, 336, 208, 464, 48, 304, 176, 432, 112, 368,
569 240, 496, 8, 264, 136, 392, 72, 328, 200, 456,
570 40, 296, 168, 424, 104, 360, 232, 488, 24, 280,
571 152, 408, 88, 344, 216, 472, 56, 312, 184, 440,
572 120, 376, 248, 504, 4, 260, 132, 388, 68, 324,
573 196, 452, 36, 292, 164, 420, 100, 356, 228, 484,
574 20, 276, 148, 404, 84, 340, 212, 468, 52, 308,
575 180, 436, 116, 372, 244, 500, 12, 268, 140, 396,
576
577 76, 332, 204, 460, 44, 300, 172, 428, 108, 364,
578 236, 492, 28, 284, 156, 412, 92, 348, 220, 476,
579 60, 316, 188, 444, 124, 380, 252, 508, 2, 258,
580 130, 386, 66, 322, 194, 450, 34, 290, 162, 418,
581 98, 354, 226, 482, 18, 274, 146, 402, 82, 338,
582 210, 466, 50, 306, 178, 434, 114, 370, 242, 498,
583 10, 266, 138, 394, 74, 330, 202, 458, 42, 298,
584 170, 426, 106, 362, 234, 490, 26, 282, 154, 410,
585 90, 346, 218, 474, 58, 314, 186, 442, 122, 378,
586 250, 506, 6, 262, 134, 390, 70, 326, 198, 454,
587
588 38, 294, 166, 422, 102, 358, 230, 486, 22, 278,
589 150, 406, 86, 342, 214, 470, 54, 310, 182, 438,
590 118, 374, 246, 502, 14, 270, 142, 398, 78, 334,
591 206, 462, 46, 302, 174, 430, 110, 366, 238, 494,
592 30, 286, 158, 414, 94, 350, 222, 478, 62, 318,
593 190, 446, 126, 382, 254, 510, 1, 257, 129, 385,
594 65, 321, 193, 449, 33, 289, 161, 417, 97, 353,
595 225, 481, 17, 273, 145, 401, 81, 337, 209, 465,
596 49, 305, 177, 433, 113, 369, 241, 497, 9, 265,
597 137, 393, 73, 329, 201, 457, 41, 297, 169, 425,
598
599 105, 361, 233, 489, 25, 281, 153, 409, 89, 345,
600 217, 473, 57, 313, 185, 441, 121, 377, 249, 505,
601 5, 261, 133, 389, 69, 325, 197, 453, 37, 293,
602 165, 421, 101, 357, 229, 485, 21, 277, 149, 405,
603 85, 341, 213, 469, 53, 309, 181, 437, 117, 373,
604 245, 501, 13, 269, 141, 397, 77, 333, 205, 461,
605 45, 301, 173, 429, 109, 365, 237, 493, 29, 285,
606 157, 413, 93, 349, 221, 477, 61, 317, 189, 445,
607 125, 381, 253, 509, 3, 259, 131, 387, 67, 323,
608 195, 451, 35, 291, 163, 419, 99, 355, 227, 483,
609
610 19, 275, 147, 403, 83, 339, 211, 467, 51, 307,
611 179, 435, 115, 371, 243, 499, 11, 267, 139, 395,
612 75, 331, 203, 459, 43, 299, 171, 427, 107, 363,
613 235, 491, 27, 283, 155, 411, 91, 347, 219, 475,
614 59, 315, 187, 443, 123, 379, 251, 507, 7, 263,
615 135, 391, 71, 327, 199, 455, 39, 295, 167, 423,
616 103, 359, 231, 487, 23, 279, 151, 407, 87, 343,
617 215, 471, 55, 311, 183, 439, 119, 375, 247, 503,
618 15, 271, 143, 399, 79, 335, 207, 463, 47, 303,
619 175, 431, 111, 367, 239, 495, 31, 287, 159, 415,
620
621 95, 351, 223, 479, 63, 319, 191, 447, 127, 383,
622 255, 511
623 };
624
625 const ntt_fft_params_t ntt_fft_12289_512 = {
626 12289, 12287, 18, 3186, (1<<18)-1, 512, 12265, 9,
627 wr_12289_1024, wf_12289_1024, wi_12289_512, 2, rev_512
628 };
629
630 /**
631 * FFT twiddle factors in Montgomery form for q = 17 and n = 8
632 */
633 static const uint16_t wr_17_8[] = { 15, 16, 8, 4, 2, 1, 9, 13, 15 };
634
635 /**
636 * FFT phase shift in forward transform for q = 17 and n = 8
637 */
638 static const uint16_t wf_17_8[] = { 4, 12, 2, 6, 1, 3, 9, 10 };
639
640 /**
641 * FFT phase shift and scaling inverse transform for q = 17 and n = 8
642 */
643 static const uint16_t wi_17_8[] = { 15, 5, 13, 10, 9, 3, 1, 6 };
644
645 /**
646 * Bit-reversed indices for n = 8
647 */
648 static const uint16_t rev_8[] = { 0, 4, 2, 6, 1, 5, 3, 7 };
649
650 const ntt_fft_params_t ntt_fft_17_8 = {
651 17, 15, 5, 4, (1<<5)-1, 8, 15, 3, wr_17_8, wf_17_8, wi_17_8, 1, rev_8
652 };