/*
Licensed to the Apache Software Foundation (ASF) under one
or more contributor license agreements.  See the NOTICE file
distributed with this work for additional information
regarding copyright ownership.  The ASF licenses this file
to you under the Apache License, Version 2.0 (the
"License"); you may not use this file except in compliance
with the License.  You may obtain a copy of the License at

  http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing,
software distributed under the License is distributed on an
"AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
KIND, either express or implied.  See the License for the
specific language governing permissions and limitations
under the License.
*/

/* NewHope API implementation. Constant time.

	LOOK - no if statements!

   M.Scott 21/07/2017
*/

#include "newhope.h"

const sign16 roots[] ={0x2ac8,0x2baf,0x299b,0x685,0x2f04,0x158d,0x2d49,0x24b5,0x1edc,0xab3,0x2a95,0x24d,0x3cb,0x6a8,0x12f9,0x15ba,0x1861,0x2a89,0x1c5c,0xbe6,0xc1e,0x2024,0x207,0x19ce,0x2710,0x1744,0x18bc,0x2cd7,0x396,0x18d5,0x1c45,0xc4,0x21a6,0xe03,0x2b3c,0x2d91,0xc5d,0x432,0x1fbc,0xcae,0x2512,0x2979,0x3b2,0x714,0xb2e,0x1a97,0x1a03,0x1bcd,0x2216,0x2701,0xa,0x263c,0x1179,0x200c,0x2d08,0x1c34,0x291,0x2c99,0x2a5a,0x723,0xb1d,0x1ccc,0x1fb6,0x2f58,0x2bfe,0x1cda,0x2a0,0x5f1,0x2de,0x1fc7,0x1ea8,0x1719,0x2fa7,0x27ec,0x20ff,0x12c0,0x1ac1,0x2232,0x2f9b,0xd3e,0x2aed,0x15f0,0x11e8,0xed0,0x26a,0x1de5,0xa3f,0xf43,0xebf,0x204e,0xac7,0x2d9c,0x5ea,0x25d1,0xb6,0x49c,0x995,0x2555,0x26e2,0x100,0x1878,0x5aa,0x2e10,0x271c,0xcb,0x1b4c,0x2fb8,0x25b7,0x1543,0x2c7b,0x241a,0x2223,0x20ca,0x24ed,0x137,0x1b65,0x1dc2,0x7c7,0x2ec3,0xd0c,0x1169,0x1c7a,0x1ea1,0xf89,0x2199,0x291d,0x1088,0x2046,0x256d,0x2bc7,0x2e9b,0x41f,0x1b55,0x2b38,0xd0,0x2e6a,0x1755,0x6bc,0x2724,0x3ba,0x222e,0x2c5c,0x2da5,0x213c,0x10fe,0x169a,0x1552,0x5d3,0x300,0x1b5d,0x1342,0x2004,0x256f,0x2039,0x667,0x23b5,0x1123,0xdb,0x2da0,0xe1e,0x2f54,0x2767,0x154a,0x40a,0x11d3,0x2821,0xc09,0x974,0x694,0xfbf,0x27ba,0x132,0x83f,0x2d06,0x10e,0x183f,0x29ae,0x28c3,0x2dc9,0x1144,0x2c70,0x2a4a,0xf3c,0x1e32,0x1171,0x1e43,0xdd4,0x2ddf,0x28d2,0xfac,0x3c4,0x2f19,0x10a6,0x2f7,0xe1d,0x828,0x138f,0x1332,0xfab,0xcf6,0x13f8,0x24a0,0x112d,0x2717,0x6e7,0x1044,0x36e,0xfe8,0x6a,0xba7,0x1d69,0x29ec,0x23b2,0xaee,0x16df,0x1068,0x1a7e,0x253f,0x24c,0xb33,0x2683,0x15ce,0x1ad3,0x1a36,0xc96,0xaea,0x260a,0xce,0x28b1,0xe4f,0x2b11,0x5f8,0x1fc4,0xe77,0x2366,0x11f9,0x153c,0x24eb,0x20cd,0x1398,0x22,0x2b97,0x249b,0x8eb,0x12b2,0x2fe3,0x29c1,0x1b00,0x2663,0xeaa,0x2e06,0xe0,0x1569,0x10f5,0x284e,0xa38,0x201d,0x1c53,0x1681,0x1f6f,0x2f95,0x2fe8,0xacb,0x1680,0x17fd,0x2c39,0x165a,0x10bb,0x29d8,0x2622,0x1196,0x884,0x2a79,0x140e,0x2d80,0x6fa,0x11b2,0x26c4,0x355,0x1054,0x29e9,0x23ed,0xbe3,0x24fa,0x1fb3,0x10ac,0x2919,0x2584,0x10a4,0xe85,0x650,0x1893,0x1dc1,0xd8e,0x12dc,0x2d42,0x284d,0xfff,0x250f,0xacd,0x13c3,0x6cc,0x1a79,0x1221,0x2614,0x270a,0x1ea,0x155,0x2818,0x222c,0x2e5b,0x25d8,0x1dbf,0x191c,0xb0f,0xdac,0x1082,0x12ef,0x11b6,0xfa8,0x2b72,0x159d,0x209e,0x31b,0x2c7c,0x14f7,0xe09,0x1bb2,0x1ec7,0x2404,0x20ae,0x6ad,0xed6,0x2b70,0x1c7b,0x18d1,0x2732,0x12da,0xd56,0x5c1,0x1648,0x18b7,0x1605,0x1bc4,0x280,0x2ece,0xc,0x1aae,0x1c4,0x1cdb,0x22d6,0x21d8,0x257c,0x51f,0x211b,0xff,0x2ee0,0x2585,0xe1,0x2c35,0x26db,0x2971,0x2208,0x17e1,0x21be,0x135e,0x28d6,0x2891,0x1689,0x2138,0xb86,0x2e3a,0x1204,0x2d10,0x2324,0xf3f,0x2508,0x33d,0xcb2,0x292a,0xe27,0x2e64,0x29f8,0x2d46,0x9b7,0x20eb,0x1b7c,0x9eb,0x2b2a,0x58c,0x27d0,0x121b,0x272e,0x29f6,0x2dbd,0x2697,0x2aac,0xd6f,0x1c67,0x2c5b,0x108d,0x363,0x249d,0x2d5e,0x2fd,0x2cb2,0x1f8f,0x20a4,0xa19,0x2ac9,0x19b1,0x1581,0x17a2,0x29eb,0x1b72,0x13b0,0xee4,0xa8f,0x2315,0x5e6,0x951,0x2e29,0xdad,0x1f2b,0x224e,0x37f,0x1a72,0xa91,0x1407,0x2df9,0x3ad,0x23f7,0x1a24,0x1d2a,0x234b,0x1df3,0x1143,0x7ff,0x1a6d,0x2774,0x2690,0x2ab5,0x586,0x2781,0x2009,0x2fdd,0x2881,0x399,0x2fb6,0x144,0x137f,0xfa0,0x2e4c,0x1c7f,0x2fac,0xb09,0x1264,0x127b,0x198c,0x2b40,0x230,0x1cf4,0x180b,0xb58,0x144a,0x2aec,0xfb,0x2602,0x14ee,0x783,0x1098,0x23d8,0x203,0xe9,0x108a,0x14b8,0xeec,0xc58,0x1248,0x243c,0x28aa,0x6bf,0x27c4,0x276e,0x19b8,0x1d11,0x2e16,0x472,0x1464,0x24b9,0x662,0x1097,0x2067,0x20d6,0x171c,0x4,0x682,0x17bb,0x1186,0x4f2,0x3ff,0x2a43,0x1dc7,0x1ae5,0x8cc,0x2e7c,0x2ef8,0x2ae0,0x2904,0xed4,0x6c5,0x14ae,0xb72,0x11c3,0x337,0x2da3,0x2916,0x6d8,0x1cf9,0x10ee,0x1800,0x1ae4,0xa0d,0x101b,0x1a8d,0x2e98,0x24cd,0x813,0x1aa4,0x9b9,0x680,0x2349,0x24d1,0x20f8,0xe31,0x249f,0x216b,0x12d9,0x1d21,0x19db,0x191a,0x1dd0,0x5df,0x55c,0x2b86,0x213,0xe9e,0x1ef1,0x268a,0x1d5e,0x1e20,0x28c1,0x1379,0x249,0x19de,0x18b,0x1e41,0x2a1e,0x2612,0x297,0x2e96,0x2102,0x46,0x1b9f,0x1a4d,0x2050,0x1b32,0x568,0x11f7,0x1829,0x870,0x1f4,0x1dca,0x990,0x1df6,0x2b62,0x13ec,0x9f2,0x1260,0x2997,0x1412,0x1e6d,0x1694,0x11ac,0x2d8b,0x276f,0x26f5,0x233e,0x2b44,0x2f5a,0x2d37,0x2cb1,0xc75,0x98d,0x1d56,0x7ae,0x10e6,0x113f,0x17b8,0xad3,0x737,0x221e,0x1b70,0x1f3e,0x2966,0x18b2,0x4fa,0x2044,0x1312,0x154e,0x2029,0x700,0x1b45,0x27a6,0x226a,0x21bf,0x58d,0x2f11,0x2e02,0x17fc,0x4d2,0x1757,0xcb1,0x2ef1,0x2582,0x1276,0x881,0x2fc0,0x104a,0x670,0x274f,0x2b53,0x19dd,0x752,0x1663,0xcbd,0x2b2b,0x2fc6,0x13b6,0x21e6,0x15f6,0x126b,0x2637,0x1cd9,0x2f50,0xe82,0x5b0,0x24e0,0x1350,0x2f24,0x21f7,0x1a16,0x2f3e,0x167e,0x1f7d,0x28a0,0x16f0,0xe33,0x53b,0x28c5,0x1500,0x2f88,0x26cc,0x2018,0x1604,0x218b,0x2cd1,0x9ee,0x17f3,0x5fd,0x1f5a,0x2d0,0x2b46,0x23cc,0x503,0x1c46,0x1cc3,0x28e2,0x243e,0x122b,0x2e0c,0xe37,0x2611,0x85e,0x9b8,0x1b24,0x762,0x19b6,0x3bc,0x2d50,0x2079,0x18da,0x170a,0x800,0xaa2,0x135a,0x1a15,0x13d1,0xca,0x2113,0x2db9,0xdb2,0x1a5c,0x29a9,0x1488,0x14c1,0x2c9,0x917,0x28e7,0x265c,0xdab,0x2ab9,0x2bc6,0x105b,0x1839,0x219c,0x50,0x11da,0x1802,0xf56,0x2e6,0x2190,0xddb,0x56e,0x9d9,0x1c81,0x1016,0x12d6,0x296f,0x14b4,0x1014,0x1e64,0x1d90,0x89f,0x2bc2,0x2777,0x2819,0x1c65,0x1a41,0x5a2,0x2cd2,0x427,0xd71,0x29c8,0x1e58,0x53f,0x7c5,0x1dcd,0x4a1,0x1268,0x2597,0x2926,0xee,0x111b,0x1038,0xe6c,0x22dc,0x2f2f,0x441,0x2cfd,0x1cb0,0x6a4,0x2224,0x620,0x5dc,0x16b1,0x2a1d,0x1787,0x20c7,0x641,0xd84,0x1c05,0x2d0d,0x2f52,0x1b8c,0xd7d,0x17e8,0x1589,0xc73,0x151b,0x4e2,0x1ae9,0x1b18,0xb9b,0x949,0x2c60,0x1e7a,0xd5,0x1bdc,0x1f57,0x1753,0x124a,0x559,0xb76,0x2334,0x12d1,0x1de1,0x14b2,0x2faa,0x1697,0x147a,0x5a1,0x2c30,0x1c02,0x1043,0x2ee1,0x2402,0x1cc8,0x2a16,0xff7,0x1364,0x1b9a,0x2a53,0x2f94,0x294c,0x1ee5,0x1a87,0x2141,0xd66,0x953,0x28a3,0x2f30,0x2477,0x18e3,0x1035,0x1fc1,0x1d68,0x2fb3,0x138c,0x2487,0x1bf8,0xd96,0x1018,0x748,0x244e,0x15bd,0x175e,0x2be,0x23d,0x1da,0x176d,0xc17,0x24be,0x2ebb,0x7d8,0x100a,0x759,0x1db4,0x2259,0x23f4,0x2d59,0x2847,0xbf5,0x1cfe,0xa20,0x258,0x1180,0x279c,0x54,0x2abf,0xc5c,0x9f9,0x3d5,0x2ce4,0x165f,0x23d9,0x27b9,0x6f9,0x281a,0x169e,0x627,0x156d,0x1ff8,0x211,0x2e34,0x1724,0x2c2e,0x2790,0x2dd5,0x2bf2,0xdbc,0x2884,0x20a9,0x2390,0x1e1a,0x1b6a,0x5f7,0xab7,0x1333,0x16ab,0x28dd,0x20,0x30f,0x24b6,0x5c2,0x1ce4,0x1400,0x2669,0x60,0x156c,0xe20,0x26d4,0x26ab,0x1ebb,0x223d,0x5b4,0x2025,0x1e1c,0xaae,0x2e08,0x6cd,0x1677,0x13d9,0x17b5,0x1046,0x1d8c,0x14eb,0x18d8,0x1ce5,0x2478,0x16ae,0xb79,0x23d4,0x684,0x156b,0x567,0x1a,0x29ce,0x83a,0x19e8,0x58e,0x294a,0x1136,0x2319,0x2fba,0x1a29,0x1d,0x1879,0x291b,0x19f6,0x2c2f,0x21c9,0x19bb,0xbbc,0x26f9,0xc22,0x708,0x11a1,0x18d3,0x7f8,0x28f8,0x2427,0x1deb,0xaed,0x26aa,0x2482,0x203b,0x2f05,0x2b82,0x192f,0x2df4,0x8dc,0x2877,0xd5e,0x240e,0x775,0x2dae,0x1d3e,0x20ba,0x215b,0x22d1,0xeba,0xf50,0xaa8,0x184a,0x1f67,0x2e04,0xc6e,0x6dd,0x1a09,0x27f,0x494,0x1426,0xae3,0xe15,0x65f,0x13c4,0x105,0x872,0x2667,0x1ff6,0xd9f,0x2ca1,0x2f39,0x2657,0x23fd,0x2405,0xb73,0x2294,0x1f1e,0x2eba,0x110a,0x2cae,0x141f,0x22cd,0x25d6,0x11c1,0x1c,0x2d8e,0x161a,0x1aa8,0x229e,0x1bf9,0x7cf,0x106d,0x2c40,0xd93,0x255e,0x28c2,0xc1a,0x2f17,0x7ca,0x2f63,0xbf};
const sign16 iroots[]= {0x2ac8,0x452,0x297c,0x666,0xb4c,0x2b8,0x1a74,0xfd,0x1a47,0x1d08,0x2959,0x2c36,0x2db4,0x56c,0x254e,0x1125,0x2f3d,0x13bc,0x172c,0x2c6b,0x32a,0x1745,0x18bd,0x8f1,0x1633,0x2dfa,0xfdd,0x23e3,0x241b,0x13a5,0x578,0x17a0,0xa9,0x104b,0x1335,0x24e4,0x28de,0x5a7,0x368,0x2d70,0x13cd,0x2f9,0xff5,0x1e88,0x9c5,0x2ff7,0x900,0xdeb,0x1434,0x15fe,0x156a,0x24d3,0x28ed,0x2c4f,0x688,0xaef,0x2353,0x1045,0x2bcf,0x23a4,0x270,0x4c5,0x21fe,0xe5b,0xfbb,0x1f79,0x6e4,0xe68,0x2078,0x1160,0x1387,0x1e98,0x22f5,0x13e,0x283a,0x123f,0x149c,0x2eca,0xb14,0xf37,0xdde,0xbe7,0x386,0x1abe,0xa4a,0x49,0x14b5,0x2f36,0x8e5,0x1f1,0x2a57,0x1789,0x2f01,0x91f,0xaac,0x266c,0x2b65,0x2f4b,0xa30,0x2a17,0x265,0x253a,0xfb3,0x2142,0x20be,0x25c2,0x121c,0x2d97,0x2131,0x1e19,0x1a11,0x514,0x22c3,0x66,0xdcf,0x1540,0x1d41,0xf02,0x815,0x5a,0x18e8,0x1159,0x103a,0x2d23,0x2a10,0x2d61,0x1327,0x403,0x25c9,0x7b3,0x1f0c,0x1a98,0x2f21,0x1fb,0x2157,0x99e,0x1501,0x640,0x1e,0x1d4f,0x2716,0xb66,0x46a,0x2fdf,0x1c69,0xf34,0xb16,0x1ac5,0x1e08,0xc9b,0x218a,0x103d,0x2a09,0x4f0,0x21b2,0x750,0x2f33,0x9f7,0x2517,0x236b,0x15cb,0x152e,0x1a33,0x97e,0x24ce,0x2db5,0xac2,0x1583,0x1f99,0x1922,0x2513,0xc4f,0x615,0x1298,0x245a,0x2f97,0x2019,0x2c93,0x1fbd,0x291a,0x8ea,0x1ed4,0xb61,0x1c09,0x230b,0x2056,0x1ccf,0x1c72,0x27d9,0x21e4,0x2d0a,0x1f5b,0xe8,0x2c3d,0x2055,0x72f,0x222,0x222d,0x11be,0x1e90,0x11cf,0x20c5,0x5b7,0x391,0x1ebd,0x238,0x73e,0x653,0x17c2,0x2ef3,0x2fb,0x27c2,0x2ecf,0x847,0x2042,0x296d,0x268d,0x23f8,0x7e0,0x1e2e,0x2bf7,0x1ab7,0x89a,0xad,0x21e3,0x261,0x2f26,0x1ede,0xc4c,0x299a,0xfc8,0xa92,0xffd,0x1cbf,0x14a4,0x2d01,0x2a2e,0x1aaf,0x1967,0x1f03,0xec5,0x25c,0x3a5,0xdd3,0x2c47,0x8dd,0x2945,0x18ac,0x197,0x2f31,0x4c9,0x14ac,0x2be2,0x166,0x43a,0xa94,0x1b53,0x293c,0x212d,0x6fd,0x521,0x109,0x185,0x2735,0x151c,0x123a,0x5be,0x2c02,0x2b0f,0x1e7b,0x1846,0x297f,0x2ffd,0x18e5,0xf2b,0xf9a,0x1f6a,0x299f,0xb48,0x1b9d,0x2b8f,0x1eb,0x12f0,0x1649,0x893,0x83d,0x2942,0x757,0xbc5,0x1db9,0x23a9,0x2115,0x1b49,0x1f77,0x2f18,0x2dfe,0xc29,0x1f69,0x287e,0x1b13,0x9ff,0x2f06,0x515,0x1bb7,0x24a9,0x17f6,0x130d,0x2dd1,0x4c1,0x1675,0x1d86,0x1d9d,0x24f8,0x55,0x1382,0x1b5,0x2061,0x1c82,0x2ebd,0x4b,0x2c68,0x780,0x24,0xff8,0x880,0x2a7b,0x54c,0x971,0x88d,0x1594,0x2802,0x1ebe,0x120e,0xcb6,0x12d7,0x15dd,0xc0a,0x2c54,0x208,0x1bfa,0x2570,0x158f,0x2c82,0xdb3,0x10d6,0x2254,0x1d8,0x26b0,0x2a1b,0xcec,0x2572,0x211d,0x1c51,0x148f,0x616,0x185f,0x1a80,0x1650,0x538,0x25e8,0xf5d,0x1072,0x34f,0x2d04,0x2a3,0xb64,0x2c9e,0x1f74,0x3a6,0x139a,0x2292,0x555,0x96a,0x244,0x60b,0x8d3,0x1de6,0x831,0x2a75,0x4d7,0x2616,0x1485,0xf16,0x264a,0x2bb,0x609,0x19d,0x21da,0x6d7,0x234f,0x2cc4,0xaf9,0x20c2,0xcdd,0x2f1,0x1dfd,0x1c7,0x247b,0xec9,0x1978,0x770,0x72b,0x1ca3,0xe43,0x1820,0xdf9,0x690,0x926,0x3cc,0x2f20,0xa7c,0x121,0x2f02,0xee6,0x2ae2,0xa85,0xe29,0xd2b,0x1326,0x2e3d,0x1553,0x2ff5,0x133,0x2d81,0x143d,0x19fc,0x174a,0x19b9,0x2a40,0x22ab,0x1d27,0x8cf,0x1730,0x1386,0x491,0x212b,0x2954,0xf53,0xbfd,0x113a,0x144f,0x21f8,0x1b0a,0x385,0x2ce6,0xf63,0x1a64,0x48f,0x2059,0x1e4b,0x1d12,0x1f7f,0x2255,0x24f2,0x16e5,0x1242,0xa29,0x1a6,0xdd5,0x7e9,0x2eac,0x2e17,0x8f7,0x9ed,0x1de0,0x1588,0x2935,0x1c3e,0x2534,0xaf2,0x2002,0x7b4,0x2bf,0x1d25,0x2273,0x1240,0x176e,0x29b1,0x217c,0x1f5d,0xa7d,0x6e8,0x1f55,0x104e,0xb07,0x241e,0xc14,0x618,0x1fad,0x2cac,0x93d,0x1e4f,0x2907,0x281,0x1bf3,0x588,0x277d,0x1e6b,0x9df,0x629,0x1f46,0x19a7,0x3c8,0x1804,0x1981,0x2536,0x19,0x6c,0x1092,0x1980,0x13ae,0xfe4,0x2f42,0x9e,0x2837,0xea,0x23e7,0x73f,0xaa3,0x226e,0x3c1,0x1f94,0x2832,0x1408,0xd63,0x1559,0x19e7,0x273,0x2fe5,0x1e40,0xa2b,0xd34,0x1be2,0x353,0x1ef7,0x147,0x10e3,0xd6d,0x248e,0xbfc,0xc04,0x9aa,0xc8,0x360,0x2262,0x100b,0x99a,0x278f,0x2efc,0x1c3d,0x29a2,0x21ec,0x251e,0x1bdb,0x2b6d,0x2d82,0x15f8,0x2924,0x2393,0x1fd,0x109a,0x17b7,0x2559,0x20b1,0x2147,0xd30,0xea6,0xf47,0x12c3,0x253,0x288c,0xbf3,0x22a3,0x78a,0x2725,0x20d,0x16d2,0x47f,0xfc,0xfc6,0xb7f,0x957,0x2514,0x1216,0xbda,0x709,0x2809,0x172e,0x1e60,0x28f9,0x23df,0x908,0x2445,0x1646,0xe38,0x3d2,0x160b,0x6e6,0x1788,0x2fe4,0x15d8,0x47,0xce8,0x1ecb,0x6b7,0x2a73,0x1619,0x27c7,0x633,0x2fe7,0x2a9a,0x1a96,0x297d,0xc2d,0x2488,0x1953,0xb89,0x131c,0x1729,0x1b16,0x1275,0x1fbb,0x184c,0x1c28,0x198a,0x2934,0x1f9,0x2553,0x11e5,0xfdc,0x2a4d,0xdc4,0x1146,0x956,0x92d,0x21e1,0x1a95,0x2fa1,0x998,0x1c01,0x131d,0x2a3f,0xb4b,0x2cf2,0x2fe1,0x724,0x1956,0x1cce,0x254a,0x2a0a,0x1497,0x11e7,0xc71,0xf58,0x77d,0x2245,0x40f,0x22c,0x871,0x3d3,0x18dd,0x1cd,0x2df0,0x1009,0x1a94,0x29da,0x1963,0x7e7,0x2908,0x848,0xc28,0x19a2,0x31d,0x2c2c,0x2608,0x23a5,0x542,0x2fad,0x865,0x1e81,0x2da9,0x25e1,0x1303,0x240c,0x7ba,0x2a8,0xc0d,0xda8,0x124d,0x28a8,0x1ff7,0x2829,0x146,0xb43,0x23ea,0x1894,0x2e27,0x2dc4,0x2d43,0x18a3,0x1a44,0xbb3,0x28b9,0x1fe9,0x226b,0x1409,0xb7a,0x1c75,0x4e,0x1299,0x1040,0x1fcc,0x171e,0xb8a,0xd1,0x75e,0x26ae,0x229b,0xec0,0x157a,0x111c,0x6b5,0x6d,0x5ae,0x1467,0x1c9d,0x200a,0x5eb,0x1339,0xbff,0x120,0x1fbe,0x13ff,0x3d1,0x2a60,0x1b87,0x196a,0x57,0x1b4f,0x1220,0x1d30,0xccd,0x248b,0x2aa8,0x1db7,0x18ae,0x10aa,0x1425,0x2f2c,0x1187,0x3a1,0x26b8,0x2466,0x14e9,0x1518,0x2b1f,0x1ae6,0x238e,0x1a78,0x1819,0x2284,0x1475,0xaf,0x2f4,0x13fc,0x227d,0x29c0,0xf3a,0x187a,0x5e4,0x1950,0x2a25,0x29e1,0xddd,0x295d,0x1351,0x304,0x2bc0,0xd2,0xd25,0x2195,0x1fc9,0x1ee6,0x2f13,0x6db,0xa6a,0x1d99,0x2b60,0x1234,0x283c,0x2ac2,0x11a9,0x639,0x2290,0x2bda,0x32f,0x2a5f,0x15c0,0x139c,0x7e8,0x88a,0x43f,0x2762,0x1271,0x119d,0x1fed,0x1b4d,0x692,0x1d2b,0x1feb,0x1380,0x2628,0x2a93,0x2226,0xe71,0x2d1b,0x20ab,0x17ff,0x1e27,0x2fb1,0xe65,0x17c8,0x1fa6,0x43b,0x548,0x2256,0x9a5,0x71a,0x26ea,0x2d38,0x1b40,0x1b79,0x658,0x15a5,0x224f,0x248,0xeee,0x2f37,0x1c30,0x15ec,0x1ca7,0x255f,0x2801,0x18f7,0x1727,0xf88,0x2b1,0x2c45,0x164b,0x289f,0x14dd,0x2649,0x27a3,0x9f0,0x21ca,0x1f5,0x1dd6,0xbc3,0x71f,0x133e,0x13bb,0x2afe,0xc35,0x4bb,0x2d31,0x10a7,0x2a04,0x180e,0x2613,0x330,0xe76,0x19fd,0xfe9,0x935,0x79,0x1b01,0x73c,0x2ac6,0x21ce,0x1911,0x761,0x1084,0x1983,0xc3,0x15eb,0xe0a,0xdd,0x1cb1,0xb21,0x2a51,0x217f,0xb1,0x1328,0x9ca,0x1d96,0x1a0b,0xe1b,0x1c4b,0x3b,0x4d6,0x2344,0x199e,0x28af,0x1624,0x4ae,0x8b2,0x2991,0x1fb7,0x41,0x2780,0x1d8b,0xa7f,0x110,0x2350,0x18aa,0x2b2f,0x1805,0x1ff,0xf0,0x2a74,0xe42,0xd97,0x85b,0x14bc,0x2901,0xfd8,0x1ab3,0x1cef,0xfbd,0x2b07,0x174f,0x69b,0x10c3,0x1491,0xde3,0x28ca,0x252e,0x1849,0x1ec2,0x1f1b,0x2853,0x12ab,0x2674,0x238c,0x350,0x2ca,0xa7,0x4bd,0xcc3,0x90c,0x892,0x276,0x1e55,0x196d,0x1194,0x1bef,0x66a,0x1da1,0x260f,0x1c15,0x49f,0x120b,0x2671,0x1237,0x2e0d,0x2791,0x17d8,0x1e0a,0x2a99,0x14cf,0xfb1,0x15b4,0x1462,0x2fbb,0xeff,0x16b,0x2d6a,0x9ef,0x5e3,0x11c0,0x2e76,0x1623,0x2db8,0x1c88,0x740,0x11e1,0x12a3,0x977,0x1110,0x2163,0x2dee,0x47b,0x2aa5,0x2a22,0x1231,0x16e7,0x1626,0x12e0,0x1d28,0xe96,0xb62,0x21d0,0xf09,0xb30,0xcb8,0x2981,0x2648,0x155d,0x27ee,0xb34,0x169,0x1574,0x1fe6,0x25f4,0x151d,0x1801,0x1f13,0x1308,0x2929,0x6eb,0x25e,0x2cca,0x1e3e,0x248f};
const sign16 inv= 0xeab;
const sign16 invpr= 0x2c2a;

