/*
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 high-level functions  */

//import amcl.SHA3;
//import amcl.RAND;

package org.apache.milagro.amcl;

public final class NHS {

	public static final int RLWE_PRIME=0x3001;	// q in Hex
	public final static int RLWE_LGN=10;		// Degree n=2^LGN
	public final static long RLWE_ND=0xF7002FFFL;	// 1/(R-q) mod R
	public final static int RLWE_ONE=0x2AC8;		// R mod q
	public final static int RLWE_R2MODP=0x1620;	// R^2 mod q

	public final static int DEGREE=(1<<RLWE_LGN);
	public final static int WL=32;

	public final static int[] 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};
	public final static int[] 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};
	public final static int inv= 0xeab;
	public final static int invpr= 0x2c2a;

	static int round(int a,int b)
	{
		return (a+b/2)/b;
	}
	
/* constant time absolute vaue */
	static int nabs(int x)
	{
		int mask=(x>>31);
		return (x+mask)^mask;
	}

/* Montgomery stuff */

	static int redc(long T)
	{
		long m=(T*RLWE_ND)&0xffffffffL;
		return (int)((m*RLWE_PRIME+T)>>>WL);
	}

	static int nres(int x)
	{
		return redc((long)x*RLWE_R2MODP);
	}

	static int modmul(int a,int b)
	{
		return redc((long)a*b);
	}

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

	static void ntt(int[] x)
	{
		int m,i,j,k,t=DEGREE/2;
		int 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(int[] x)
	{
		int m,i,j,k,t=1;
		int 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,invpr); 
			x[j]=modmul(U+V,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 Encode(byte[] key,int[] 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 Decode(int[] poly,byte[] key)
	{
		int i,j,k;
		int 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]=(byte)((((int)key[j]&0xff)>>1) + (b<<7));
				i++;
			}
			j++;
		}
	}

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

	static void Parse(byte[] seed,int[] poly)
	{
		int i,j;
		int n;
		byte[] hash=new byte[4*DEGREE];
		SHA3 sh=new SHA3(SHA3.SHAKE128);

		for (i=0;i<32;i++)
			sh.process(seed[i]);
		sh.shake(hash,4*DEGREE);

		for (i=j=0;i<DEGREE;i++)
		{
			n=(int)hash[j]&0x7f; n<<=8;
			n+=(int)hash[j+1]&0xff; n<<=8;
			n+=(int)hash[j+2]&0xff; n<<=8;
			n+=(int)hash[j+3]&0xff; 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 pack(int[] poly,byte[] array)
	{
		int i,j,k;
		int 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 unpack(byte[] array,int[] poly)
	{
		int i,j,k;
		int a,b,c,d,e,f,g;

		for (i=j=0;i<DEGREE; )
		{
			a=((int)array[j++])&0xff; b=((int)array[j++])&0xff; c=((int)array[j++])&0xff; d=((int)array[j++])&0xff; e=((int)array[j++])&0xff; f=((int)array[j++])&0xff; g=((int)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 Compress(int[] poly,byte[] array)
	{
		int i,j,k,b;
		int 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]=(byte)(col&0xff);
			array[j+1]=(byte)((col>>>8)&0xff);
			array[j+2]=(byte)((col>>>16)&0xff);
			j+=3; col=0;
		}
	}

	static void Decompress(byte[] array,int[] poly)
	{
		int i,j,k,b;
		int col=0;

		for (i=j=0;i<DEGREE;)
		{
			col=(int)array[j+2]&0xff;
			col=(col<<8)+((int)array[j+1]&0xff);
			col=(col<<8)+((int)array[j]&0xff);
			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 Error(RAND RNG,int[] poly)
	{
		int i,j;
		int n1,n2,r;
		for (i=0;i<DEGREE;i++)
		{
			n1=RNG.getByte()+(RNG.getByte()<<8);
			n2=RNG.getByte()+(RNG.getByte()<<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(int[] p)
	{
		int i;
		for (i=0;i<DEGREE;i++)
			p[i]=redc(p[i]);
	}

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

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

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

	static void poly_sub(int[] p1,int[] p2,int[] 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(int[] poly)
	{
		int i;
		int 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(int[] poly)
	{
		int i;
		int 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 */

	public static void SERVER_1(RAND RNG,byte[] SB,byte[] S)
	{
		int i;
		byte[] seed=new byte[32];
		byte[] array=new byte[1792];

		int[] s=new int[DEGREE];
		int[] e=new int[DEGREE];
		int[] b=new int[DEGREE];

		for (i=0;i<32;i++)
			seed[i]=(byte)RNG.getByte();

		Parse(seed,b);

		Error(RNG,e);
		Error(RNG,s);

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

		redc_it(b);
		pack(b,array);
		
		for (i=0;i<32;i++)
			SB[i]=seed[i];
		for (i=0;i<1792;i++)
			SB[i+32]=array[i];

		poly_hard_reduce(s);

		pack(s,array);

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

	}

	public static void CLIENT(RAND RNG,byte[] SB,byte[] UC,byte[] KEY)
	{
		int i;
		SHA3 sh=new SHA3(SHA3.HASH256);

		byte[] seed=new byte[32];
		byte[] array=new byte[1792];
		byte[] key=new byte[32];
		byte[] cc=new byte[384];

		int[] sd=new int[DEGREE];
		int[] ed=new int[DEGREE];
		int[] u=new int[DEGREE];
		int[] k=new int[DEGREE];
		int[] c=new int[DEGREE];
		
		Error(RNG,sd);
		Error(RNG,ed);

		ntt(sd);
		ntt(ed);

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

		for (i=0;i<1792;i++)
			array[i]=SB[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]=(byte)RNG.getByte();

		for (i=0;i<32;i++)
			sh.process(key[i]);
		sh.hash(key);

		Encode(key,k);

		unpack(array,c);
		nres_it(c);

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

		Compress(c,cc);

		sh.init(SHA3.HASH256);
		for (i=0;i<32;i++)
			sh.process(key[i]);
		sh.hash(key);

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

		redc_it(u);
		pack(u,array);

		for (i=0;i<1792;i++)
			UC[i]=array[i];
		for (i=0;i<384;i++)
			UC[i+1792]=cc[i];

	}

	public static void SERVER_2(byte[] S,byte[] UC,byte[] KEY)
	{
		int i;
		SHA3 sh=new SHA3(SHA3.HASH256);

		int[] c=new int[DEGREE];
		int[] s=new int[DEGREE];
		int[] k=new int[DEGREE];

		byte[] array=new byte[1792];
		byte[] key=new byte[32];
		byte[] cc=new byte[384];

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

		unpack(array,k);
		nres_it(k);

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

		Decompress(cc,c);

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

		unpack(array,s);

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

		Decode(k,key);

		for (i=0;i<32;i++)
			sh.process(key[i]);
		sh.hash(key);

		for (i=0;i<32;i++)
			KEY[i]=key[i];
	}
/*
	public static void main(String[] args) {
		int i;
		byte[] RAW=new byte[100];
		byte[] S=new byte[1792];
		byte[] SB=new byte[1824];
		byte[] UC=new byte[2176];
		byte[] KEYA=new byte[32];
		byte[] KEYB=new byte[32];

		RAND SRNG=new RAND();
		RAND CRNG=new RAND();
		SRNG.clean(); CRNG.clean();

		for (i=0;i<100;i++) RAW[i]=(byte)(i+1);
		SRNG.seed(100,RAW);

										for (i=0;i<100;i++) RAW[i]=(byte)(i+2);
										CRNG.seed(100,RAW);

// NewHope Simple key exchange

		SERVER_1(SRNG,SB,S);
										CLIENT(CRNG,SB,UC,KEYB);
		SERVER_2(S,UC,KEYA);

		System.out.printf("Alice key= 0x");
		for (i=0;i<KEYA.length;i++)
			System.out.printf("%02x", KEYA[i]);
		System.out.println();


										System.out.printf("Bob's key= 0x");
										for (i=0;i<KEYA.length;i++)
											System.out.printf("%02x", KEYB[i]);
										System.out.println();
	} */
}