/*
	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.
*/

//
//  nhs.swift
//

//import Foundation
//import Darwin

//import amcl

/* NewHope Simple API high-level functions  */

public struct NHS
{
   	static let PRIME:Int32 = 0x3001	// q in Hex
	static let LGN:Int = 10	// Degree n=2^LGN

	static let ND:UInt32 = 0xF7002FFF	// 1/(R-q) mod R
	static let ONE: Int32 = 0x2AC8	// R mod q
	static let R2MODP: UInt64 = 0x1620	// R^2 mod q


	static let DEGREE: Int = (1<<LGN)
	static let WL: Int32 = 32

	static let inv: Int32 =  0xeab
	static let invpr: Int32 = 0x2c2a

	static let roots:[Int32] = [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];
	static let iroots:[Int32] = [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];


	private static func round(_ a: Int32,_ b: Int32) -> Int32
	{
		return (a+b/2)/b
	}

	private static func nabs(_ x: Int32) -> Int32
	{
		let mask=(x>>31)
		return (x+mask)^mask		
	}

/* Montgomery stuff */

	private static func redc(_ T: UInt64) -> Int32
	{
		let m:UInt32=(UInt32(T&0xffffffff) &* ND)
		return Int32((UInt64(m)*UInt64(PRIME)+T)>>UInt64(WL))		
	}

	private static func nres(_ x: Int32) -> Int32 
	{
		return redc(UInt64(x)*R2MODP)
	}

