path: root/lib/liboqs/src/sig/falcon/pqclean_falcon-1024_clean/vrfy.c

#include "inner.h"

/*
 * Falcon signature verification.
 *
 * ==========================(LICENSE BEGIN)============================
 *
 * Copyright (c) 2017-2019  Falcon Project
 *
 * Permission is hereby granted, free of charge, to any person obtaining
 * a copy of this software and associated documentation files (the
 * "Software"), to deal in the Software without restriction, including
 * without limitation the rights to use, copy, modify, merge, publish,
 * distribute, sublicense, and/or sell copies of the Software, and to
 * permit persons to whom the Software is furnished to do so, subject to
 * the following conditions:
 *
 * The above copyright notice and this permission notice shall be
 * included in all copies or substantial portions of the Software.
 *
 * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND,
 * EXPRESS OR IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF
 * MERCHANTABILITY, FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT.
 * IN NO EVENT SHALL THE AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY
 * CLAIM, DAMAGES OR OTHER LIABILITY, WHETHER IN AN ACTION OF CONTRACT,
 * TORT OR OTHERWISE, ARISING FROM, OUT OF OR IN CONNECTION WITH THE
 * SOFTWARE OR THE USE OR OTHER DEALINGS IN THE SOFTWARE.
 *
 * ===========================(LICENSE END)=============================
 *
 * @author   Thomas Pornin <thomas.pornin@nccgroup.com>
 */


/* ===================================================================== */
/*
 * Constants for NTT.
 *
 *   n = 2^logn  (2 <= n <= 1024)
 *   phi = X^n + 1
 *   q = 12289
 *   q0i = -1/q mod 2^16
 *   R = 2^16 mod q
 *   R2 = 2^32 mod q
 */

#define Q     12289
#define Q0I   12287
#define R      4091
#define R2    10952

/*
 * Table for NTT, binary case:
 *   GMb[x] = R*(g^rev(x)) mod q
 * where g = 7 (it is a 2048-th primitive root of 1 modulo q)
 * and rev() is the bit-reversal function over 10 bits.
 */