#define DEGREE (1<<RLWE_LGN)
#define WL 32

#define round(a,b) (((a)+((b)/2))/(b))

/* constant time absolute vaue */
static sign32 nabs(sign32 x)
{
	sign32 mask=(x>>31);
	return (x+mask)^mask;
}

/* Montgomery stuff */

static sign32 redc(unsign64 T)
{
	unsign32 m=(unsign32)T*(unsign32)RLWE_ND;
	return ((unsign64)m*RLWE_PRIME+T)>>WL;
}

static sign32 nres(unsign32 x)
{
	return redc((unsign64)x*RLWE_R2MODP);
}

static sign32 modmul(unsign32 a,unsign32 b)
{
	return redc((unsign64)a*b);
}

/* NTT code */
/* Cooley-Tukey NTT */

static void ntt(sign32 *x)
{
	int m,i,j,k,t=DEGREE/2;
	sign32 S,U,V,W,q=RLWE_PRIME;

/* Convert to Montgomery form */
	for (j=0;j<DEGREE;j++)
		x[j]=nres(x[j]);

	m=1;
	while (m<DEGREE)
	{
		k=0;
		for (i=0;i<m;i++)
		{
			S=roots[m+i];
			for (j=k;j<k+t;j++)
			{
				U=x[j];   
				V=modmul(x[j+t],S);
				x[j]=U+V;
				x[j+t]=U+2*q-V;
			}
			k+=2*t;
		}
		t/=2;
		m*=2;
	}
}

