summaryrefslogtreecommitdiff
path: root/src/libstrongswan/math/libnttfft/ntt_fft_params.c
blob: 4daac272a19d9da7a56b4aea3ea041cbc9709bc1 (plain)
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
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
/*
 * Copyright (C) 2014-2016 Andreas Steffen
 * HSR Hochschule fuer Technik Rapperswil
 *
 * This program is free software; you can redistribute it and/or modify it
 * under the terms of the GNU General Public License as published by the
 * Free Software Foundation; either version 2 of the License, or (at your
 * option) any later version.  See <http://www.fsf.org/copyleft/gpl.txt>.
 *
 * This program is distributed in the hope that it will be useful, but
 * WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
 * or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 * for more details.
 */

#include "ntt_fft_params.h"

/**
 * FFT twiddle factors in Montgomery form for q = 12289 and n = 1024
 */
static const uint16_t wr_12289_1024[] = {
	 4075,  3051,  2031,  1207,  9987, 10092,  2948,  9273, 11973,  9094,
	 3202,  9430,  7377,  5092,  3728, 10626,  4536,  1062,  2882,  6039,
	  975, 10908,  6065,  2249, 11889,  4978, 10431,  7270, 12138,  4890,
	 6119,  4895,  6364,  4611,  4737, 10911,  6212,  9452,  8455,  8758,
	11316,  1479, 11026, 11847,  2920,  7901,  6190,  8374,  4789,  1170,
	 8174,  7278,   241, 11809,  1058,  2686,  8724,  9650,  5868,  4885,
	 5874,  5179,  7991, 10600,  3262,    81,  3969, 10146,  5594,  3748,
	11606,  3400,  6843,  3504, 11939,  7428,  7591,  3289,  1404,  7351,
	 3818,  2747, 11713,  8643,  5681,  8011, 11580,  2126,  5862,  4591,
	 3757, 12047,   431,  8830,  2555,  2305,  2344,  4255, 11871,  4096,

	 4080,  3296,  1747, 11869,  3998, 11567,  1489, 11516, 11279, 11955,
	 8212,  9140,  5456,  9275, 12071,  1607,  5009, 11950,  7967,  9424,
	 7083,  2975, 10596,  3066,  2766,   355,  5106,  4414,  7373,  4896,
	 6413,  7012, 11785, 12171,  6507, 11618,  3988, 11077,  2057,  2481,
	10968,  9005, 11130,  4654,  6844,  3553,  2051,  2187,  8851,  3584,
	 3570,  2884,  6137,  5777,   426,  8585,  2839,  3932,  8333,  2780,
	 1041,  1853,  4774,   435,  9026, 12159,  5919,  7384,  5435,  8246,
	10806,  1067,  3127,  5755, 11637,  4919,  7540,   790,  1843,  4284,
	 1003, 12280, 11848,  2969, 10302,   949,  9634,  5084,  3336,  3707,
	 9597,  3271,   522,  1000, 12133,  4645,  6403,  6522,    64,  3136,

	 6196,  8668,  6906,  6591,  3445,  9048,   948,  9585,  2683,  8577,
	 2447,  9302,  1105,  4989, 10970,  9103,  3643,  6461,  9364,  4143,
	 6383,  5542,  1200,  9644,  5574,  2768,   453,  9908,  6221,  9893,
	 5486, 10745, 10367,  4134,  5942,  8511, 11502, 10593,  2919,  7852,
	 3789,  1326,  3529,   875,  6008, 11745, 10211,  8779,    56,  2744,
	11566,  1440,  9115,  4231, 10695,  7917,  6974,  9923,  6956,  9041,
	  605,  5067,  2503, 12046,   382,  6429,  7796,  1045,  2049,  2089,
	 4049,  1777,  1050,  2294,  1805,  2422,  8077,  2525,   835,  4048,
	 1728, 10938,  7535,   545,  2127,  5911,  6992, 10805,  1018,   726,
	10996, 10377,  4624,  5374,  5257, 11813,  1254,     1,    49,  2401,

	 7048,  1260,   295,  2166,  7822,  2319,  3030,  1002, 12231,  9447,
	 8210,  9042,   654,  7468,  9551,  1017,   677,  8595,  3329,  3364,
	 5079,  3091,  3991, 11224,  9260, 11336,  2459,  9890,  5339,  3542,
	 1512,   354,  5057,  2013,   325,  3636,  6118,  4846,  3963,  9852,
	 3477, 10616,  4046,  1630,  6136,  5728, 10314,  1537,  1579,  3637,
	 6167,  7247, 11011, 11112,  3772,   493, 11868,  3949,  9166,  6730,
	10256, 10984,  9789,   390,  6821,  2426,  8273, 12129,  4449,  9088,
	 2908,  7313,  1956,  9821,  1958,  9919,  6760, 11726,  9280,    27,
	 1323,  3382,  5961,  9442,  7965,  9326,  2281,  1168,  8076,  2476,
	10723,  9289,   468, 10643,  5369,  5012, 12097,  2881,  5990, 10863,

	 3860,  4805,  1954,  9723,  9445,  8112,  4240, 11136,  4948,  8961,
	 8974,  9611,  3957,  9558,  1360,  5195,  8775, 12149,  5429,  7952,
	 8689,  7935,  7856,  3985, 10930,  7143,  5915,  7188,  8120,  4632,
	 5766, 12176,  6752, 11334,  2361,  5088,  3532,  1022,   922,  8311,
	 1702,  9664,  6554,  1632,  6234, 10530, 12121,  4057,  2169,  7969,
	 9522, 11885,  4782,   827,  3656,  7098,  3710,  9744, 10474,  9377,
	 4780,   729, 11143,  5291,  1190,  9154,  6142,  6022,   142,  6958,
	 9139,  5407,  6874,  5023,   347,  4714,  9784,   145,  7105,  4053,
	 1973, 10654,  5908,  6845,  3602,  4452,  9235, 10111,  3879,  5736,
	10706,  8456,  8807,  1428,  8527, 12286, 12142,  5086,  3434,  8509,

	11404,  5791,  1112,  5332,  3199,  9283,   174,  8526, 12237,  9741,
	10327,  2174,  8214,  9238, 10258, 11082,  2302,  2197,  9341,  3016,
	  316,  3195,  9087,  2859,  4912,  7197,  8561,  1663,  7753, 11227,
	 9407,  6250, 11314,  1381,  6224, 10040,   400,  7311,  1858,  5019,
	  151,  7399,  6170,  7394,  5925,  7678,  7552,  1378,  6077,  2837,
	 3834,  3531,   973, 10810,  1263,   442,  9369,  4388,  6099,  3915,
	 7500, 11119,  4115,  5011, 12048,   480, 11231,  9603,  3565,  2639,
	 6421,  7404,  6415,  7110,  4298,  1689,  9027, 12208,  8320,  2143,
	 6695,  8541,   683,  8889,  5446,  8785,   350,  4861,  4698,  9000,
	10885,  4938,  8471,  9542,   576,  3646,  6608,  4278,   709, 10163,

	 6427,  7698,  8532,   242, 11858,  3459,  9734,  9984,  9945,  8034,
	  418,  8193,  8209,  8993, 10542,   420,  8291,   722, 10800,   773,
	 1010,   334,  4077,  3149,  6833,  3014,   218, 10682,  7280,   339,
	 4322,  2865,  5206,  9314,  1693,  9223,  9523, 11934,  7183,  7875,
	 4916,  7393,  5876,  5277,   504,   118,  5782,   671,  8301,  1212,
	10232,  9808,  1321,  3284,  1159,  7635,  5445,  8736, 10238, 10102,
	 3438,  8705,  8719,  9405,  6152,  6512, 11863,  3704,  9450,  8357,
	 3956,  9509, 11248, 10436,  7515, 11854,  3263,   130,  6370,  4905,
	 6854,  4043,  1483, 11222,  9162,  6534,   652,  7370,  4749, 11499,
	10446,  8005, 11286,     9,   441,  9320,  1987, 11340,  2655,  7205,

	 8953,  8582,  2692,  9018, 11767, 11289,   156,  7644,  5886,  5767,
	12225,  9153,  6093,  3621,  5383,  5698,  8844,  3241, 11341,  2704,
	 9606,  3712,  9842,  2987, 11184,  7300,  1319,  3186,  8646,  5828,
	 2925,  8146,  5906,  6747, 11089,  2645,  6715,  9521, 11836,  2381,
	 6068,  2396,  6803,  1544,  1922,  8155,  6347,  3778,   787,  1696,
	 9370,  4437,  8500, 10963,  8760, 11414,  6281,   544,  2078,  3510,
	12233,  9545,   723, 10849,  3174,  8058,  1594,  4372,  5315,  2366,
	 5333,  3248, 11684,  7222,  9786,   243, 11907,  5860,  4493, 11244,
	10240, 10200,  8240, 10512, 11239,  9995, 10484,  9867,  4212,  9764,
	11454,  8241, 10561,  1351,  4754, 11744, 10162,  6378,  5297,  1484,

	11271, 11563,  1293,  1912,  7665,  6915,  7032,   476, 11035, 12288,
	12240,  9888,  5241, 11029, 11994, 10123,  4467,  9970,  9259, 11287,
	   58,  2842,  4079,  3247, 11635,  4821,  2738, 11272, 11612,  3694,
	 8960,  8925,  7210,  9198,  8298,  1065,  3029,   953,  9830,  2399,
	 6950,  8747, 10777, 11935,  7232, 10276, 11964,  8653,  6171,  7443,
	 8326,  2437,  8812,  1673,  8243, 10659,  6153,  6561,  1975, 10752,
	10710,  8652,  6122,  5042,  1278,  1177,  8517, 11796,   421,  8340,
	 3123,  5559,  2033,  1305,  2500, 11899,  5468,  9863,  4016,   160,
	 7840,  3201,  9381,  4976, 10333,  2468, 10331,  2370,  5529,   563,
	 3009, 12262, 10966,  8907,  6328,  2847,  4324,  2963, 10008, 11121,

	 4213,  9813,  1566,  3000, 11821,  1646,  6920,  7277,   192,  9408,
	 6299,  1426,  8429,  7484, 10335,  2566,  2844,  4177,  8049,  1153,
	 7341,  3328,  3315,  2678,  8332,  2731, 10929,  7094,  3514,   140,
	 6860,  4337,  3600,  4354,  4433,  8304,  1359,  5146,  6374,  5101,
	 4169,  7657,  6523,   113,  5537,   955,  9928,  7201,  8757, 11267,
	11367,  3978, 10587,  2625,  5735, 10657,  6055,  1759,   168,  8232,
	10120,  4320,  2767,   404,  7507, 11462,  8633,  5191,  8579,  2545,
	 1815,  2912,  7509, 11560,  1146,  6998, 11099,  3135,  6147,  6267,
	12147,  5331,  3150,  6882,  5415,  7266, 11942,  7575,  2505, 12144,
	 5184,  8236, 10316,  1635,  6381,  5444,  8687,  7837,  3054,  2178,

	 8410,  6553,  1583,  3833,  3482, 10861,  3762,     3,   147,  7203,
	 8855,  3780,   885,  6498, 11177,  6957,  9090,  3006, 12115,  3763,
	   52,  2548,  1962, 10115,  4075
};