static const uint16_t GMb[] = {
    4091,  7888, 11060, 11208,  6960,  4342,  6275,  9759,
    1591,  6399,  9477,  5266,   586,  5825,  7538,  9710,
    1134,  6407,  1711,   965,  7099,  7674,  3743,  6442,
    10414,  8100,  1885,  1688,  1364, 10329, 10164,  9180,
    12210,  6240,   997,   117,  4783,  4407,  1549,  7072,
    2829,  6458,  4431,  8877,  7144,  2564,  5664,  4042,
    12189,   432, 10751,  1237,  7610,  1534,  3983,  7863,
    2181,  6308,  8720,  6570,  4843,  1690,    14,  3872,
    5569,  9368, 12163,  2019,  7543,  2315,  4673,  7340,
    1553,  1156,  8401, 11389,  1020,  2967, 10772,  7045,
    3316, 11236,  5285, 11578, 10637, 10086,  9493,  6180,
    9277,  6130,  3323,   883, 10469,   489,  1502,  2851,
    11061,  9729,  2742, 12241,  4970, 10481, 10078,  1195,
    730,  1762,  3854,  2030,  5892, 10922,  9020,  5274,
    9179,  3604,  3782, 10206,  3180,  3467,  4668,  2446,
    7613,  9386,   834,  7703,  6836,  3403,  5351, 12276,
    3580,  1739, 10820,  9787, 10209,  4070, 12250,  8525,
    10401,  2749,  7338, 10574,  6040,   943,  9330,  1477,
    6865,  9668,  3585,  6633, 12145,  4063,  3684,  7680,
    8188,  6902,  3533,  9807,  6090,   727, 10099,  7003,
    6945,  1949,  9731, 10559,  6057,   378,  7871,  8763,
    8901,  9229,  8846,  4551,  9589, 11664,  7630,  8821,
    5680,  4956,  6251,  8388, 10156,  8723,  2341,  3159,
    1467,  5460,  8553,  7783,  2649,  2320,  9036,  6188,
    737,  3698,  4699,  5753,  9046,  3687,    16,   914,
    5186, 10531,  4552,  1964,  3509,  8436,  7516,  5381,
    10733,  3281,  7037,  1060,  2895,  7156,  8887,  5357,
    6409,  8197,  2962,  6375,  5064,  6634,  5625,   278,
    932, 10229,  8927,  7642,   351,  9298,   237,  5858,
    7692,  3146, 12126,  7586,  2053, 11285,  3802,  5204,
    4602,  1748, 11300,   340,  3711,  4614,   300, 10993,
    5070, 10049, 11616, 12247,  7421, 10707,  5746,  5654,
    3835,  5553,  1224,  8476,  9237,  3845,   250, 11209,
    4225,  6326,  9680, 12254,  4136,  2778,   692,  8808,
    6410,  6718, 10105, 10418,  3759,  7356, 11361,  8433,
    6437,  3652,  6342,  8978,  5391,  2272,  6476,  7416,
    8418, 10824, 11986,  5733,   876,  7030,  2167,  2436,
    3442,  9217,  8206,  4858,  5964,  2746,  7178,  1434,
    7389,  8879, 10661, 11457,  4220,  1432, 10832,  4328,
    8557,  1867,  9454,  2416,  3816,  9076,   686,  5393,
    2523,  4339,  6115,   619,   937,  2834,  7775,  3279,
    2363,  7488,  6112,  5056,   824, 10204, 11690,  1113,
    2727,  9848,   896,  2028,  5075,  2654, 10464,  7884,
    12169,  5434,  3070,  6400,  9132, 11672, 12153,  4520,
    1273,  9739, 11468,  9937, 10039,  9720,  2262,  9399,
    11192,   315,  4511,  1158,  6061,  6751, 11865,   357,
    7367,  4550,   983,  8534,  8352, 10126,  7530,  9253,
    4367,  5221,  3999,  8777,  3161,  6990,  4130, 11652,
    3374, 11477,  1753,   292,  8681,  2806, 10378, 12188,
    5800, 11811,  3181,  1988,  1024,  9340,  2477, 10928,
    4582,  6750,  3619,  5503,  5233,  2463,  8470,  7650,
    7964,  6395,  1071,  1272,  3474, 11045,  3291, 11344,
    8502,  9478,  9837,  1253,  1857,  6233,  4720, 11561,
    6034,  9817,  3339,  1797,  2879,  6242,  5200,  2114,
    7962,  9353, 11363,  5475,  6084,  9601,  4108,  7323,
    10438,  9471,  1271,   408,  6911,  3079,   360,  8276,
    11535,  9156,  9049, 11539,   850,  8617,   784,  7919,
    8334, 12170,  1846, 10213, 12184,  7827, 11903,  5600,
    9779,  1012,   721,  2784,  6676,  6552,  5348,  4424,
    6816,  8405,  9959,  5150,  2356,  5552,  5267,  1333,
    8801,  9661,  7308,  5788,  4910,   909, 11613,  4395,
    8238,  6686,  4302,  3044,  2285, 12249,  1963,  9216,
    4296, 11918,   695,  4371,  9793,  4884,  2411, 10230,
    2650,   841,  3890, 10231,  7248,  8505, 11196,  6688,
    4059,  6060,  3686,  4722, 11853,  5816,  7058,  6868,
    11137,  7926,  4894, 12284,  4102,  3908,  3610,  6525,
    7938,  7982, 11977,  6755,   537,  4562,  1623,  8227,
    11453,  7544,   906, 11816,  9548, 10858,  9703,  2815,
    11736,  6813,  6979,   819,  8903,  6271, 10843,   348,
    7514,  8339,  6439,   694,   852,  5659,  2781,  3716,
    11589,  3024,  1523,  8659,  4114, 10738,  3303,  5885,
    2978,  7289, 11884,  9123,  9323, 11830,    98,  2526,
    2116,  4131, 11407,  1844,  3645,  3916,  8133,  2224,
    10871,  8092,  9651,  5989,  7140,  8480,  1670,   159,
    10923,  4918,   128,  7312,   725,  9157,  5006,  6393,
    3494,  6043, 10972,  6181, 11838,  3423, 10514,  7668,
    3693,  6658,  6905, 11953, 10212, 11922,  9101,  8365,
    5110,    45,  2400,  1921,  4377,  2720,  1695,    51,
    2808,   650,  1896,  9997,  9971, 11980,  8098,  4833,
    4135,  4257,  5838,  4765, 10985, 11532,   590, 12198,
    482, 12173,  2006,  7064, 10018,  3912, 12016, 10519,
    11362,  6954,  2210,   284,  5413,  6601,  3865, 10339,
    11188,  6231,   517,  9564, 11281,  3863,  1210,  4604,
    8160, 11447,   153,  7204,  5763,  5089,  9248, 12154,
    11748,  1354,  6672,   179,  5532,  2646,  5941, 12185,
    862,  3158,   477,  7279,  5678,  7914,  4254,   302,
    2893, 10114,  6890,  9560,  9647, 11905,  4098,  9824,
    10269,  1353, 10715,  5325,  6254,  3951,  1807,  6449,
    5159,  1308,  8315,  3404,  1877,  1231,   112,  6398,
    11724, 12272,  7286,  1459, 12274,  9896,  3456,   800,
    1397, 10678,   103,  7420,  7976,   936,   764,   632,
    7996,  8223,  8445,  7758, 10870,  9571,  2508,  1946,
    6524, 10158,  1044,  4338,  2457,  3641,  1659,  4139,
    4688,  9733, 11148,  3946,  2082,  5261,  2036, 11850,
    7636, 12236,  5366,  2380,  1399,  7720,  2100,  3217,
    10912,  8898,  7578, 11995,  2791,  1215,  3355,  2711,
    2267,  2004,  8568, 10176,  3214,  2337,  1750,  4729,
    4997,  7415,  6315, 12044,  4374,  7157,  4844,   211,
    8003, 10159,  9290, 11481,  1735,  2336,  5793,  9875,
    8192,   986,  7527,  1401,   870,  3615,  8465,  2756,
    9770,  2034, 10168,  3264,  6132,    54,  2880,  4763,
    11805,  3074,  8286,  9428,  4881,  6933,  1090, 10038,
    2567,   708,   893,  6465,  4962, 10024,  2090,  5718,
    10743,   780,  4733,  4623,  2134,  2087,  4802,   884,
    5372,  5795,  5938,  4333,  6559,  7549,  5269, 10664,
    4252,  3260,  5917, 10814,  5768,  9983,  8096,  7791,
    6800,  7491,  6272,  1907, 10947,  6289, 11803,  6032,
    11449,  1171,  9201,  7933,  2479,  7970, 11337,  7062,
    8911,  6728,  6542,  8114,  8828,  6595,  3545,  4348,
    4610,  2205,  6999,  8106,  5560, 10390,  9321,  2499,
    2413,  7272,  6881, 10582,  9308,  9437,  3554,  3326,
    5991, 11969,  3415, 12283,  9838, 12063,  4332,  7830,
    11329,  6605, 12271,  2044, 11611,  7353, 11201, 11582,
    3733,  8943,  9978,  1627,  7168,  3935,  5050,  2762,
    7496, 10383,   755,  1654, 12053,  4952, 10134,  4394,
    6592,  7898,  7497,  8904, 12029,  3581, 10748,  5674,
    10358,  4901,  7414,  8771,   710,  6764,  8462,  7193,
    5371,  7274, 11084,   290,  7864,  6827, 11822,  2509,
    6578,  4026,  5807,  1458,  5721,  5762,  4178,  2105,
    11621,  4852,  8897,  2856, 11510,  9264,  2520,  8776,
    7011,  2647,  1898,  7039,  5950, 11163,  5488,  6277,
    9182, 11456,   633, 10046, 11554,  5633,  9587,  2333,
    7008,  7084,  5047,  7199,  9865,  8997,   569,  6390,
    10845,  9679,  8268, 11472,  4203,  1997,     2,  9331,
    162,  6182,  2000,  3649,  9792,  6363,  7557,  6187,
    8510,  9935,  5536,  9019,  3706, 12009,  1452,  3067,
    5494,  9692,  4865,  6019,  7106,  9610,  4588, 10165,
    6261,  5887,  2652, 10172,  1580, 10379,  4638,  9949
};