/* Gentleman-Sande INTT */

static void intt(sign32 *x)
{
	int m,i,j,k,t=1;
	sign32 S,U,V,W,q=RLWE_PRIME;

	m=DEGREE/2;
	while (m>1)
	{
		k=0;
		for (i=0;i<m;i++)
		{
			S=iroots[m+i];
			for (j=k;j<k+t;j++)
			{	
				U=x[j]; 
				V=x[j+t];
				x[j]=U+V;	
				W=U+DEGREE*q-V; 
				x[j+t]=modmul(W,S); 
			}
			k+=2*t;
		}
		t*=2;
		m/=2;
	}

/* Last iteration merged with n^-1 */

	t=DEGREE/2;
	for (j=0;j<t;j++)
	{
		U=x[j];
		V=x[j+t];
		W=U+DEGREE*q-V; 
		x[j+t]=modmul(W,(sign32)invpr); 
		x[j]=modmul(U+V,(sign32)inv);
	}
/* convert back from Montgomery to "normal" form */
	for (j=0;j<DEGREE;j++)
	{
		x[j]=redc(x[j]);  
		x[j]-=q;
		x[j]+=(x[j]>>(WL-1))&q;
	} 
}

/* See https://eprint.iacr.org/2016/1157.pdf */ 

static void NHSEncode(byte *key,sign32 *poly)
{
	int i,j,b,k,kj,q2;

	q2=RLWE_PRIME/2;
	for (i=j=0;i<256;)
	{
		kj=key[j++];
		for (k=0;k<8;k++)
		{
			b=kj&1;
			poly[i]=b*q2;
			poly[i+256]=b*q2;
			poly[i+512]=b*q2;
			poly[i+768]=b*q2;
			kj>>=1;
			i++;
		}
	}		
}