/**
 * FFT phase shift in forward transform for q = 12289 and n = 1024
 */
static const uint16_t wf_12289_1024[] = {
	 3186, 10013,  8646, 11366,  5828,  3929,  2925,  8186,  8146,  7866,
	 5906,  4475,  6747, 10362, 11089,  3889,  2645,  6226,  6715, 10138,
	 9521,  5202, 11836,  9118,  2381,  4378,  6068,  5609,  2396,  4483,
	 6803, 10754,  1544, 10808,  1922,  1165,  8155,  7929,  6347,  7562,
	 3778,  1868,   787,  5509,  1696, 11872,  9370,  4145,  4437,  6481,
	 8500, 10344, 10963,  3007,  8760, 12164, 11414,  6164,  6281,  7100,
	  544,  3808,  2078,  2257,  3510, 12281, 12233, 11897,  9545,  5370,
	  723,  5061, 10849,  2209,  3174,  9929,  8058,  7250,  1594, 11158,
	 4372,  6026,  5315,   338,  2366,  4273,  5333,   464,  3248, 10447,
	11684,  8054,  7222,  1398,  9786,  7057,   243,  1701, 11907,  9615,

	 5860,  4153,  4493,  6873, 11244,  4974, 10240, 10235, 10200,  9955,
	 8240,  8524, 10512, 12139, 11239,  4939,  9995,  8520, 10484, 11943,
	 9867,  7624,  4212,  4906,  9764,  6903, 11454,  6444,  8241,  8531,
	10561,   193,  1351,  9457,  4754,  8700, 11744,  8474, 10162,  9689,
	 6378,  7779,  5297,   212,  1484, 10388, 11271,  5163, 11563,  7207,
	 1293,  9051,  1912,  1095,  7665,  4499,  6915, 11538,  7032,    68,
	  476,  3332, 11035,  3511, 12288, 12282, 12240, 11946,  9888,  7771,
	 5241, 12109, 11029,  3469, 11994, 10224, 10123,  9416,  4467,  6691,
	 9970,  8345,  9259,  3368, 11287,  5275,    58,   406,  2842,  7605,
	 4079,  3975,  3247, 10440, 11635,  7711,  4821,  9169,  2738,  6877,

	11272,  5170, 11612,  7550,  3694,  1280,  8960,  1275,  8925,  1030,
	 7210,  1314,  9198,  2941,  8298,  8930,  1065,  7455,  3029,  8914,
	  953,  6671,  9830,  7365,  2399,  4504,  6950, 11783,  8747, 12073,
	10777,  1705, 11935,  9811,  7232,  1468, 10276, 10487, 11964, 10014,
	 8653, 11415,  6171,  6330,  7443,  2945,  8326,  9126,  2437,  4770,
	 8812,   239,  1673, 11711,  8243,  8545, 10659,   879,  6153,  6204,
	 6561,  9060,  1975,  1536, 10752,  1530, 10710,  1236,  8652, 11408,
	 6122,  5987,  5042, 10716,  1278,  8946,  1177,  8239,  8517, 10463,
	11796,  8838,   421,  2947,  8340,  9224,  3123,  9572,  5559,  2046,
	 2033,  1942,  1305,  9135,  2500,  5211, 11899,  9559,  5468,  1409,

	 9863,  7596,  4016,  3534,   160,  1120,  7840,  5724,  3201, 10118,
	 9381,  4222,  4976, 10254, 10333, 10886,  2468,  4987, 10331, 10872,
	 2370,  4301,  5529,  1836,   563,  3941,  3009,  8774, 12262, 12100,
	10966,  3028,  8907,   904,  6328,  7429,  2847,  7640,  4324,  5690,
	 2963,  8452, 10008,  8611, 11121,  4113,  4213,  4913,  9813,  7246,
	 1566, 10962,  3000,  8711, 11821,  9013,  1646, 11522,  6920, 11573,
	 7277,  1783,   192,  1344,  9408,  4411,  6299,  7226,  1426,  9982,
	 8429,  9847,  7484,  3232, 10335, 10900,  2566,  5673,  2844,  7619,
	 4177,  4661,  8049,  7187,  1153,  8071,  7341,  2231,  3328, 11007,
	 3315, 10916,  2678,  6457,  8332,  9168,  2731,  6828, 10929,  2769,

	 7094,   502,  3514,    20,   140,   980,  6860, 11153,  4337,  5781,
	 3600,   622,  4354,  5900,  4433,  6453,  8304,  8972,  1359,  9513,
	 5146, 11444,  6374,  7751,  5101, 11129,  4169,  4605,  7657,  4443,
	 6523,  8794,   113,   791,  5537,  1892,   955,  6685,  9928,  8051,
	 7201,  1251,  8757, 12143, 11267,  5135, 11367,  5835,  3978,  3268,
	10587,   375,  2625,  6086,  5735,  3278, 10657,   865,  6055,  5518,
	 1759,    24,   168,  1176,  8232,  8468, 10120,  9395,  4320,  5662,
	 2767,  7080,   404,  2828,  7507,  3393, 11462,  6500,  8633, 11275,
	 5191, 11759,  8579, 10897,  2545,  5526,  1815,   416,  2912,  8095,
	 7509,  3407, 11560,  7186,  1146,  8022,  6998, 12119, 11099,  3959,

	 3135,  9656,  6147,  6162,  6267,  7002, 12147, 11295,  5331,   450,
	 3150,  9761,  6882, 11307,  5415,  1038,  7266,  1706, 11942,  9860,
	 7575,  3869,  2505,  5246, 12144, 11274,  5184, 11710,  8236,  8496,
	10316, 10767,  1635, 11445,  6381,  7800,  5444,  1241,  8687, 11653,
	 7837,  5703,  3054,  9089,  2178,  2957,  8410,  9714,  6553,  9004,
	 1583, 11081,  3833,  2253,  3482, 12085, 10861,  2293,  3762,  1756,
	    3,    21,   147,  1029,  7203,  1265,  8855,   540,  3780,  1882,
	  885,  6195,  6498,  8619, 11177,  4505,  6957, 11832,  9090,  2185,
	 3006,  8753, 12115, 11071,  3763,  1763,    52,   364,  2548,  5547,
	 1962,  1445, 10115,  9360,  4075,  3947,  3051,  9068,  2031,  1928,

	 1207,  8449,  9987,  8464, 10092,  9199,  2948,  8347,  9273,  3466,
	11973, 10077,  9094,  2213,  3202, 10125,  9430,  4565,  7377,  2483,
	 5092, 11066,  3728,  1518, 10626,   648,  4536,  7174,  1062,  7434,
	 2882,  7885,  6039,  5406,   975,  6825, 10908,  2622,  6065,  5588,
	 2249,  3454, 11889,  9489,  4978, 10268, 10431, 11572,  7270,  1734,
	12138, 11232,  4890,  9652,  6119,  5966,  4895,  9687,  6364,  7681,
	 4611,  7699,  4737,  8581, 10911,  2643,  6212,  6617,  9452,  4719,
	 8455, 10029,  8758, 12150, 11316,  5478,  1479, 10353, 11026,  3448,
	11847,  9195,  2920,  8151,  7901,  6151,  6190,  6463,  8374,  9462,
	 4789,  8945,  1170,  8190,  8174,  8062,  7278,  1790,   241,  1687,

	11809,  8929,  1058,  7406,  2686,  6513,  8724, 11912,  9650,  6105,
	 5868,  4209,  4885,  9617,  5874,  4251,  5179, 11675,  7991,  6781,
	10600,   466,  3262, 10545,    81,   567,  3969,  3205, 10146,  9577,
	 5594,  2291,  3748,  1658, 11606,  7508,  3400, 11511,  6843, 11034,
	 3504, 12239, 11939,  9839,  7428,  2840,  7591,  3981,  3289, 10734,
	 1404,  9828,  7351,  2301,  3818,  2148,  2747,  6940, 11713,  8257,
	 8643, 11345,  5681,  2900,  8011,  6921, 11580,  7326,  2126,  2593,
	 5862,  4167,  4591,  7559,  3757,  1721, 12047, 10595,   431,  3017,
	 8830,   365,  2555,  5596,  2305,  3846,  2344,  4119,  4255,  5207,
	11871,  9363,  4096,  4094,  4080,  3982,  3296, 10783,  1747, 12229,

	11869,  9349,  3998,  3408, 11567,  7235,  1489, 10423, 11516,  6878,
	11279,  5219, 11955,  9951,  8212,  8328,  9140,  2535,  5456,  1325,
	 9275,  3480, 12071, 10763,  1607, 11249,  5009, 10485, 11950,  9916,
	 7967,  6613,  9424,  4523,  7083,   425,  2975,  8536, 10596,   438,
	 3066,  9173,  2766,  7073,   355,  2485,  5106, 11164,  4414,  6320,
	 7373,  2455,  4896,  9694,  6413,  8024,  7012, 12217, 11785,  8761,
	12171, 11463,  6507,  8682, 11618,  7592,  3988,  3338, 11077,  3805,
	 2057,  2110,  2481,  5078, 10968,  3042,  9005,  1590, 11130,  4176,
	 4654,  8000,  6844, 11041,  3553,   293,  2051,  2068,  2187,  3020,
	 8851,   512,  3584,   510,  3570,   412,  2884,  7899,  6137,  6092,

	 5777,  3572,   426,  2982,  8585, 10939,  2839,  7584,  3932,  2946,
	 8333,  9175,  2780,  7171,  1041,  7287,  1853,   682,  4774,  8840,
	  435,  3045,  9026,  1737, 12159, 11379,  5919,  4566,  7384,  2532,
	 5435,  1178,  8246,  8566, 10806,  1908,  1067,  7469,  3127,  9600,
	 5755,  3418, 11637,  7725,  4919,  9855,  7540,  3624,   790,  5530,
	 1843,   612,  4284,  5410,  1003,  7021, 12280, 12226, 11848,  9202,
	 2969,  8494, 10302, 10669,   949,  6643,  9634,  5993,  5084, 11010,
	 3336, 11063,  3707,  1371,  9597,  5734,  3271, 10608,   522,  3654,
	 1000,  7000, 12133, 11197,  4645,  7937,  6403,  7954,  6522,  8787,
	   64,   448,  3136,  9663,  6196,  6505,  8668, 11520,  6906, 11475,

	 6591,  9270,  3445, 11826,  9048,  1891,   948,  6636,  9585,  5650,
	 2683,  6492,  8577, 10883,  2447,  4840,  9302,  3669,  1105,  7735,
	 4989, 10345, 10970,  3056
};