/*
 * Table for inverse NTT, binary case:
 *   iGMb[x] = R*((1/g)^rev(x)) mod q
 * Since g = 7, 1/g = 8778 mod 12289.
 */
static const uint16_t iGMb[] = {
    4091,  4401,  1081,  1229,  2530,  6014,  7947,  5329,
    2579,  4751,  6464, 11703,  7023,  2812,  5890, 10698,
    3109,  2125,  1960, 10925, 10601, 10404,  4189,  1875,
    5847,  8546,  4615,  5190, 11324, 10578,  5882, 11155,
    8417, 12275, 10599,  7446,  5719,  3569,  5981, 10108,
    4426,  8306, 10755,  4679, 11052,  1538, 11857,   100,
    8247,  6625,  9725,  5145,  3412,  7858,  5831,  9460,
    5217, 10740,  7882,  7506, 12172, 11292,  6049,    79,
    13,  6938,  8886,  5453,  4586, 11455,  2903,  4676,
    9843,  7621,  8822,  9109,  2083,  8507,  8685,  3110,
    7015,  3269,  1367,  6397, 10259,  8435, 10527, 11559,
    11094,  2211,  1808,  7319,    48,  9547,  2560,  1228,
    9438, 10787, 11800,  1820, 11406,  8966,  6159,  3012,
    6109,  2796,  2203,  1652,   711,  7004,  1053,  8973,
    5244,  1517,  9322, 11269,   900,  3888, 11133, 10736,
    4949,  7616,  9974,  4746, 10270,   126,  2921,  6720,
    6635,  6543,  1582,  4868,    42,   673,  2240,  7219,
    1296, 11989,  7675,  8578, 11949,   989, 10541,  7687,
    7085,  8487,  1004, 10236,  4703,   163,  9143,  4597,
    6431, 12052,  2991, 11938,  4647,  3362,  2060, 11357,
    12011,  6664,  5655,  7225,  5914,  9327,  4092,  5880,
    6932,  3402,  5133,  9394, 11229,  5252,  9008,  1556,
    6908,  4773,  3853,  8780, 10325,  7737,  1758,  7103,
    11375, 12273,  8602,  3243,  6536,  7590,  8591, 11552,
    6101,  3253,  9969,  9640,  4506,  3736,  6829, 10822,
    9130,  9948,  3566,  2133,  3901,  6038,  7333,  6609,
    3468,  4659,   625,  2700,  7738,  3443,  3060,  3388,
    3526,  4418, 11911,  6232,  1730,  2558, 10340,  5344,
    5286,  2190, 11562,  6199,  2482,  8756,  5387,  4101,
    4609,  8605,  8226,   144,  5656,  8704,  2621,  5424,
    10812,  2959, 11346,  6249,  1715,  4951,  9540,  1888,
    3764,    39,  8219,  2080,  2502,  1469, 10550,  8709,
    5601,  1093,  3784,  5041,  2058,  8399, 11448,  9639,
    2059,  9878,  7405,  2496,  7918, 11594,   371,  7993,
    3073, 10326,    40, 10004,  9245,  7987,  5603,  4051,
    7894,   676, 11380,  7379,  6501,  4981,  2628,  3488,
    10956,  7022,  6737,  9933,  7139,  2330,  3884,  5473,
    7865,  6941,  5737,  5613,  9505, 11568, 11277,  2510,
    6689,   386,  4462,   105,  2076, 10443,   119,  3955,
    4370, 11505,  3672, 11439,   750,  3240,  3133,   754,
    4013, 11929,  9210,  5378, 11881, 11018,  2818,  1851,
    4966,  8181,  2688,  6205,  6814,   926,  2936,  4327,
    10175,  7089,  6047,  9410, 10492,  8950,  2472,  6255,
    728,  7569,  6056, 10432, 11036,  2452,  2811,  3787,
    945,  8998,  1244,  8815, 11017, 11218,  5894,  4325,
    4639,  3819,  9826,  7056,  6786,  8670,  5539,  7707,
    1361,  9812,  2949, 11265, 10301,  9108,   478,  6489,
    101,  1911,  9483,  3608, 11997, 10536,   812,  8915,
    637,  8159,  5299,  9128,  3512,  8290,  7068,  7922,
    3036,  4759,  2163,  3937,  3755, 11306,  7739,  4922,
    11932,   424,  5538,  6228, 11131,  7778, 11974,  1097,
    2890, 10027,  2569,  2250,  2352,   821,  2550, 11016,
    7769,   136,   617,  3157,  5889,  9219,  6855,   120,
    4405,  1825,  9635,  7214, 10261, 11393,  2441,  9562,
    11176,   599,  2085, 11465,  7233,  6177,  4801,  9926,
    9010,  4514,  9455, 11352, 11670,  6174,  7950,  9766,
    6896, 11603,  3213,  8473,  9873,  2835, 10422,  3732,
    7961,  1457, 10857,  8069,   832,  1628,  3410,  4900,
    10855,  5111,  9543,  6325,  7431,  4083,  3072,  8847,
    9853, 10122,  5259, 11413,  6556,   303,  1465,  3871,
    4873,  5813, 10017,  6898,  3311,  5947,  8637,  5852,
    3856,   928,  4933,  8530,  1871,  2184,  5571,  5879,
    3481, 11597,  9511,  8153,    35,  2609,  5963,  8064,
    1080, 12039,  8444,  3052,  3813, 11065,  6736,  8454,
    2340,  7651,  1910, 10709,  2117,  9637,  6402,  6028,
    2124,  7701,  2679,  5183,  6270,  7424,  2597,  6795,
    9222, 10837,   280,  8583,  3270,  6753,  2354,  3779,
    6102,  4732,  5926,  2497,  8640, 10289,  6107, 12127,
    2958, 12287, 10292,  8086,   817,  4021,  2610,  1444,
    5899, 11720,  3292,  2424,  5090,  7242,  5205,  5281,
    9956,  2702,  6656,   735,  2243, 11656,   833,  3107,
    6012,  6801,  1126,  6339,  5250, 10391,  9642,  5278,
    3513,  9769,  3025,   779,  9433,  3392,  7437,   668,
    10184,  8111,  6527,  6568, 10831,  6482,  8263,  5711,
    9780,   467,  5462,  4425, 11999,  1205,  5015,  6918,
    5096,  3827,  5525, 11579,  3518,  4875,  7388,  1931,
    6615,  1541,  8708,   260,  3385,  4792,  4391,  5697,
    7895,  2155,  7337,   236, 10635, 11534,  1906,  4793,
    9527,  7239,  8354,  5121, 10662,  2311,  3346,  8556,
    707,  1088,  4936,   678, 10245,    18,  5684,   960,
    4459,  7957,   226,  2451,     6,  8874,   320,  6298,
    8963,  8735,  2852,  2981,  1707,  5408,  5017,  9876,
    9790,  2968,  1899,  6729,  4183,  5290, 10084,  7679,
    7941,  8744,  5694,  3461,  4175,  5747,  5561,  3378,
    5227,   952,  4319,  9810,  4356,  3088, 11118,   840,
    6257,   486,  6000,  1342, 10382,  6017,  4798,  5489,
    4498,  4193,  2306,  6521,  1475,  6372,  9029,  8037,
    1625,  7020,  4740,  5730,  7956,  6351,  6494,  6917,
    11405,  7487, 10202, 10155,  7666,  7556, 11509,  1546,
    6571, 10199,  2265,  7327,  5824, 11396, 11581,  9722,
    2251, 11199,  5356,  7408,  2861,  4003,  9215,   484,
    7526,  9409, 12235,  6157,  9025,  2121, 10255,  2519,
    9533,  3824,  8674, 11419, 10888,  4762, 11303,  4097,
    2414,  6496,  9953, 10554,   808,  2999,  2130,  4286,
    12078,  7445,  5132,  7915,   245,  5974,  4874,  7292,
    7560, 10539,  9952,  9075,  2113,  3721, 10285, 10022,
    9578,  8934, 11074,  9498,   294,  4711,  3391,  1377,
    9072, 10189,  4569, 10890,  9909,  6923,    53,  4653,
    439, 10253,  7028, 10207,  8343,  1141,  2556,  7601,
    8150, 10630,  8648,  9832,  7951, 11245,  2131,  5765,
    10343,  9781,  2718,  1419,  4531,  3844,  4066,  4293,
    11657, 11525, 11353,  4313,  4869, 12186,  1611, 10892,
    11489,  8833,  2393,    15, 10830,  5003,    17,   565,
    5891, 12177, 11058, 10412,  8885,  3974, 10981,  7130,
    5840, 10482,  8338,  6035,  6964,  1574, 10936,  2020,
    2465,  8191,   384,  2642,  2729,  5399,  2175,  9396,
    11987,  8035,  4375,  6611,  5010, 11812,  9131, 11427,
    104,  6348,  9643,  6757, 12110,  5617, 10935,   541,
    135,  3041,  7200,  6526,  5085, 12136,   842,  4129,
    7685, 11079,  8426,  1008,  2725, 11772,  6058,  1101,
    1950,  8424,  5688,  6876, 12005, 10079,  5335,   927,
    1770,   273,  8377,  2271,  5225, 10283,   116, 11807,
    91, 11699,   757,  1304,  7524,  6451,  8032,  8154,
    7456,  4191,   309,  2318,  2292, 10393, 11639,  9481,
    12238, 10594,  9569,  7912, 10368,  9889, 12244,  7179,
    3924,  3188,   367,  2077,   336,  5384,  5631,  8596,
    4621,  1775,  8866,   451,  6108,  1317,  6246,  8795,
    5896,  7283,  3132, 11564,  4977, 12161,  7371,  1366,
    12130, 10619,  3809,  5149,  6300,  2638,  4197,  1418,
    10065,  4156,  8373,  8644, 10445,   882,  8158, 10173,
    9763, 12191,   459,  2966,  3166,   405,  5000,  9311,
    6404,  8986,  1551,  8175,  3630, 10766,  9265,   700,
    8573,  9508,  6630, 11437, 11595,  5850,  3950,  4775,
    11941,  1446,  6018,  3386, 11470,  5310,  5476,   553,
    9474,  2586,  1431,  2741,   473, 11383,  4745,   836,
    4062, 10666,  7727, 11752,  5534,   312,  4307,  4351,
    5764,  8679,  8381,  8187,     5,  7395,  4363,  1152,
    5421,  5231,  6473,   436,  7567,  8603,  6229,  8230
};