	private static func modmul(_ a: Int32,_ b: Int32) -> Int32 
	{
		return redc(UInt64(a)*UInt64(b));
	}

/* Cooley-Tukey NTT */
	private static func ntt(_ x:inout [Int32]) 
	{
		var t=DEGREE/2
		let q=PRIME

/* Convert to Montgomery form */
		for j in 0..<DEGREE {x[j]=nres(x[j])}
		var m=1
		while m<DEGREE {
			var k=0
			for i in 0..<m {
				let S=roots[m+i]
				for j in k..<k+t {
					let U=x[j]
					let 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 */

	private static func intt(_ x:inout [Int32]) 
	{
		var t=1
		let q=PRIME
		var m=DEGREE/2
		while m>1 {
			var k=0
			for i in 0..<m {
				let S=iroots[m+i]
				for j in k..<k+t {	
					let U=x[j] 
					let V=x[j+t]
					x[j]=U+V
					let W=U+Int32(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 in 0..<t {
			let U=x[j]
			let V=x[j+t]
			let W=U+Int32(DEGREE)*q-V 
			x[j+t]=modmul(W,invpr)
			x[j]=modmul(U+V,inv)
		}
/* convert back from Montgomery to "normal" form */
		for j in 0..<DEGREE {
			x[j]=redc(UInt64(x[j]))
			x[j]-=q
			x[j]+=(x[j]>>(WL-1))&q
		} 
	}

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

	private static func encode(_ key: [UInt8],_ poly:inout [Int32]) {

		let q2=PRIME/2
		var j=0
		var i=0
		while i<256  {
			var kj=key[j]
			j+=1
			for _ in 0..<8 {
				let b=Int32(kj&1)
				poly[i]=b*q2
				poly[i+256]=b*q2
				poly[i+512]=b*q2
				poly[i+768]=b*q2
				kj>>=1
				i+=1
			}
		}			
	}

	private static func decode(_ poly: [Int32],_ key:inout [UInt8]) {
		let q2=PRIME/2
		for i in 0..<32 {
			key[i]=0;
		}

		var i=0
		var j=0
		while i<256 {
			for _ in 0..<8 {
				let t=nabs(poly[i]-q2)+nabs(poly[i+256]-q2)+nabs(poly[i+512]-q2)+nabs(poly[i+768]-q2)
				var b=t-PRIME
				b=(b>>31)&1
				key[j]=(key[j]>>1)+UInt8(b<<7)
				i+=1
			}
			j+=1
		}
	}
/* convert 32-byte seed to random polynomial */

	private static func parse(_ seed: [UInt8],_ poly:inout [Int32]) {
		var hash=[UInt8](repeating:0,count:4*DEGREE)

		var sh=SHA3(SHA3.SHAKE128)

		for i in 0..<32 {
			sh.process(seed[i])
		}
		sh.shake(&hash,4*DEGREE)

		var j=0
		for i in 0..<DEGREE {
			var n=Int32(hash[j]&0x7f); n<<=8
			n+=Int32(hash[j+1]); n<<=8
			n+=Int32(hash[j+2]); n<<=8
			n+=Int32(hash[j+3]); j+=4
			poly[i]=nres(n)
			//poly[i]=modmul(n,ONE); // reduce 31-bit random number mod q
		}
	} 
/* Compress 14 bits polynomial coefficients into byte array */
/* 7 bytes is 3x14 */

	private static func nhs_pack(_ poly: [Int32],_ array:inout [UInt8]) {
		var j=0
		var i=0
		while i<DEGREE  {
			let a=poly[i]; let b=poly[i+1]; let c=poly[i+2]; let d=poly[i+3]; i+=4
			array[j]=UInt8(a&0xff)
			array[j+1]=UInt8(((a>>8)|(b<<6))&0xff)
			array[j+2]=UInt8((b>>2)&0xff)
			array[j+3]=UInt8(((b>>10)|(c<<4))&0xff)
			array[j+4]=UInt8((c>>4)&0xff)
			array[j+5]=UInt8(((c>>12)|(d<<2))&0xff)
			array[j+6]=UInt8(d>>6)
			j+=7
		}
	}

	private static func nhs_unpack(_ array: [UInt8],_ poly:inout [Int32]) {
		var j=0
		var i=0
		while i<DEGREE {
			let a=Int32((array[j])&0xff); let b=Int32((array[j+1])&0xff); let c=Int32((array[j+2])&0xff); let d=Int32((array[j+3])&0xff); let e=Int32((array[j+4])&0xff); let f=Int32((array[j+5])&0xff); let g=Int32((array[j+6])&0xff); j+=7
			poly[i]=a|((b&0x3f)<<8)
			poly[i+1]=(b>>6)|(c<<2)|((d&0xf)<<10)
			poly[i+2]=(d>>4)|(e<<4)|((f&3)<<12)
			poly[i+3]=(f>>2)|(g<<6)
			i+=4
		}
	}
/* See https://eprint.iacr.org/2016/1157.pdf */ 

	private static func compress(_ poly: [Int32],_ array:inout [UInt8]) {
	
		var col:Int32=0
		var j=0
		var i=0
		while i<DEGREE  {
			for _ in 0..<8  {
				let b=round((poly[i]*8),PRIME)&7 
				col=(col<<3)+b
				i+=1
			}
			array[j]=UInt8(col&0xff)
			array[j+1]=UInt8((col>>8)&0xff)
			array[j+2]=UInt8((col>>16)&0xff)
			j+=3; col=0
		}
	}

	private static func decompress(_ array: [UInt8],_ poly:inout [Int32]) {
		var col:Int32=0
		var j=0
		var i=0
		while i<DEGREE  {
			col=Int32(array[j+2])&0xff;
			col=(col<<8)+(Int32(array[j+1])&0xff)
			col=(col<<8)+(Int32(array[j])&0xff)
			j+=3
			for _ in 0..<8 {
				let b=(col&0xe00000)>>21; col<<=3
				poly[i]=round((b*PRIME),8)
				i+=1
			}
		}
	}
/* generate centered binomial distribution */ 

	private static func error(_ rng: inout RAND,_ poly:inout [Int32]) {
		var r: Int32
		for i in 0..<DEGREE {
			var n1=(Int32(rng.getByte())&0xff)+((Int32(rng.getByte())&0xff)<<8)
			var n2=(Int32(rng.getByte())&0xff)+((Int32(rng.getByte())&0xff)<<8)
			r=0
			for _ in 0..<16 {
				r+=(n1&1)-(n2&1)
				n1>>=1; n2>>=1
			}
			poly[i]=(r+PRIME);
		}
	}

	private static func redc_it(_ p:inout [Int32]) {
		for i in 0..<DEGREE {
			p[i]=redc(UInt64(p[i]))
		}
		
	}

	private static func nres_it(_ p:inout [Int32]) {
		for i in 0..<DEGREE {
			p[i]=nres(p[i])
		}
		
	}

	private static func poly_mul(_ p1:inout [Int32],_ p2: [Int32],_ p3: [Int32]) {
		for i in 0..<DEGREE {
			p1[i]=modmul(p2[i],p3[i])
		}
	}

	private static func poly_add(_ p1:inout [Int32],_ p2: [Int32],_ p3: [Int32]) {
		for i in 0..<DEGREE {
			p1[i]=(p2[i]+p3[i])
		}
	}

	private static func poly_sub(_ p1:inout [Int32],_ p2: [Int32],_ p3: [Int32]) {
		for i in 0..<DEGREE {
			p1[i]=(p2[i]+PRIME-p3[i])
		}
	}
/* reduces inputs < 2q */
	private static func poly_soft_reduce(_ poly:inout [Int32]) {
		for i in 0..<DEGREE {
			let e=poly[i]-PRIME
			poly[i]=e+((e>>(WL-1))&PRIME)
		}
	}

/* fully reduces modulo q */
	private static func poly_hard_reduce(_ poly:inout [Int32]) {
		for i in 0..<DEGREE {
			var e=modmul(poly[i],ONE)
			e=e-PRIME
			poly[i]=e+((e>>(WL-1))&PRIME)
		}
	}
/* API files */

	public static func SERVER_1(_ rng: inout RAND,_ SB:inout [UInt8],_ S:inout [UInt8]) {
		var seed=[UInt8](repeating:0,count:32)
		var array=[UInt8](repeating:0,count:1792)
		var s=[Int32](repeating:0,count:DEGREE)
		var e=[Int32](repeating:0,count:DEGREE)
		var b=[Int32](repeating:0,count:DEGREE)

		for i in 0..<32 {
			seed[i]=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)
		nhs_pack(b,&array)

		for i in 0..<32 {
			SB[i]=seed[i]
		}

		for i in 0..<1792 {
			SB[i+32]=array[i]
		}

		poly_hard_reduce(&s)
		nhs_pack(s,&array)

		for i in 0..<1792 {
			S[i]=array[i]
		}
	}

	public static func CLIENT(_ rng: inout RAND,_ SB: [UInt8],_ UC:inout [UInt8],_ KEY:inout [UInt8]) {
		var sh=SHA3(SHA3.HASH256)
		var seed=[UInt8](repeating:0,count:32)
		var array=[UInt8](repeating:0,count:1792)
		var key=[UInt8](repeating:0,count:32)
		var cc=[UInt8](repeating:0,count:384)

		var sd=[Int32](repeating:0,count:DEGREE)
		var ed=[Int32](repeating:0,count:DEGREE)
		var u=[Int32](repeating:0,count:DEGREE)
		var k=[Int32](repeating:0,count:DEGREE)
		var c=[Int32](repeating:0,count:DEGREE)

		error(&rng,&sd)
		error(&rng,&ed)

		ntt(&sd)
		ntt(&ed)

		for i in 0..<32 {
			seed[i]=SB[i]
		}

		for i in 0..<1792 {
			array[i]=SB[i+32]
		}

		parse(seed,&u)

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

		for i in 0..<32 {
			key[i]=rng.getByte()
		}

		for i in 0..<32 {
			sh.process(key[i])
		}
		sh.hash(&key)

		encode(key,&k)

		nhs_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=SHA3(SHA3.HASH256)
		for i in 0..<32 {
			sh.process(key[i])
		}
		sh.hash(&key);

		for i in 0..<32 {
			KEY[i]=key[i]
		}

		redc_it(&u)
		nhs_pack(u,&array)

		for i in 0..<1792 {
			UC[i]=array[i]
		}

		for i in 0..<384 {
			UC[i+1792]=cc[i]
		}
	}

	public static func SERVER_2(_ S: [UInt8],_ UC: [UInt8],_ KEY:inout [UInt8]) {
		var sh=SHA3(SHA3.HASH256)

		var c=[Int32](repeating:0,count:DEGREE)
		var k=[Int32](repeating:0,count:DEGREE)
		var s=[Int32](repeating:0,count:DEGREE)

		var array=[UInt8](repeating:0,count:1792)
		var key=[UInt8](repeating:0,count:32)
		var cc=[UInt8](repeating:0,count:384)

		for i in 0..<1792 {
			array[i]=UC[i]
		}

		nhs_unpack(array,&k)
		nres_it(&k)

		for i in 0..<384 {
			cc[i]=UC[i+1792]
		}

		decompress(cc,&c)

		for i in 0..<1792 {
			array[i]=S[i]
		}

		nhs_unpack(array,&s)

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

		decode(k,&key)

		for i in 0..<32 {
			sh.process(key[i])
		}
		sh.hash(&key)

		for i in 0..<32 {
			KEY[i]=key[i]
		}
	}

}
/*
public func TestNHS()
{
	var S=[UInt8](repeating:0,count:1792)
	var SB=[UInt8](repeating:0,count:1824)
	var UC=[UInt8](repeating:0,count:2176)
	var KEYA=[UInt8](repeating:0,count:32)
	var KEYB=[UInt8](repeating:0,count:32)


	var RAW=[UInt8](repeating: 0,count: 100)
	let srng=RAND()
				let crng=RAND()
				crng.clean()
    
	srng.clean()
	for i in 0..<100 {RAW[i]=UInt8((i+1)&0xff)}
	srng.seed(100,RAW)
				
				for i in 0..<100 {RAW[i]=UInt8((i+2)&0xff)}
				crng.seed(100,RAW)


	NHS.SERVER_1(srng,&SB,&S)
				NHS.CLIENT(crng,SB,&UC,&KEYB)

 			   	for i in 0..<32 {
            				let h=String(KEYB[i],radix:16)
            				print("\(h)", terminator: "")
        			}
        			print("")

	NHS.SERVER_2(S,UC,&KEYA)

	for i in 0..<32 {
            	let h=String(KEYA[i],radix:16)
            	print("\(h)", terminator: "")
        }
        print("")
}

*/