/**
 * FFT phase shift and scaling inverse transform for q = 12289 and n = 1024
 */
static const uint16_t wi_12289_1024[] = {
	12277,  5265,  9530,  3117,  5712,   816, 10650,  3277,  9246,  4832,
	 5957,   851, 10655, 10300,  3227,   461,  3577,   511,    73,  1766,
	 5519,  2544,  2119,  7325,  2802,  5667, 11343,  3376,  5749,  6088,
	 7892,  2883,  3923,  2316,  3842,  4060,   580,  3594,  2269,  9102,
	 6567,  9716,  1388,  5465,  7803,  8137,  2918,  3928,  9339, 10112,
	11978, 10489,  3254,  3976,   568,  8859, 11799, 12219, 12279, 10532,
	12038,  8742,  4760,   680,  8875,  4779,  7705,  8123,  2916, 10950,
	 6831,  4487,   641, 10625,  5029,  2474,  2109,  5568,  2551,  2120,
	 3814,  4056,  2335, 10867,  3308, 11006,  6839,   977, 10673,  8547,
	 1221,  1930,  7298, 11576,  8676,  2995,  3939,  7585, 11617, 12193,

	 5253,  2506,   358,  8829,  6528, 11466,  1638,   234,  1789, 10789,
	 6808, 11506,  8666,  1238,  3688,  4038,  4088,   584,  1839,  7285,
	 8063,  4663,  9444, 10127,  8469,  4721,  2430,  9125, 11837,  1691,
	10775,  6806,  6239,  6158,  7902,  4640,  4174,  5863, 11371,  3380,
	 3994, 11104,  6853,   979,  3651, 11055,  6846,   978,  7162,  9801,
	10178,  1454,  7230,  4544,  9427,  8369, 11729, 12209, 10522, 10281,
	 8491,  1213,  5440,  9555,  1365,   195,  3539, 11039,  1577,  5492,
	11318,  5128, 11266,  3365,  7503,  4583,  7677,  8119,  4671,  5934,
	 7870,  6391,   913,  1886,  2025,  5556,  7816, 11650,  6931,  9768,
	 3151,  9228,  6585,  7963, 11671,  6934, 11524,  6913, 11521,  5157,

	 7759,  2864,  9187,  3068,  5705,   815,  1872,  2023,   289,  5308,
	 6025,  7883,  9904,  4926,  7726,  8126,  4672,  2423,  9124,  3059,
	  437,  1818,  7282,  6307,   901,  7151, 11555,  8673,  1239,   177,
	 5292,   756,   108,  1771,   253,  8814, 10037,  4945,  2462,  7374,
	 2809,  5668,  7832,  4630,  2417,  5612,  7824,  8140,  4674,  7690,
	11632,  8684, 11774,  1682,  5507,  7809, 11649, 10442,  8514,  6483,
	 9704,  6653,  2706, 10920,  1560,  3734,  2289,   327,  7069,  4521,
	 4157,  4105,  2342, 10868, 12086, 12260,  3507,   501, 10605,  1515,
	 1972,  7304,  2799,  3911,  7581,  1083,  7177,  6292,  4410,   630,
	   90,  3524,  2259,  7345,  6316,  6169,  6148,  6145,  4389,   627,

	10623, 12051, 12255,  8773,  6520,  2687,  3895,  2312,  5597, 11333,
	 1619,  5498,  2541,   363,  3563,   509,  7095, 11547, 12183,  3496,
	 2255,  9100,  1300,  7208,  8052,  6417,  7939,  9912,  1416,  5469,
	 6048,   864,  1879,  2024,  9067,  6562,  2693,  7407,  9836, 10183,
	 8477,  1211,   173,  7047,  8029,  1147,  3675,   525,    75,  7033,
	 8027,  8169,  1167,  7189,  1027,  7169,  9802,  6667,  2708,  3898,
	 4068,  9359,  1337,   191,  5294,  6023,  2616,  7396, 11590,  8678,
	 8262,  6447,   921, 10665, 12057,  3478,  4008, 11106, 12120,  3487,
	 9276, 10103,  6710, 11492,  8664,  8260,  1180, 10702,  5040,   720,
	 3614,  5783,  9604,  1372,   196,    28,     4, 10534,  5016, 11250,

	10385, 12017,  8739,  3004,  9207,  6582,  6207,  7909,  4641,   663,
	 7117,  8039,  2904,  3926,  4072,  7604,  6353, 11441,  3390,  5751,
	11355, 10400,  8508,  2971,  2180,  2067,  5562, 11328,  6885, 11517,
	 6912,  2743,  3903, 11091,  3340,  9255, 10100,  4954,  7730,  6371,
	 9688,  1384,  7220,  2787,  9176,  4822,  4200,   600,  7108,  2771,
	 3907,  9336,  8356,  8216,  8196,  4682,  4180,  9375,  6606,  7966,
	 1138, 10696,  1528,  5485, 11317,  8639, 10012,  6697,  7979,  4651,
	 2420,  7368, 11586, 10433,  3246,  7486,  2825, 10937,  3318,   474,
	 7090,  4524,  5913,  7867,  4635,  9440, 11882,  3453,  5760,  4334,
	 9397,  3098, 10976,  1568,   224,    32, 10538,  3261,  3977,  9346,

	10113,  8467, 11743, 12211,  3500,   500,  1827,   261,  5304,  7780,
	 2867, 10943,  6830,  7998, 11676,  1668,  5505,  2542,  9141,  4817,
	 9466,  6619, 11479,  5151,  4247,  7629,  4601,  5924,  6113,  6140,
	 9655,  6646,  2705,  2142,   306,  7066,  2765,   395,  1812,  3770,
	11072,  8604, 10007, 11963,  1709,  9022,  4800,  7708,  9879,  6678,
	  954,  5403,  4283,  4123,   589,  8862,  1266,  3692,  2283,  9104,
	11834, 12224,  7013,  4513,  7667,  6362,  4420,  2387,   341,  7071,
	 9788,  6665,  9730,  1390, 10732, 10311,  1473,  1966,  3792,  7564,
	11614, 10437,  1491,   213,  1786,  9033,  3046,  9213, 10094,  1442,
	  206,  1785,   255,  1792,   256, 10570,  1510,  7238,  1034,  7170,

	 6291,  7921, 11665,  3422,  4000,  2327,  2088,  5565,   795, 10647,
	 1521,  5484,  2539,  7385,  1055,  7173,  8047, 11683,  1669,  1994,
	 3796,  5809,  4341,  9398, 11876, 12230, 10525, 12037, 12253,  3506,
	 4012,  9351,  4847,  2448,  7372,  9831,  3160,  2207,  5582,  2553,
	 7387,  6322,  9681,  1383, 10731,  1533,   219,  5298,  4268,  7632,
	 6357,  9686,  8406,  4712,  9451, 10128,  4958,  5975, 11387,  8649,
	11769,  6948, 11526, 12180,  1740, 10782,  6807,  2728,  7412,  4570,
	 4164,  4106, 11120, 12122,  8754, 11784,  3439,  5758, 11356,  6889,
	 9762, 11928,  1704,  1999, 10819, 12079, 12259,  7018, 11536,  1648,
	 1991,  2040,  2047,  2048, 10826, 12080,  8748,  8272,  8204,  1172,

	 1923,  7297,  2798,  7422,  6327,  4415,  7653,  6360, 11442, 12168,
	 7005,  8023,  9924,  8440,  8228,  2931,  7441,  1063,  3663,  5790,
	 9605, 10150,  1450,  8985, 11817, 10466, 10273, 12001,  3470,  7518,
	 1074,  1909,  7295,  9820,  4914,   702,  5367,  7789,  8135,  9940,
	 1420,  3714, 11064, 12114, 12264,  1752,  5517,  9566, 11900,  1700,
	 3754,  5803,   829,  1874,  7290,  2797, 10933,  5073,  7747,  8129,
	 6428,  6185, 11417,  1631,   233,  5300,  9535, 10140, 11982,  8734,
	 8270,  2937, 10953,  8587,  8249,  2934,  9197,  4825,  5956,  4362,
	 9401,  1343,  3703,   529, 10609, 12049,  6988,  6265,   895,  3639,
	 4031,  4087,  4095,   585, 10617,  8539,  4731,  4187,  9376,  3095,

	 9220, 10095, 10220,  1460, 10742, 12068,  1724,  5513, 11321,  6884,
	 2739,  5658,  6075,  4379, 11159, 10372,  8504,  4726,  9453,  3106,
	 7466, 11600, 10435,  8513,  9994,  8450,  9985,  3182, 10988,  8592,
	 2983,  9204,  4826,  2445,  5616,  6069,   867,  3635,  5786, 11360,
	 5134,  2489, 10889, 12089,  1727,  7269,  2794,  9177,  1311,  5454,
	 9557,  6632,  2703,  9164, 10087,  1441,  3717,   531,  3587,  2268,
	  324,  5313,   759,  1864,  5533,  2546,  7386,  9833,  8427,  4715,
	11207,  1601,  7251,  4547, 11183, 12131,  1733, 10781, 10318,  1474,
	10744,  5046,  4232, 11138, 10369,  6748,   964,  7160,  4534,  7670,
	 8118,  8182,  4680, 11202,  6867,   981,  8918,  1274,   182,    26,

	 7026,  8026, 11680, 12202, 10521,  1503,  7237,  4545,  5916,  9623,
	 8397, 11733, 10454,  3249,  9242,  6587,   941,  1890,   270, 10572,
	 6777,  9746,  6659,  6218,  6155,  6146,   878,  1881,  7291, 11575,
	12187,  1741,  7271,  8061, 11685,  6936,  4502,  9421,  4857,  4205,
	 7623,  1089, 10689,  1527,  8996, 10063, 11971, 10488,  6765,  2722,
	 3900,  9335, 11867,  6962, 11528,  5158,  4248,  4118,  5855,  2592,
	 5637,  6072,  2623,  7397,  8079,  9932,  4930,  5971,   853,  3633,
	  519,  8852, 11798,  3441, 11025,  1575,   225,  8810, 11792, 12218,
	 3501,  9278,  3081,  9218,  4828,  7712,  8124, 11694, 12204,  3499,
	 4011,   573,  3593,  5780,  7848,  9899, 10192,  1456,   208,  7052,

	 2763,  7417, 11593, 10434, 12024,  8740, 11782, 10461,  3250,  5731,
	 7841,  9898,  1414,   202,  3540,  7528,  2831,  2160, 10842,  5060,
	 4234,  4116,   588,    84
};