static void NHSDecode(sign32 *poly,byte *key)
{
	int i,j,k;
	sign32 b,t,q2;
	q2=RLWE_PRIME/2;
	for (i=0;i<32;i++)
		key[i]=0;

	for (i=j=0;i<256;)
	{
		for (k=0;k<8;k++)
		{
			t=nabs(poly[i]-q2)+nabs(poly[i+256]-q2)+nabs(poly[i+512]-q2)+nabs(poly[i+768]-q2);

			b=t-RLWE_PRIME;
			b=(b>>31)&1;
			key[j]=(key[j]>>1)+(b<<7);
			i++;
		}
		j++;
	}
}

/* convert 32-byte seed to random polynomial */

static void parse(byte *seed,sign32 *poly)
{
	int i,j;
	sign32 n;
	byte hash[4*DEGREE];
	sha3 sh;

	SHA3_init(&sh,SHAKE128);
	for (i=0;i<32;i++)
		SHA3_process(&sh,seed[i]);
	SHA3_shake(&sh,(char *)hash,4*DEGREE);

	for (i=j=0;i<DEGREE;i++)
	{

		n=hash[j]&0x7f; n<<=8;
		n+=hash[j+1]; n<<=8;
		n+=hash[j+2]; n<<=8;
		n+=hash[j+3]; j+=4;
		poly[i]=nres(n);
		//poly[i]=modmul(n,RLWE_ONE); // reduce 31-bit random number mod q
	}
} 