/*
 * Reduce a small signed integer modulo q. The source integer MUST
 * be between -q/2 and +q/2.
 */
static inline uint32_t
mq_conv_small(int x) {
    /*
     * If x < 0, the cast to uint32_t will set the high bit to 1.
     */
    uint32_t y;

    y = (uint32_t)x;
    y += Q & -(y >> 31);
    return y;
}

/*
 * Addition modulo q. Operands must be in the 0..q-1 range.
 */
static inline uint32_t
mq_add(uint32_t x, uint32_t y) {
    /*
     * We compute x + y - q. If the result is negative, then the
     * high bit will be set, and 'd >> 31' will be equal to 1;
     * thus '-(d >> 31)' will be an all-one pattern. Otherwise,
     * it will be an all-zero pattern. In other words, this
     * implements a conditional addition of q.
     */
    uint32_t d;

    d = x + y - Q;
    d += Q & -(d >> 31);
    return d;
}

/*
 * Subtraction modulo q. Operands must be in the 0..q-1 range.
 */
static inline uint32_t
mq_sub(uint32_t x, uint32_t y) {
    /*
     * As in mq_add(), we use a conditional addition to ensure the
     * result is in the 0..q-1 range.
     */
    uint32_t d;

    d = x - y;
    d += Q & -(d >> 31);
    return d;
}