/**
 * Bit-reversed indices for n = 1024
 */
static const uint16_t rev_1024[] = {
	   0,  512,  256,  768,  128,  640,  384,  896,   64,  576,
	 320,  832,  192,  704,  448,  960,   32,  544,  288,  800,
	 160,  672,  416,  928,   96,  608,  352,  864,  224,  736,
	 480,  992,   16,  528,  272,  784,  144,  656,  400,  912,
	  80,  592,  336,  848,  208,  720,  464,  976,   48,  560,
	 304,  816,  176,  688,  432,  944,  112,  624,  368,  880,
	 240,  752,  496, 1008,    8,  520,  264,  776,  136,  648,
	 392,  904,   72,  584,  328,  840,  200,  712,  456,  968,
	  40,  552,  296,  808,  168,  680,  424,  936,  104,  616,
	 360,  872,  232,  744,  488, 1000,   24,  536,  280,  792,

	 152,  664,  408,  920,   88,  600,  344,  856,  216,  728,
	 472,  984,   56,  568,  312,  824,  184,  696,  440,  952,
	 120,  632,  376,  888,  248,  760,  504, 1016,    4,  516,
	 260,  772,  132,  644,  388,  900,   68,  580,  324,  836,
	 196,  708,  452,  964,   36,  548,  292,  804,  164,  676,
	 420,  932,  100,  612,  356,  868,  228,  740,  484,  996,
	  20,  532,  276,  788,  148,  660,  404,  916,   84,  596,
	 340,  852,  212,  724,  468,  980,   52,  564,  308,  820,
	 180,  692,  436,  948,  116,  628,  372,  884,  244,  756,
	 500, 1012,   12,  524,  268,  780,  140,  652,  396,  908,

	  76,  588,  332,  844,  204,  716,  460,  972,   44,  556,
	 300,  812,  172,  684,  428,  940,  108,  620,  364,  876,
	 236,  748,  492, 1004,   28,  540,  284,  796,  156,  668,
	 412,  924,   92,  604,  348,  860,  220,  732,  476,  988,
	  60,  572,  316,  828,  188,  700,  444,  956,  124,  636,
	 380,  892,  252,  764,  508, 1020,    2,  514,  258,  770,
	 130,  642,  386,  898,   66,  578,  322,  834,  194,  706,
	 450,  962,   34,  546,  290,  802,  162,  674,  418,  930,
	  98,  610,  354,  866,  226,  738,  482,  994,   18,  530,
	 274,  786,  146,  658,  402,  914,   82,  594,  338,  850,

	 210,  722,  466,  978,   50,  562,  306,  818,  178,  690,
	 434,  946,  114,  626,  370,  882,  242,  754,  498, 1010,
	  10,  522,  266,  778,  138,  650,  394,  906,   74,  586,
	 330,  842,  202,  714,  458,  970,   42,  554,  298,  810,
	 170,  682,  426,  938,  106,  618,  362,  874,  234,  746,
	 490, 1002,   26,  538,  282,  794,  154,  666,  410,  922,
	  90,  602,  346,  858,  218,  730,  474,  986,   58,  570,
	 314,  826,  186,  698,  442,  954,  122,  634,  378,  890,
	 250,  762,  506, 1018,    6,  518,  262,  774,  134,  646,
	 390,  902,   70,  582,  326,  838,  198,  710,  454,  966,

	  38,  550,  294,  806,  166,  678,  422,  934,  102,  614,
	 358,  870,  230,  742,  486,  998,   22,  534,  278,  790,
	 150,  662,  406,  918,   86,  598,  342,  854,  214,  726,
	 470,  982,   54,  566,  310,  822,  182,  694,  438,  950,
	 118,  630,  374,  886,  246,  758,  502, 1014,   14,  526,
	 270,  782,  142,  654,  398,  910,   78,  590,  334,  846,
	 206,  718,  462,  974,   46,  558,  302,  814,  174,  686,
	 430,  942,  110,  622,  366,  878,  238,  750,  494, 1006,
	  30,  542,  286,  798,  158,  670,  414,  926,   94,  606,
	 350,  862,  222,  734,  478,  990,   62,  574,  318,  830,

	 190,  702,  446,  958,  126,  638,  382,  894,  254,  766,
	 510, 1022,    1,  513,  257,  769,  129,  641,  385,  897,
	  65,  577,  321,  833,  193,  705,  449,  961,   33,  545,
	 289,  801,  161,  673,  417,  929,   97,  609,  353,  865,
	 225,  737,  481,  993,   17,  529,  273,  785,  145,  657,
	 401,  913,   81,  593,  337,  849,  209,  721,  465,  977,
	  49,  561,  305,  817,  177,  689,  433,  945,  113,  625,
	 369,  881,  241,  753,  497, 1009,    9,  521,  265,  777,
	 137,  649,  393,  905,   73,  585,  329,  841,  201,  713,
	 457,  969,   41,  553,  297,  809,  169,  681,  425,  937,

	 105,  617,  361,  873,  233,  745,  489, 1001,   25,  537,
	 281,  793,  153,  665,  409,  921,   89,  601,  345,  857,
	 217,  729,  473,  985,   57,  569,  313,  825,  185,  697,
	 441,  953,  121,  633,  377,  889,  249,  761,  505, 1017,
	   5,  517,  261,  773,  133,  645,  389,  901,   69,  581,
	 325,  837,  197,  709,  453,  965,   37,  549,  293,  805,
	 165,  677,  421,  933,  101,  613,  357,  869,  229,  741,
	 485,  997,   21,  533,  277,  789,  149,  661,  405,  917,
	  85,  597,  341,  853,  213,  725,  469,  981,   53,  565,
	 309,  821,  181,  693,  437,  949,  117,  629,  373,  885,

	 245,  757,  501, 1013,   13,  525,  269,  781,  141,  653,
	 397,  909,   77,  589,  333,  845,  205,  717,  461,  973,
	  45,  557,  301,  813,  173,  685,  429,  941,  109,  621,
	 365,  877,  237,  749,  493, 1005,   29,  541,  285,  797,
	 157,  669,  413,  925,   93,  605,  349,  861,  221,  733,
	 477,  989,   61,  573,  317,  829,  189,  701,  445,  957,
	 125,  637,  381,  893,  253,  765,  509, 1021,    3,  515,
	 259,  771,  131,  643,  387,  899,   67,  579,  323,  835,
	 195,  707,  451,  963,   35,  547,  291,  803,  163,  675,
	 419,  931,   99,  611,  355,  867,  227,  739,  483,  995,

	  19,  531,  275,  787,  147,  659,  403,  915,   83,  595,
	 339,  851,  211,  723,  467,  979,   51,  563,  307,  819,
	 179,  691,  435,  947,  115,  627,  371,  883,  243,  755,
	 499, 1011,   11,  523,  267,  779,  139,  651,  395,  907,
	  75,  587,  331,  843,  203,  715,  459,  971,   43,  555,
	 299,  811,  171,  683,  427,  939,  107,  619,  363,  875,
	 235,  747,  491, 1003,   27,  539,  283,  795,  155,  667,
	 411,  923,   91,  603,  347,  859,  219,  731,  475,  987,
	  59,  571,  315,  827,  187,  699,  443,  955,  123,  635,
	 379,  891,  251,  763,  507, 1019,    7,  519,  263,  775,

	 135,  647,  391,  903,   71,  583,  327,  839,  199,  711,
	 455,  967,   39,  551,  295,  807,  167,  679,  423,  935,
	 103,  615,  359,  871,  231,  743,  487,  999,   23,  535,
	 279,  791,  151,  663,  407,  919,   87,  599,  343,  855,
	 215,  727,  471,  983,   55,  567,  311,  823,  183,  695,
	 439,  951,  119,  631,  375,  887,  247,  759,  503, 1015,
	  15,  527,  271,  783,  143,  655,  399,  911,   79,  591,
	 335,  847,  207,  719,  463,  975,   47,  559,  303,  815,
	 175,  687,  431,  943,  111,  623,  367,  879,  239,  751,
	 495, 1007,   31,  543,  287,  799,  159,  671,  415,  927,

	  95,  607,  351,  863,  223,  735,  479,  991,   63,  575,
	 319,  831,  191,  703,  447,  959,  127,  639,  383,  895,
	 255,  767,  511, 1023
};