/* Compress 14 bits polynomial coefficients into byte array */
/* 7 bytes is 3x14 */

static void NHSpack(sign32 *poly,byte *array)
{
	int i,j;
	sign32 a,b,c,d;

	for (i=j=0;i<DEGREE; )
	{
		a=poly[i++]; b=poly[i++]; c=poly[i++]; d=poly[i++];
		array[j++]=(byte)(a&0xff);
		array[j++]=(byte)(((a>>8)|(b<<6))&0xff);
		array[j++]=(byte)((b>>2)&0xff);
		array[j++]=(byte)(((b>>10)|(c<<4))&0xff);
		array[j++]=(byte)((c>>4)&0xff);
		array[j++]=(byte)(((c>>12)|(d<<2))&0xff);
		array[j++]=(byte)(d>>6);
	}
}

static void NHSunpack(byte *array,sign32 *poly)
{
	int i,j;
	sign32 a,b,c,d,e,f,g;

	for (i=j=0;i<DEGREE; )
	{
		a=((sign32)array[j++])&0xff; b=((sign32)array[j++])&0xff; c=((sign32)array[j++])&0xff; d=((sign32)array[j++])&0xff; e=((sign32)array[j++])&0xff; f=((sign32)array[j++])&0xff; g=((sign32)array[j++])&0xff;
		poly[i++]=a|((b&0x3f)<<8);
		poly[i++]=(b>>6)|(c<<2)|((d&0xf)<<10);
		poly[i++]=(d>>4)|(e<<4)|((f&3)<<12);
		poly[i++]=(f>>2)|(g<<6);
	}
}