/*
 * Division by 2 modulo q. Operand must be in the 0..q-1 range.
 */
static inline uint32_t
mq_rshift1(uint32_t x) {
    x += Q & -(x & 1);
    return (x >> 1);
}

/*
 * Montgomery multiplication modulo q. If we set R = 2^16 mod q, then
 * this function computes: x * y / R mod q
 * Operands must be in the 0..q-1 range.
 */
static inline uint32_t
mq_montymul(uint32_t x, uint32_t y) {
    uint32_t z, w;

    /*
     * We compute x*y + k*q with a value of k chosen so that the 16
     * low bits of the result are 0. We can then shift the value.
     * After the shift, result may still be larger than q, but it
     * will be lower than 2*q, so a conditional subtraction works.
     */

    z = x * y;
    w = ((z * Q0I) & 0xFFFF) * Q;

    /*
     * When adding z and w, the result will have its low 16 bits
     * equal to 0. Since x, y and z are lower than q, the sum will
     * be no more than (2^15 - 1) * q + (q - 1)^2, which will
     * fit on 29 bits.
     */
    z = (z + w) >> 16;

    /*
     * After the shift, analysis shows that the value will be less
     * than 2q. We do a subtraction then conditional subtraction to
     * ensure the result is in the expected range.
     */
    z -= Q;
    z += Q & -(z >> 31);
    return z;
}