const ntt_fft_params_t ntt_fft_12289_1024 = {
	12289, 12287, 18, 3186, (1<<18)-1, 1024, 12277, 10,
	wr_12289_1024, wf_12289_1024, wi_12289_1024, 1, rev_1024
};

/**
 * FFT phase shift and scaling inverse transform for q = 12289 and n = 512
 */
static const uint16_t wi_12289_512[] = {
	12265,  6771, 11424,  9011,  6203, 11914,  9021,  6454,  7154,   146,
	11038,  4238,  5604, 10397, 11498,  3495,  7846,  7684,  1160,  4538,
	  845,  2776,  3317,  5836,  6389, 11667,  6508,  1136, 11309, 12269,
	11787,  9520,  5461,  3121,  5832,  1373,  1282, 10058,  4218,  5102,
	 7628,  4670,  6616,  1389,  9057,  2442,  2307,  5063,  7878, 10945,
	10506,   716,   767,  3276,  3578,  1327,  5043,  7376,  8176,  3678,
	 3837,  6599,  4649,  4860, 11385,  9261,   189,  3515,  8348, 10453,
	 7988,  1417,  7302,  1403,  2035,  8067,  2171,  6565, 11169,  8755,
	 4693, 10880,  2730,  7078,  3154, 10347, 10243,  2717,  3065,  9342,
	 3451,  1826,  4050,  3343,  1573,  6302,   881, 11053, 10759, 10753,

	 3229,  6085, 11410,  3744,   578, 12050,  7519,  3163,  9344,  5959,
	  874,  2275,  1802, 10821,  2478, 10584,   216,   506,  7785,  4924,
	 5618,  3375,  4834,  3359,  9348, 10975, 11259, 11014, 11009,  4739,
	 7119,  5412,  3120,  4578,  1849,  8314,  4684, 11883,  7014,  8921,
	 3944,  5598,  2873,  2065,  8820,   180,  4518,   343,     7,  8778,
	 8957, 12221,   751,  7790, 11194,  3238,  5082,  7126,  1901, 12077,
	 4510,  2600,  3815,  3589,  2832, 12096,  3758,  5845,  5386,  7383,
	 4665,   346,  3769,  7350,   150,  3765,  2334,  2054,  7315,  5416,
	 8136,  2674, 10588,  5232, 10891,  4235,  1842, 11825,  8016, 11951,
	 6263,  1131,  5039,  2360, 10080,  7228,  6919,   392,     8, 10032,

	 8481,  5189,  6125,   125,  9282,  1945,  5808,  8144,   417,  6780,
	10421,  4727,  4360, 11124,  1481,  1535,  7806,  6680,  7911,  3171,
	 7087,  2151,  6063,  8400,  1927,  7814,  4423,  4103,  8360,   923,
	 2276,  3056, 10345,  7735,  3669,  4840, 10883,  6492,  5650,  6636,
	 1891, 11826,  9270, 11475, 11520,  6505,  9663,   448,  8787,  7954,
	 7937, 11197,  7000,  3654, 10608,  5734,  1371, 11063, 11010,  5993,
	 6643, 10669,  8494,  9202, 12226,  7021,  5410,   612,  5530,  3624,
	 9855,  7725,  3418,  9600,  7469,  1908,  8566,  1178,  2532,  4566,
	11379,  1737,  3045,  8840,   682,  7287,  7171,  9175,  2946,  7584,
	10939,  2982,  3572,  6092,  7899,   412,   510,   512,  3020,  2068,

	  293, 11041,  8000,  4176,  1590,  3042,  5078,  2110,  3805,  3338,
	 7592,  8682, 11463,  8761, 12217,  8024,  9694,  2455,  6320, 11164,
	 2485,  7073,  9173,   438,  8536,   425,  4523,  6613,  9916, 10485,
	11249, 10763,  3480,  1325,  2535,  8328,  9951,  5219,  6878, 10423,
	 7235,  3408,  9349, 12229, 10783,  3982,  4094,  9363,  5207,  4119,
	 3846,  5596,   365,  3017, 10595,  1721,  7559,  4167,  2593,  7326,
	 6921,  2900, 11345,  8257,  6940,  2148,  2301,  9828, 10734,  3981,
	 2840,  9839, 12239, 11034, 11511,  7508,  1658,  2291,  9577,  3205,
	  567, 10545,   466,  6781, 11675,  4251,  9617,  4209,  6105, 11912,
	 6513,  7406,  8929,  1687,  1790,  8062,  8190,  8945,  9462,  6463,

	 6151,  8151,  9195,  3448, 10353,  5478, 12150, 10029,  4719,  6617,
	 2643,  8581,  7699,  7681,  9687,  5966,  9652, 11232,  1734, 11572,
	10268,  9489,  3454,  5588,  2622,  6825,  5406,  7885,  7434,  7174,
	  648,  1518, 11066,  2483,  4565, 10125,  2213, 10077,  3466,  8347,
	 9199,  8464,  8449,  1928,  9068,  3947,  9360,  1445,  5547,   364,
	 1763, 11071,  8753,  2185, 11832,  4505,  8619,  6195,  1882,   540,
	 1265,  1029,    21,  1756,  2293, 12085,  2253, 11081,  9004,  9714,
	 2957,  9089,  5703, 11653,  1241,  7800, 11445, 10767,  8496, 11710,
	11274,  5246,  3869,  9860,  1706,  1038, 11307,  9761,   450, 11295,
	 7002,  6162,  9656,  3959, 12119,  8022,  7186,  3407,  8095,   416,

	 5526, 10897, 11759, 11275,  6500,  3393,  2828,  7080,  5662,  9395,
	 8468,  1176
};