/* See https://eprint.iacr.org/2016/1157.pdf */ 

static void NHSCompress(sign32 *poly,byte *array)
{
	int i,j,k,b;
	unsign32 col=0;

	for (i=j=0;i<DEGREE;)
	{
		for (k=0;k<8;k++)
		{
			b=round((poly[i]*8),RLWE_PRIME)&7; 
			col=(col<<3)+b;
			i++;
		}
		array[j]=col&0xff;
		array[j+1]=(col>>8)&0xff;
		array[j+2]=(col>>16)&0xff;
		j+=3; col=0;
	}
}

static void NHSDecompress(byte *array,sign32 *poly)
{
	int i,j,k,b;
	unsign32 col=0;

	for (i=j=0;i<DEGREE;)
	{
		col=array[j+2];
		col=(col<<8)+array[j+1];
		col=(col<<8)+array[j];
		j+=3;
		for (k=0;k<8;k++)
		{
			b=(col&0xe00000)>>21; col<<=3;
			poly[i]=round((b*RLWE_PRIME),8);
			i++;
		}
	}
}

/* generate centered binomial distribution */ 

static void NHSError(csprng *RNG,sign32 *poly)
{
	int i,j;
	sign32 n1,n2,r;
	for (i=0;i<DEGREE;i++)
	{
		n1=RAND_byte(RNG)+(RAND_byte(RNG)<<8);
		n2=RAND_byte(RNG)+(RAND_byte(RNG)<<8);
		r=0;
		for (j=0;j<16;j++)
		{
			r+=(n1&1)-(n2&1);
			n1>>=1; n2>>=1;
		}
		poly[i]=(r+RLWE_PRIME);
	}
}