/*
 * Montgomery squaring (computes (x^2)/R).
 */
static inline uint32_t
mq_montysqr(uint32_t x) {
    return mq_montymul(x, x);
}

/*
 * Divide x by y modulo q = 12289.
 */
static inline uint32_t
mq_div_12289(uint32_t x, uint32_t y) {
    /*
     * We invert y by computing y^(q-2) mod q.
     *
     * We use the following addition chain for exponent e = 12287:
     *
     *   e0 = 1
     *   e1 = 2 * e0 = 2
     *   e2 = e1 + e0 = 3
     *   e3 = e2 + e1 = 5
     *   e4 = 2 * e3 = 10
     *   e5 = 2 * e4 = 20
     *   e6 = 2 * e5 = 40
     *   e7 = 2 * e6 = 80
     *   e8 = 2 * e7 = 160
     *   e9 = e8 + e2 = 163
     *   e10 = e9 + e8 = 323
     *   e11 = 2 * e10 = 646
     *   e12 = 2 * e11 = 1292
     *   e13 = e12 + e9 = 1455
     *   e14 = 2 * e13 = 2910
     *   e15 = 2 * e14 = 5820
     *   e16 = e15 + e10 = 6143
     *   e17 = 2 * e16 = 12286
     *   e18 = e17 + e0 = 12287
     *
     * Additions on exponents are converted to Montgomery
     * multiplications. We define all intermediate results as so
     * many local variables, and let the C compiler work out which
     * must be kept around.
     */
    uint32_t y0, y1, y2, y3, y4, y5, y6, y7, y8, y9;
    uint32_t y10, y11, y12, y13, y14, y15, y16, y17, y18;

    y0 = mq_montymul(y, R2);
    y1 = mq_montysqr(y0);
    y2 = mq_montymul(y1, y0);
    y3 = mq_montymul(y2, y1);
    y4 = mq_montysqr(y3);
    y5 = mq_montysqr(y4);
    y6 = mq_montysqr(y5);
    y7 = mq_montysqr(y6);
    y8 = mq_montysqr(y7);
    y9 = mq_montymul(y8, y2);
    y10 = mq_montymul(y9, y8);
    y11 = mq_montysqr(y10);
    y12 = mq_montysqr(y11);
    y13 = mq_montymul(y12, y9);
    y14 = mq_montysqr(y13);
    y15 = mq_montysqr(y14);
    y16 = mq_montymul(y15, y10);
    y17 = mq_montysqr(y16);
    y18 = mq_montymul(y17, y0);

    /*
     * Final multiplication with x, which is not in Montgomery
     * representation, computes the correct division result.
     */
    return mq_montymul(y18, x);
}

/*
 * Compute NTT on a ring element.
 */
static void
mq_NTT(uint16_t *a, unsigned logn) {
    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;
            uint32_t s;

            s = GMb[m + i];
            j2 = j1 + ht;
            for (j = j1; j < j2; j ++) {
                uint32_t u, v;

                u = a[j];
                v = mq_montymul(a[j + ht], s);
                a[j] = (uint16_t)mq_add(u, v);
                a[j + ht] = (uint16_t)mq_sub(u, v);
            }
        }
        t = ht;
    }
}

/*
 * Compute the inverse NTT on a ring element, binary case.
 */