/**
 * Bit-reversed indices for n = 512
 */
static const uint16_t rev_512[] = {
	  0, 256, 128, 384,  64, 320, 192, 448,  32, 288, 
	160, 416,  96, 352, 224, 480,  16, 272, 144, 400,
	 80, 336, 208, 464,  48, 304, 176, 432, 112, 368,
	240, 496,   8, 264, 136, 392,  72, 328, 200, 456,
	 40, 296, 168, 424, 104, 360, 232, 488,  24, 280,
	152, 408,  88, 344, 216, 472,  56, 312, 184, 440,
	120, 376, 248, 504,   4, 260, 132, 388,  68, 324,
	196, 452,  36, 292, 164, 420, 100, 356, 228, 484,
	 20, 276, 148, 404,  84, 340, 212, 468,  52, 308,
	180, 436, 116, 372, 244, 500,  12, 268, 140, 396,

	 76, 332, 204, 460,  44, 300, 172, 428, 108, 364,
	236, 492,  28, 284, 156, 412,  92, 348, 220, 476,
	 60, 316, 188, 444, 124, 380, 252, 508,   2, 258,
	130, 386,  66, 322, 194, 450,  34, 290, 162, 418,
	 98, 354, 226, 482,  18, 274, 146, 402,  82, 338,
	210, 466,  50, 306, 178, 434, 114, 370, 242, 498,
	 10, 266, 138, 394,  74, 330, 202, 458,  42, 298,
	170, 426, 106, 362, 234, 490,  26, 282, 154, 410,
	 90, 346, 218, 474,  58, 314, 186, 442, 122, 378,
	250, 506,   6, 262, 134, 390,  70, 326, 198, 454,

	 38, 294, 166, 422, 102, 358, 230, 486,  22, 278,
	150, 406,  86, 342, 214, 470,  54, 310, 182, 438,
	118, 374, 246, 502,  14, 270, 142, 398,  78, 334,
	206, 462,  46, 302, 174, 430, 110, 366, 238, 494,
	 30, 286, 158, 414,  94, 350, 222, 478,  62, 318,
	190, 446, 126, 382, 254, 510,   1, 257, 129, 385,
	 65, 321, 193, 449,  33, 289, 161, 417,  97, 353,
	225, 481,  17, 273, 145, 401,  81, 337, 209, 465,
	 49, 305, 177, 433, 113, 369, 241, 497,   9, 265,
	137, 393,  73, 329, 201, 457,  41, 297, 169, 425,

	105, 361, 233, 489,  25, 281, 153, 409,  89, 345,
	217, 473,  57, 313, 185, 441, 121, 377, 249, 505,
	  5, 261, 133, 389,  69, 325, 197, 453,  37, 293,
	165, 421, 101, 357, 229, 485,  21, 277, 149, 405,
	 85, 341, 213, 469,  53, 309, 181, 437, 117, 373,
	245, 501,  13, 269, 141, 397,  77, 333, 205, 461,
	 45, 301, 173, 429, 109, 365, 237, 493,  29, 285,
	157, 413,  93, 349, 221, 477,  61, 317, 189, 445,
	125, 381, 253, 509,   3, 259, 131, 387,  67, 323,
	195, 451,  35, 291, 163, 419,  99, 355, 227, 483,

	 19, 275, 147, 403,  83, 339, 211, 467,  51, 307,
	179, 435, 115, 371, 243, 499,  11, 267, 139, 395,
	 75, 331, 203, 459,  43, 299, 171, 427, 107, 363,
	235, 491,  27, 283, 155, 411,  91, 347, 219, 475,
	 59, 315, 187, 443, 123, 379, 251, 507,   7, 263,
	135, 391,  71, 327, 199, 455,  39, 295, 167, 423,
	103, 359, 231, 487,  23, 279, 151, 407,  87, 343,
	215, 471,  55, 311, 183, 439, 119, 375, 247, 503,
	 15, 271, 143, 399,  79, 335, 207, 463,  47, 303,
	175, 431, 111, 367, 239, 495,  31, 287, 159, 415,

	 95, 351, 223, 479,  63, 319, 191, 447, 127, 383,
	255, 511
};

const ntt_fft_params_t ntt_fft_12289_512 = {
	12289, 12287, 18, 3186, (1<<18)-1, 512, 12265, 9,
	wr_12289_1024, wf_12289_1024, wi_12289_512, 2, rev_512
};

/**
 * FFT twiddle factors in Montgomery form for q = 17 and n = 8
 */
static const uint16_t wr_17_8[] = { 15, 16, 8, 4, 2, 1, 9, 13, 15 };

/**
 * FFT phase shift in forward transform for q = 17 and n = 8
 */
static const uint16_t wf_17_8[] = { 4, 12, 2, 6, 1, 3, 9, 10 };

/**
 * FFT phase shift and scaling inverse transform for q = 17 and n = 8
 */
static const uint16_t wi_17_8[] = { 15, 5, 13, 10, 9, 3, 1, 6 };

/**
 * Bit-reversed indices for n = 8
 */
static const uint16_t rev_8[] = { 0, 4, 2, 6, 1, 5, 3, 7 };

const ntt_fft_params_t ntt_fft_17_8 = {
	17, 15, 5, 4, (1<<5)-1, 8, 15, 3, wr_17_8, wf_17_8, wi_17_8, 1, rev_8
};