static void redc_it(sign32 *p)
{
	int i;
	for (i=0;i<DEGREE;i++)
		p[i]=redc(p[i]);
}

static void nres_it(sign32 *p)
{
	int i;
	for (i=0;i<DEGREE;i++)
		p[i]=nres(p[i]);
}

static void poly_mul(sign32 *p1,sign32 *p2,sign32 *p3)
{
	int i;
	for (i=0;i<DEGREE;i++)
		p1[i]=modmul(p2[i],p3[i]);
}

static void poly_add(sign32 *p1,sign32 *p2,sign32 *p3)
{
	int i;
	for (i=0;i<DEGREE;i++)
		p1[i]=(p2[i]+p3[i]);
}

static void poly_sub(sign32 *p1,sign32 *p2,sign32 *p3)
{
	int i;
	for (i=0;i<DEGREE;i++)
		p1[i]=(p2[i]+RLWE_PRIME-p3[i]);
}

/* reduces inputs < 2q */
static void poly_soft_reduce(sign32 *poly)
{
	int i;
	sign32 e;
	for (i=0;i<DEGREE;i++)
	{
		e=poly[i]-RLWE_PRIME;
		poly[i]=e+((e>>(WL-1))&RLWE_PRIME);
	}
}

/* fully reduces modulo q */
static void poly_hard_reduce(sign32 *poly)
{
	int i;
	sign32 e;
	for (i=0;i<DEGREE;i++)
	{
		e=modmul(poly[i],RLWE_ONE);
		e=e-RLWE_PRIME;
		poly[i]=e+((e>>(WL-1))&RLWE_PRIME);
	}
}