static void
mq_iNTT(uint16_t *a, unsigned logn) {
    size_t n, t, m;
    uint32_t 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;
            uint32_t s;

            j2 = j1 + t;
            s = iGMb[hm + i];
            for (j = j1; j < j2; j ++) {
                uint32_t u, v, w;

                u = a[j];
                v = a[j + t];
                a[j] = (uint16_t)mq_add(u, v);
                w = mq_sub(u, v);
                a[j + t] = (uint16_t)
                           mq_montymul(w, s);
            }
        }
        t = dt;
        m = hm;
    }

    /*
     * To complete the inverse NTT, we must now divide all values by
     * n (the vector size). We thus need the inverse of n, i.e. we
     * need to divide 1 by 2 logn times. But we also want it in
     * Montgomery representation, i.e. we also want to multiply it
     * by R = 2^16. In the common case, this should be a simple right
     * shift. The loop below is generic and works also in corner cases;
     * its computation time is negligible.
     */
    ni = R;
    for (m = n; m > 1; m >>= 1) {
        ni = mq_rshift1(ni);
    }
    for (m = 0; m < n; m ++) {
        a[m] = (uint16_t)mq_montymul(a[m], ni);
    }
}

/*
 * Convert a polynomial (mod q) to Montgomery representation.
 */
static void
mq_poly_tomonty(uint16_t *f, unsigned logn) {
    size_t u, n;

    n = (size_t)1 << logn;
    for (u = 0; u < n; u ++) {
        f[u] = (uint16_t)mq_montymul(f[u], R2);
    }
}

/*
 * Multiply two polynomials together (NTT representation, and using
 * a Montgomery multiplication). Result f*g is written over f.
 */
static void
mq_poly_montymul_ntt(uint16_t *f, const uint16_t *g, unsigned logn) {
    size_t u, n;

    n = (size_t)1 << logn;
    for (u = 0; u < n; u ++) {
        f[u] = (uint16_t)mq_montymul(f[u], g[u]);
    }
}

/*
 * Subtract polynomial g from polynomial f.
 */
static void
mq_poly_sub(uint16_t *f, const uint16_t *g, unsigned logn) {
    size_t u, n;

    n = (size_t)1 << logn;
    for (u = 0; u < n; u ++) {
        f[u] = (uint16_t)mq_sub(f[u], g[u]);
    }
}

/* ===================================================================== */

/* see inner.h */
void
PQCLEAN_FALCON1024_CLEAN_to_ntt_monty(uint16_t *h, unsigned logn) {
    mq_NTT(h, logn);
    mq_poly_tomonty(h, logn);
}

/* see inner.h */
int
PQCLEAN_FALCON1024_CLEAN_verify_raw(const uint16_t *c0, const int16_t *s2,
                                    const uint16_t *h, unsigned logn, uint8_t *tmp) {
    size_t u, n;
    uint16_t *tt;

    n = (size_t)1 << logn;
    tt = (uint16_t *)tmp;

    /*
     * Reduce s2 elements modulo q ([0..q-1] range).
     */
    for (u = 0; u < n; u ++) {
        uint32_t w;

        w = (uint32_t)s2[u];
        w += Q & -(w >> 31);
        tt[u] = (uint16_t)w;
    }

    /*
     * Compute -s1 = s2*h - c0 mod phi mod q (in tt[]).
     */
    mq_NTT(tt, logn);
    mq_poly_montymul_ntt(tt, h, logn);
    mq_iNTT(tt, logn);
    mq_poly_sub(tt, c0, logn);

    /*
     * Normalize -s1 elements into the [-q/2..q/2] range.
     */
    for (u = 0; u < n; u ++) {
        int32_t w;

        w = (int32_t)tt[u];
        w -= (int32_t)(Q & -(((Q >> 1) - (uint32_t)w) >> 31));
        ((int16_t *)tt)[u] = (int16_t)w;
    }

    /*
     * Signature is valid if and only if the aggregate (-s1,s2) vector
     * is short enough.
     */
    return PQCLEAN_FALCON1024_CLEAN_is_short((int16_t *)tt, s2, logn);
}

/* see inner.h */
int
PQCLEAN_FALCON1024_CLEAN_compute_public(uint16_t *h,
                                        const int8_t *f, const int8_t *g, unsigned logn, uint8_t *tmp) {
    size_t u, n;
    uint16_t *tt;

    n = (size_t)1 << logn;
    tt = (uint16_t *)tmp;
    for (u = 0; u < n; u ++) {
        tt[u] = (uint16_t)mq_conv_small(f[u]);
        h[u] = (uint16_t)mq_conv_small(g[u]);
    }
    mq_NTT(h, logn);
    mq_NTT(tt, logn);
    for (u = 0; u < n; u ++) {
        if (tt[u] == 0) {
            return 0;
        }
        h[u] = (uint16_t)mq_div_12289(h[u], tt[u]);
    }
    mq_iNTT(h, logn);
    return 1;
}

/* see inner.h */
int
PQCLEAN_FALCON1024_CLEAN_complete_private(int8_t *G,
        const int8_t *f, const int8_t *g, const int8_t *F,
        unsigned logn, uint8_t *tmp) {
    size_t u, n;
    uint16_t *t1, *t2;

    n = (size_t)1 << logn;
    t1 = (uint16_t *)tmp;
    t2 = t1 + n;
    for (u = 0; u < n; u ++) {
        t1[u] = (uint16_t)mq_conv_small(g[u]);
        t2[u] = (uint16_t)mq_conv_small(F[u]);
    }
    mq_NTT(t1, logn);
    mq_NTT(t2, logn);
    mq_poly_tomonty(t1, logn);
    mq_poly_montymul_ntt(t1, t2, logn);
    for (u = 0; u < n; u ++) {
        t2[u] = (uint16_t)mq_conv_small(f[u]);
    }
    mq_NTT(t2, logn);
    for (u = 0; u < n; u ++) {
        if (t2[u] == 0) {
            return 0;
        }
        t1[u] = (uint16_t)mq_div_12289(t1[u], t2[u]);
    }
    mq_iNTT(t1, logn);
    for (u = 0; u < n; u ++) {
        uint32_t w;
        int32_t gi;

        w = t1[u];
        w -= (Q & ~ -((w - (Q >> 1)) >> 31));
        gi = *(int32_t *)&w;
        if (gi < -127 || gi > +127) {
            return 0;
        }
        G[u] = (int8_t)gi;
    }
    return 1;
}

/* see inner.h */
int
PQCLEAN_FALCON1024_CLEAN_is_invertible(
    const int16_t *s2, unsigned logn, uint8_t *tmp) {
    size_t u, n;
    uint16_t *tt;
    uint32_t r;

    n = (size_t)1 << logn;
    tt = (uint16_t *)tmp;
    for (u = 0; u < n; u ++) {
        uint32_t w;

        w = (uint32_t)s2[u];
        w += Q & -(w >> 31);
        tt[u] = (uint16_t)w;
    }
    mq_NTT(tt, logn);
    r = 0;
    for (u = 0; u < n; u ++) {
        r |= (uint32_t)(tt[u] - 1);
    }
    return (int)(1u - (r >> 31));
}

/* see inner.h */
int
PQCLEAN_FALCON1024_CLEAN_verify_recover(uint16_t *h,
                                        const uint16_t *c0, const int16_t *s1, const int16_t *s2,
                                        unsigned logn, uint8_t *tmp) {
    size_t u, n;
    uint16_t *tt;
    uint32_t r;

    n = (size_t)1 << logn;

    /*
     * Reduce elements of s1 and s2 modulo q; then write s2 into tt[]
     * and c0 - s1 into h[].
     */
    tt = (uint16_t *)tmp;
    for (u = 0; u < n; u ++) {
        uint32_t w;

        w = (uint32_t)s2[u];
        w += Q & -(w >> 31);
        tt[u] = (uint16_t)w;

        w = (uint32_t)s1[u];
        w += Q & -(w >> 31);
        w = mq_sub(c0[u], w);
        h[u] = (uint16_t)w;
    }

    /*
     * Compute h = (c0 - s1) / s2. If one of the coefficients of s2
     * is zero (in NTT representation) then the operation fails. We
     * keep that information into a flag so that we do not deviate
     * from strict constant-time processing; if all coefficients of
     * s2 are non-zero, then the high bit of r will be zero.
     */
    mq_NTT(tt, logn);
    mq_NTT(h, logn);
    r = 0;
    for (u = 0; u < n; u ++) {
        r |= (uint32_t)(tt[u] - 1);
        h[u] = (uint16_t)mq_div_12289(h[u], tt[u]);
    }
    mq_iNTT(h, logn);

    /*
     * Signature is acceptable if and only if it is short enough,
     * and s2 was invertible mod phi mod q. The caller must still
     * check that the rebuilt public key matches the expected
     * value (e.g. through a hash).
     */
    r = ~r & (uint32_t) - PQCLEAN_FALCON1024_CLEAN_is_short(s1, s2, logn);
    return (int)(r >> 31);
}

/* see inner.h */
int
PQCLEAN_FALCON1024_CLEAN_count_nttzero(const int16_t *sig, unsigned logn, uint8_t *tmp) {
    uint16_t *s2;
    size_t u, n;
    uint32_t r;

    n = (size_t)1 << logn;
    s2 = (uint16_t *)tmp;
    for (u = 0; u < n; u ++) {
        uint32_t w;

        w = (uint32_t)sig[u];
        w += Q & -(w >> 31);
        s2[u] = (uint16_t)w;
    }
    mq_NTT(s2, logn);
    r = 0;
    for (u = 0; u < n; u ++) {
        uint32_t w;

        w = (uint32_t)s2[u] - 1u;
        r += (w >> 31);
    }
    return (int)r;
}