/* API files */

void NHS_SERVER_1(csprng *RNG,octet *SB,octet *S)
{
	int i;
	byte seed[32],array[1792];
	sign32 s[DEGREE],e[DEGREE],b[DEGREE];

	for (i=0;i<32;i++)
		seed[i]=RAND_byte(RNG);

	parse(seed,b);
	
	NHSError(RNG,e);
	NHSError(RNG,s);

	ntt(s);
	ntt(e);
	poly_mul(b,b,s);
	poly_add(b,b,e);
	poly_hard_reduce(b);

	redc_it(b);
	NHSpack(b,array);

	OCT_empty(SB);
	OCT_jbytes(SB,(char *)seed,32);
	OCT_jbytes(SB,(char *)array,1792);

	poly_hard_reduce(s);

	NHSpack(s,array);
	OCT_empty(S);
	OCT_jbytes(S,(char *)array,1792);

}

void NHS_CLIENT(csprng *RNG,octet *SB,octet *UC,octet *KEY)
{
	int i;
	sha3 sh;
	byte seed[32],array[1792],key[32],cc[384];
	sign32 sd[DEGREE],ed[DEGREE],u[DEGREE],k[DEGREE],c[DEGREE];
	NHSError(RNG,sd);
	NHSError(RNG,ed);

	ntt(sd);
	ntt(ed);

	for (i=0;i<32;i++)
		seed[i]=SB->val[i];

	for (i=0;i<1792;i++)
		array[i]=SB->val[i+32];

	parse(seed,u);

	poly_mul(u,u,sd);
	poly_add(u,u,ed);
	poly_hard_reduce(u);

	for (i=0;i<32;i++)
		key[i]=RAND_byte(RNG);

	SHA3_init(&sh,SHA3_HASH256);
	for (i=0;i<32;i++)
		SHA3_process(&sh,key[i]);
	SHA3_hash(&sh,(char *)key);

	NHSEncode(key,k);

	NHSunpack(array,c);
	nres_it(c);

	poly_mul(c,c,sd);
	intt(c);
	NHSError(RNG,ed);
	poly_add(c,c,ed);
	poly_add(c,c,k);

	NHSCompress(c,cc);

	SHA3_init(&sh,SHA3_HASH256);
	for (i=0;i<32;i++)
		SHA3_process(&sh,key[i]);
	SHA3_hash(&sh,(char *)key);

	OCT_empty(KEY);
	OCT_jbytes(KEY,(char *)key,32);

	redc_it(u);
	NHSpack(u,array);

	OCT_empty(UC);
	OCT_jbytes(UC,(char *)array,1792);
	OCT_jbytes(UC,(char *)cc,384);
}

void NHS_SERVER_2(octet *S,octet *UC,octet *KEY)
{
	int i;
	sha3 sh;
	sign32 c[DEGREE],s[DEGREE],k[DEGREE];
	byte array[1792],key[32],cc[384];

	for (i=0;i<1792;i++)
		array[i]=UC->val[i];

	NHSunpack(array,k);
	nres_it(k);

	for (i=0;i<384;i++)
		cc[i]=UC->val[i+1792];

	NHSDecompress(cc,c);

	for (i=0;i<1792;i++)
		array[i]=S->val[i];

	NHSunpack(array,s);

	poly_mul(k,k,s);
	intt(k);
	poly_sub(k,c,k);
	poly_soft_reduce(k);

	NHSDecode(k,key);

	SHA3_init(&sh,SHA3_HASH256);
	for (i=0;i<32;i++)
		SHA3_process(&sh,key[i]);
	SHA3_hash(&sh,(char *)key);

	OCT_empty(KEY);
	OCT_jbytes(KEY,(char *)key,32);
}