#### Keygen (n=256):
kgseed = 9db3d7a9f2b2987d065fbed8910516e8
f = [2,0,0,0,2,-2,-1,0,0,-1,1,1,-1,0,1,1,0,1,-1,1,-1,0,0,0,2,0,-1,1,-1,-1,1,-1,0,1,2,1,1,-1,-1,-2,1,0,-1,0,-1,0,0,0,-1,1,1,2,-1,0,0,-1,0,-2,1,-1,0,1,-2,1,0,0,-1,0,0,0,1,1,1,-1,0,-1,-1,0,0,1,0,-2,0,0,2,0,1,0,-1,-1,-1,-1,0,-1,-1,-2,-2,-1,1,-1,1,2,1,0,0,-1,-1,-1,2,-1,0,-1,2,0,1,0,2,-2,0,-2,1,-1,-1,1,0,-1,2,1,0,1,1,0,0,-1,1,1,0,-1,-2,0,0,1,-1,0,0,-1,0,1,1,-2,1,1,0,0,-1,1,-1,2,-1,-1,1,1,0,1,2,2,1,-2,-1,-1,0,0,1,0,0,-1,1,1,-1,1,0,0,0,-1,2,-1,-1,0,1,1,1,1,1,0,0,0,-1,0,-2,-1,-1,0,1,-2,0,2,-1,1,2,-1,0,1,0,1,1,0,-2,0,1,1,1,1,0,0,-1,-1,0,1,0,1,1,-1,1,-1,1,0,0,1,1,2,-2,-2,0,0,-2,0,-1,-1,1,-1,0,1,1,0,-1,1]
g = [0,1,-1,-1,1,2,0,1,1,0,1,1,1,0,0,0,2,0,-1,1,0,1,-1,-1,1,1,0,-1,0,0,-1,-2,1,-1,0,0,2,0,0,-2,-1,0,1,-1,-1,0,2,0,1,0,0,0,0,-1,0,-1,0,2,0,1,2,0,-2,2,1,-1,0,-2,-1,0,0,-2,-1,-1,0,-1,0,1,0,-1,0,-2,0,2,-1,-1,1,1,-1,1,1,1,1,0,2,0,1,-1,0,0,1,-1,-1,0,1,1,-1,-1,1,-1,-1,0,1,1,0,2,-1,0,-1,1,-1,0,1,1,1,-1,0,1,2,0,-2,-1,0,-2,-1,1,1,-1,-1,1,-1,2,2,-1,1,-1,0,0,0,-1,1,1,1,-1,-1,0,0,-2,0,0,-2,1,2,-1,0,-1,-1,-1,-1,1,1,0,-1,0,0,0,-1,-2,-1,1,1,0,-2,1,1,1,-2,1,0,-1,-2,0,1,0,0,1,0,-1,0,0,-1,0,2,1,1,0,-1,1,2,0,-1,1,0,1,0,0,0,1,-1,0,0,-1,0,0,1,0,0,-1,0,0,-2,2,-1,0,-1,1,0,0,0,-1,1,1,0,0,-2,1,0,0,1,-2,-2,-1,-1,-1,1,2]
F = [-7,2,6,2,4,3,-2,-4,-6,1,-7,-6,-1,-3,0,-1,0,6,14,0,-2,-8,-5,-1,0,-1,14,7,4,0,2,-1,-1,-2,-6,4,-1,-7,-5,10,0,0,6,5,-9,-2,1,-4,2,-3,0,3,11,6,1,-2,-2,-1,-5,1,4,-4,5,-6,-2,-3,12,-7,3,4,-5,-8,-2,5,-8,3,7,-3,4,5,4,-6,1,1,0,-1,-7,-5,-1,6,-5,5,-5,-2,-5,7,-2,5,-8,-1,2,-2,2,6,-1,-6,-1,0,-1,3,-1,-4,3,2,3,-3,3,2,0,2,-6,2,3,-1,-5,2,4,4,-1,-2,5,6,-4,2,2,-6,-5,2,3,-3,7,-5,1,0,0,-3,0,-2,2,-6,0,-4,-1,-1,-6,-2,11,2,5,-1,-9,2,2,-1,7,3,2,-2,1,0,-9,12,-2,-4,3,-3,2,-1,-1,10,0,2,-3,-3,-1,1,-2,10,2,8,-1,-1,3,-6,-5,3,-5,-5,3,7,2,6,-2,2,-7,7,-2,4,-5,0,-1,4,-2,5,6,0,7,-3,-2,2,7,1,0,-3,-3,-9,8,-6,2,12,0,-7,0,4,-8,-7,6,7,6,-3,-6,2,5,0,-3,-4,-1,2,3,0,5,-1,4,-3,1,2]
G = [-4,-6,5,2,-3,1,7,4,-3,-1,0,1,5,2,-8,9,4,-4,-1,7,3,-7,-6,4,-2,1,-1,2,7,4,-2,-1,0,3,-3,0,-1,3,5,0,1,0,4,0,0,-3,4,6,-3,-5,1,7,-6,3,3,-4,-1,4,-3,-4,2,0,1,-3,-5,5,2,2,-3,-2,1,-2,-7,0,5,0,-5,-2,-1,0,2,-3,-8,-1,0,-1,-4,3,2,-3,3,-1,4,-9,2,7,8,-5,1,2,0,3,1,0,-4,0,1,2,8,2,-5,1,0,1,1,-5,-7,-8,18,9,-7,0,11,5,-4,-5,-8,-1,-2,3,-3,5,1,3,-14,2,1,0,-6,-9,1,8,6,-4,-5,1,-3,-4,-4,0,0,1,6,5,5,-8,-6,-4,0,0,3,6,-6,7,-5,-2,-3,-4,-9,-7,7,2,-2,0,4,-4,-4,2,-1,-1,3,0,-6,-1,0,1,0,-2,-1,0,8,4,1,-4,3,4,-6,2,1,1,4,-1,2,1,-3,-4,2,3,-6,-10,-2,-1,10,0,1,-3,-5,-10,-3,-1,-1,-7,0,7,1,0,-2,5,5,4,-4,-6,-3,3,-2,-1,2,7,-3,-2,-2,3,-1,2,-7,-7,1,7,0,0,9,-1,-6,0,-8,1]
q00 = [556,8,-33,-1,22,-50,-25,-10,-23,-1,4,-8,-13,25,35,-23,25,0,-9,-18,0,-33,-28,33,17,-43,-13,-20,27,40,4,28,7,-8,21,-43,-8,23,-30,-24,0,-3,3,5,6,2,-31,22,13,-1,48,-20,-6,-9,-24,-25,13,3,26,-59,-17,-8,0,26,10,-19,6,15,-26,-54,-32,-16,4,-16,-28,9,44,-42,-4,52,8,14,-4,-13,-6,-14,27,38,-43,4,18,-12,36,34,10,-6,-14,-30,-2,-5,19,-7,-22,15,58,0,-23,25,-16,-36,27,4,25,-7,-3,-28,62,-18,-3,-9,14,0,-15,15,14,-18,8,17,0,-17,-8,18,-14,-15,15,0,-14,9,3,18,-62,28,3,7,-25,-4,-27,36,16,-25,23,0,-58,-15,22,7,-19,5,2,30,14,6,-10,-34,-36,12,-18,-4,43,-38,-27,14,6,13,4,-14,-8,-52,4,42,-44,-9,28,16,-4,16,32,54,26,-15,-6,19,-10,-26,0,8,17,59,-26,-3,-13,25,24,9,6,20,-48,1,-13,-22,31,-2,-6,-5,-3,3,0,24,30,-23,8,43,-21,8,-7,-28,-4,-40,-27,20,13,43,-17,-33,28,33,0,18,9,0,-25,23,-35,-25,13,8,-4,1,23,10,25,50,-22,1,33,-8]
q01 = [0,234,19,38,-97,200,-85,-152,138,90,45,151,-79,-235,6,215,-11,-64,235,220,-327,-222,5,-257,164,79,13,-48,223,160,-34,-102,277,-14,-356,168,-11,-50,56,209,-244,27,409,-208,-19,140,-3,-470,203,297,51,-128,-135,4,73,176,-48,-213,283,186,-210,-114,110,112,-9,-21,153,-113,-151,-209,-304,19,234,132,-263,-8,209,-15,-26,31,-98,-175,-12,-135,-77,297,122,282,-178,49,-222,129,-189,-6,-35,172,-299,170,-48,68,61,62,-28,135,-30,-112,207,138,109,-140,-232,-87,172,152,3,136,210,-175,-23,-363,-127,61,-78,-149,-19,152,-45,-236,250,261,-115,-2,-175,-187,-8,160,273,199,55,-160,17,21,238,-211,-58,-117,77,-50,-270,249,-14,-225,-111,142,143,106,-201,-157,29,-60,-256,-315,-89,-13,238,328,178,-193,-96,19,87,-156,-382,154,-177,-262,25,284,361,-33,137,-282,-180,44,8,-208,217,497,-4,13,-80,152,187,-54,-280,-215,169,219,-110,35,-48,206,-55,191,-169,-92,-245,101,-227,-81,-32,92,-72,-72,229,81,-27,-14,131,209,50,167,-83,-183,-325,-84,190,-95,77,179,-40,48,232,-209,11,-111,-10,-111,-148,-190,138,248,217,-304,201,378,-233,-300,-120,91,-131,-60,-67,154,207,-233]
q11 = [10383,283,-1749,-927,533,-1426,-767,-463,-400,839,1364,-455,-58,1955,485,-1013,-615,-164,-228,-867,-717,231,206,1581,511,-838,-649,1143,136,-693,231,647,-1658,-392,1478,-296,-468,719,-157,-251,-66,745,71,210,-877,-227,-1424,-488,459,1706,686,170,515,23,-572,607,-1301,215,1039,-610,-1488,547,1233,-241,500,798,-1284,634,-133,-1357,-759,933,108,-395,-17,-144,1316,480,-11,-95,520,-702,-158,437,-409,260,571,-321,17,470,703,355,391,-634,-570,-179,95,-1243,518,635,584,-261,-780,-326,733,698,261,291,-808,-1474,453,-160,729,175,679,-728,985,-497,-1651,-349,573,-774,-412,-132,22,1124,500,-960,0,960,-500,-1124,-22,132,412,774,-573,349,1651,497,-985,728,-679,-175,-729,160,-453,1474,808,-291,-261,-698,-733,326,780,261,-584,-635,-518,1243,-95,179,570,634,-391,-355,-703,-470,-17,321,-571,-260,409,-437,158,702,-520,95,11,-480,-1316,144,17,395,-108,-933,759,1357,133,-634,1284,-798,-500,241,-1233,-547,1488,610,-1039,-215,1301,-607,572,-23,-515,-170,-686,-1706,-459,488,1424,227,877,-210,-71,-745,66,251,157,-719,468,296,-1478,392,1658,-647,-231,693,-136,-1143,649,838,-511,-1581,-206,-231,717,867,228,164,615,1013,-485,-1955,58,455,-1364,-839,400,463,767,1426,-533,927,1749,-283]
priv = 9db3d7a9f2b2987d065fbed8910516e821b6c08a71585a4e5abaecdd0a751d1c057d02d339c5c6c3fd3025b383a8546d749b3c9676216fc55355aaae66c49ead3e19870659079c12c59ac8bd196bf68cb8582166a45066070c110559615872ab
pub = ec9b6c0eda42fa38f2663c896f34ee24040160234e1690c3f2b019a008c00e51b1b911e1e754756ebf408c6284b70dc059d0c56d680d0fd04a9a97eb7fe4edc4d2a0c80d56da368ac845842aad07324d7d1ad8fcc626d988eda3400eb8e7228abbfffeb6f7fbfffbef7f7fed5faffffbfefe9f05d030b3c836d918337b6c1f7545e3e0dd7c88dbb18fd968524e7537c34bfac89d00ea132660c854978a5a2d974eea06d70a3febdc46dd0500a44f0d2fdfa02165150d63a80a3138d1f31b99cf128c02d5cb29337f860449b02fd41bbad1716e700814997096d02f13ea840607d10e191f61ae0b864c297a1ab131dd81bc0522ac2aaa2f443d3e1b871d6fcf8a6d8be756ac980388d2ae166a7e3d4d9412982cebfa057201aeba07a011c7379f1115eed239744d310df90de06e8e8f6ac89c1d3bff3a580cee48b2c05f13579b7d9ab005191c69208919b32c08cfd9f1030d4f98bb3517d6a9db6d232fce36bfa85bf465e2501f5c4747e5511a0d83d132a752b64453be5e4db32730e8d00b6e096e93bd8af8d92fc97ae82b775b823b429acfe8ffffeffedbbf6ffffdbff77ffbefffffef7f7fffefff7b7fb7eef7f7fffffffbffbfed3f00000000000000000000
#### Sign (n=256):
f = [2,0,0,0,2,-2,-1,0,0,-1,1,1,-1,0,1,1,0,1,-1,1,-1,0,0,0,2,0,-1,1,-1,-1,1,-1,0,1,2,1,1,-1,-1,-2,1,0,-1,0,-1,0,0,0,-1,1,1,2,-1,0,0,-1,0,-2,1,-1,0,1,-2,1,0,0,-1,0,0,0,1,1,1,-1,0,-1,-1,0,0,1,0,-2,0,0,2,0,1,0,-1,-1,-1,-1,0,-1,-1,-2,-2,-1,1,-1,1,2,1,0,0,-1,-1,-1,2,-1,0,-1,2,0,1,0,2,-2,0,-2,1,-1,-1,1,0,-1,2,1,0,1,1,0,0,-1,1,1,0,-1,-2,0,0,1,-1,0,0,-1,0,1,1,-2,1,1,0,0,-1,1,-1,2,-1,-1,1,1,0,1,2,2,1,-2,-1,-1,0,0,1,0,0,-1,1,1,-1,1,0,0,0,-1,2,-1,-1,0,1,1,1,1,1,0,0,0,-1,0,-2,-1,-1,0,1,-2,0,2,-1,1,2,-1,0,1,0,1,1,0,-2,0,1,1,1,1,0,0,-1,-1,0,1,0,1,1,-1,1,-1,1,0,0,1,1,2,-2,-2,0,0,-2,0,-1,-1,1,-1,0,1,1,0,-1,1]
g = [0,1,-1,-1,1,2,0,1,1,0,1,1,1,0,0,0,2,0,-1,1,0,1,-1,-1,1,1,0,-1,0,0,-1,-2,1,-1,0,0,2,0,0,-2,-1,0,1,-1,-1,0,2,0,1,0,0,0,0,-1,0,-1,0,2,0,1,2,0,-2,2,1,-1,0,-2,-1,0,0,-2,-1,-1,0,-1,0,1,0,-1,0,-2,0,2,-1,-1,1,1,-1,1,1,1,1,0,2,0,1,-1,0,0,1,-1,-1,0,1,1,-1,-1,1,-1,-1,0,1,1,0,2,-1,0,-1,1,-1,0,1,1,1,-1,0,1,2,0,-2,-1,0,-2,-1,1,1,-1,-1,1,-1,2,2,-1,1,-1,0,0,0,-1,1,1,1,-1,-1,0,0,-2,0,0,-2,1,2,-1,0,-1,-1,-1,-1,1,1,0,-1,0,0,0,-1,-2,-1,1,1,0,-2,1,1,1,-2,1,0,-1,-2,0,1,0,0,1,0,-1,0,0,-1,0,2,1,1,0,-1,1,2,0,-1,1,0,1,0,0,0,1,-1,0,0,-1,0,0,1,0,0,-1,0,0,-2,2,-1,0,-1,1,0,0,0,-1,1,1,0,0,-2,1,0,0,1,-2,-2,-1,-1,-1,1,2]
F2 = [1,0,0,0,0,1,0,0,0,1,1,0,1,1,0,1,0,0,0,0,0,0,1,1,0,1,0,1,0,0,0,1,1,0,0,0,1,1,1,0,0,0,0,1,1,0,1,0,0,1,0,1,1,0,1,0,0,1,1,1,0,0,1,0,0,1,0,1,1,0,1,0,0,1,0,1,1,1,0,1,0,0,1,1,0,1,1,1,1,0,1,1,1,0,1,1,0,1,0,1,0,0,0,0,1,0,1,0,1,1,1,0,1,0,1,1,1,0,0,0,0,0,1,1,1,0,0,0,1,0,1,0,0,0,0,0,1,0,1,1,1,1,1,0,0,1,0,0,0,0,0,0,1,1,0,0,1,0,1,1,1,0,0,1,1,1,0,0,1,0,1,0,0,0,1,1,0,1,1,0,0,0,1,1,1,1,0,0,0,0,1,1,1,0,1,1,1,1,1,1,0,0,0,0,1,1,0,0,1,0,1,0,0,1,0,0,1,1,0,0,1,1,0,1,1,1,0,0,0,0,0,1,0,0,0,1,0,1,0,1,0,0,1,0,1,0,1,0,1,0,1,1,0,1,1,0]
G2 = [0,0,1,0,1,1,1,0,1,1,0,1,1,0,0,1,0,0,1,1,1,1,0,0,0,1,1,0,1,0,0,1,0,1,1,0,1,1,1,0,1,0,0,0,0,1,0,0,1,1,1,1,0,1,1,0,1,0,1,0,0,0,1,1,1,1,0,0,1,0,1,0,1,0,1,0,1,0,1,0,0,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,1,1,0,0,1,1,0,0,0,1,0,0,0,1,1,0,1,1,1,1,0,0,1,1,0,1,1,0,1,0,1,0,1,1,1,1,1,0,0,1,0,0,1,1,0,0,0,1,1,1,0,0,0,0,1,0,1,1,0,0,0,0,0,1,0,0,1,1,0,1,0,1,1,1,0,0,0,0,0,0,0,1,1,1,0,0,1,0,1,0,0,1,0,0,0,1,0,1,0,0,0,1,1,0,1,0,1,1,0,0,1,0,0,0,1,0,0,1,1,1,0,1,1,1,1,0,1,1,0,0,1,1,0,0,0,1,1,0,1,0,1,1,0,0,1,1,0,1,1,1,1,0,0,1,1,0,0,0,1]
hpub = b8582166a45066070c110559615872ab
# hm = SHAKE256(message || hpub) (64 bytes)
hm = f507fed257d3b99d66f2c679ecdc78363bf8d27492b95bc9625fbc590e19012b23ce5da33df3e979fffc82e3f2f0874427a6e632afca1cf7af5cc030aa811596
salt = c8c2ce3a29d329f7f12b61372bbe
# h = SHAKE256(hm || salt) (2*n bits)
h0 = [1,0,1,1,1,1,0,0,0,0,0,1,1,1,1,0,0,1,1,0,1,0,0,0,0,0,1,0,0,0,1,1,0,0,0,1,1,0,1,0,1,0,1,1,0,1,1,1,1,1,0,0,1,1,1,1,0,0,1,0,0,1,0,0,1,1,0,1,0,1,1,0,0,0,0,1,1,1,0,0,1,1,0,1,0,0,1,1,0,1,0,1,0,0,1,1,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,1,0,1,1,0,1,1,0,1,1,0,1,0,1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,1,1,0,0,1,0,0,0,0,1,0,1,0,0,0,0,1,0,1,0,0,0,0,0,0,1,0,1,1,0,1,1,0,1,1,1,0,1,1,1,1,0,0,0,0,1,1,1,1,0,1,1,0,0,0,1,1,1,1,0,0,1,1,0,0,1,1,0,1,0,1,0,1,1,0,1,1,0,0,1,1,1,0,0,1,0,0,0,1,0,0,0,1,0,1,1,0,0,1,1,1,0,1,1,0,0,1,0,0,1,1,1,1,1,0]
h1 = [1,0,1,1,1,1,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,0,1,1,0,1,1,1,1,0,1,0,1,0,0,0,0,0,1,1,1,0,1,0,1,0,0,1,1,0,0,0,0,0,0,1,0,1,1,0,1,1,1,1,0,0,0,0,1,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,1,0,1,1,1,1,0,1,0,1,1,0,1,1,1,1,1,0,0,1,1,1,1,0,1,1,1,0,0,1,0,1,1,0,1,1,1,0,1,1,0,0,0,0,1,0,1,1,0,0,1,1,0,1,1,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,1,0,1,1,1,0,0,0,1,0,0,0,0,0,0,1,1,0,1,1,0,1,0,0,1,1,1,0,0,1,1,0,0,1,1,1,0,0,0,0,1,1,0,0,0,0,0,1,1,0,1,0,0,0,1,1,1,1,0,1,0,0,0,0,1,0,0,1,1,1,1,1,1,0,1,1,1,1,1]
# t = B*h (mod 2)
t0 = [0,0,0,1,0,0,1,0,0,0,1,0,0,1,1,1,1,1,0,0,0,1,0,0,0,1,1,1,1,0,1,1,0,1,1,1,0,1,0,0,0,1,0,1,1,1,0,1,0,0,0,0,1,1,0,0,1,1,0,1,1,0,1,0,1,1,0,1,1,1,1,1,1,1,0,0,0,1,1,0,0,1,0,0,1,1,0,0,0,0,0,0,0,0,0,1,0,0,0,1,1,1,0,1,0,0,1,0,0,1,1,1,0,1,1,1,0,1,0,0,0,0,1,1,1,0,1,0,0,0,1,0,0,0,0,1,1,1,0,0,0,1,1,1,0,0,1,0,1,1,0,0,1,0,1,1,1,1,1,1,0,0,0,0,1,0,1,1,0,0,0,0,1,1,0,0,1,0,1,1,1,1,0,0,1,0,0,1,0,0,1,0,0,1,0,1,1,0,0,0,0,0,1,0,0,0,1,1,0,0,0,1,0,0,1,0,1,0,0,1,0,0,1,1,1,1,0,1,0,0,0,1,1,1,0,0,0,0,1,1,0,1,1,0,0,0,0,1,0,1,0,1,1,1,1,0]
t1 = [1,0,1,0,0,0,0,1,0,1,0,1,1,0,0,0,0,0,0,1,1,0,1,1,0,1,1,0,0,0,1,0,0,1,1,1,0,1,1,1,1,1,1,0,1,0,1,1,1,0,0,0,1,1,0,1,1,0,0,1,1,1,0,1,1,0,0,1,0,1,0,1,1,1,0,0,0,1,1,0,1,1,0,1,0,1,0,0,1,1,0,0,0,1,0,0,1,0,1,1,1,1,0,1,0,0,1,1,0,0,1,0,0,0,0,0,1,0,0,1,0,1,0,0,1,0,1,0,1,1,0,0,0,0,1,1,0,0,0,1,1,1,0,0,0,0,1,0,1,0,1,1,0,1,1,1,1,0,0,0,1,0,0,0,1,1,0,0,1,1,0,0,1,1,1,0,0,0,0,0,0,0,0,0,0,0,1,1,1,0,0,0,1,1,1,1,0,1,1,0,0,1,1,0,0,1,0,1,0,1,1,0,0,1,1,1,1,1,1,0,1,0,1,0,1,1,0,0,0,1,0,1,0,1,1,0,0,1,0,1,0,1,0,1,0,1,1,1,1,1,0,0,0,1,1,1]
# (dx0, dx1) = (2*x0, 2*x1)
dx0 = [0,2,0,-1,0,2,-3,0,0,-2,-3,2,-2,-3,3,-1,-3,1,-2,0,0,-1,2,0,-2,1,-1,-1,-3,0,1,-1,2,-1,1,-1,2,-1,0,0,0,1,-2,-1,1,-1,0,-1,-2,0,2,-2,-1,-1,0,-2,1,1,2,-3,1,0,-1,-2,-3,-1,0,-1,-1,-1,1,1,3,3,-2,2,0,-1,1,-4,0,-1,0,0,1,3,-2,-2,2,-2,2,0,0,2,-6,1,2,0,0,-1,-1,-3,2,-1,-4,-4,3,-2,-2,1,1,-1,-2,-1,3,-1,0,-3,2,0,-2,2,-1,-1,-1,-2,1,4,-2,0,-1,0,0,0,-2,-1,-1,-1,0,-2,2,-3,1,-3,0,4,-1,2,-5,-1,0,0,-3,0,-1,-3,1,1,1,-5,0,-2,0,2,1,0,3,1,2,-2,-2,0,-1,-3,0,0,-1,-2,1,-1,-3,1,0,2,-3,-2,-2,3,2,0,1,0,0,1,0,1,-1,-2,2,0,0,0,-1,0,2,0,3,3,-2,-2,-2,-1,6,0,-3,-2,-1,-4,-4,-1,2,0,-1,-1,-3,1,0,-1,-2,0,0,-1,1,1,0,2,-4,-4,-1,-1,2,1,1,4,2,2,0,-1,2,-1,2,-3,3,-5,-1,4]
dx1 = [1,0,3,0,0,2,0,-1,0,1,-2,-1,-1,2,-2,2,2,0,4,-3,-3,-2,3,1,0,-3,1,0,0,2,1,2,-2,1,-1,1,0,1,1,3,-1,-1,-1,0,-1,-2,-1,-3,-1,2,2,0,3,1,4,1,-1,2,-2,3,-1,-1,-2,3,3,2,0,5,4,1,2,1,3,1,-2,-2,0,-1,-1,0,1,1,4,1,4,5,-2,2,-3,3,0,2,0,-1,0,2,-1,2,-1,1,-1,-1,0,-1,-2,2,-1,-1,-2,0,-1,2,0,0,0,-2,1,0,-2,-1,2,-1,-2,0,3,0,-1,2,-3,1,-2,-2,2,-2,-1,1,4,0,-2,1,1,1,-2,0,2,0,1,-4,-1,2,1,1,0,-1,1,1,-1,-2,-4,-2,3,2,2,0,1,-3,-2,0,3,1,2,0,-1,1,1,2,-2,-2,2,4,0,0,-2,-2,0,0,-1,-1,1,-2,2,2,-1,-3,1,1,0,3,-1,6,0,3,-1,0,0,-1,2,1,0,-1,1,2,-2,-3,-1,-1,-3,1,-1,-4,1,0,-1,0,-1,3,0,2,0,3,0,1,0,1,-1,0,2,5,4,5,-2,-1,0,3,2,-1,1,1,3,3,-2,2,-2,1,1,-3]
l2norm(2*x)^2 = 1879
# w = h1 - 2*s1
w = [-5,24,47,11,-21,-55,-10,-44,-5,52,0,22,42,54,-2,-46,-23,-32,-92,-22,-1,22,-74,42,65,25,42,-21,5,51,9,-39,15,29,27,29,33,50,35,75,-34,-35,100,-31,-93,20,-59,9,-7,-9,80,-47,46,-1,8,-64,46,-16,-14,-17,19,-37,26,55,24,-49,-8,26,-15,43,10,24,20,86,50,-18,35,-38,27,49,-14,-15,41,25,21,-28,36,44,4,1,-22,-14,66,20,-76,-34,-93,-7,-23,61,13,36,58,-40,18,-16,36,-95,-16,-75,29,31,-7,38,45,72,-57,43,36,-51,53,19,-63,-11,-16,26,-21,-53,37,75,-16,31,-105,-85,-26,50,33,-12,27,63,50,25,-49,-11,-30,-39,-55,16,-24,10,42,47,2,3,33,-12,-42,29,1,-22,-11,-115,-44,-4,16,26,-28,36,94,-10,23,-14,-74,-47,-38,-58,-77,-21,-36,69,-9,37,-88,46,-40,17,0,36,-38,-4,58,28,-31,-21,82,83,9,64,-1,-2,-82,-23,-33,-11,-26,22,-67,61,-94,-4,-31,103,-39,30,4,92,-44,-91,107,-52,38,26,-16,40,15,51,-16,-19,52,46,38,23,31,59,-33,36,-27,2,-58,42,-28,19,16,0,91,-35,29,95,17,-53,6,-3,25,-31,-39,-17]
symbreak = -1
s1 = [-2,12,24,6,-10,-27,-5,-22,-2,26,0,11,21,27,-1,-23,-11,-16,-46,-11,0,11,-37,21,33,13,21,-10,3,26,5,-19,8,15,14,15,17,25,18,38,-17,-17,50,-15,-46,10,-29,5,-3,-4,40,-23,23,0,4,-32,23,-8,-7,-8,10,-18,13,28,12,-24,-4,13,-7,22,5,12,10,43,25,-9,18,-19,14,25,-7,-7,21,13,11,-14,18,22,2,1,-11,-7,33,10,-38,-17,-46,-3,-11,31,7,18,29,-20,9,-8,18,-47,-8,-37,15,16,-3,19,23,36,-28,22,18,-25,27,10,-31,-5,-8,13,-10,-26,19,38,-8,16,-52,-42,-13,25,17,-6,14,32,25,13,-24,-5,-15,-19,-27,8,-12,5,21,24,1,2,17,-6,-21,15,1,-11,-5,-57,-22,-2,8,13,-14,18,47,-5,12,-7,-37,-23,-19,-29,-38,-10,-18,35,-4,19,-44,23,-20,9,0,18,-19,-2,29,14,-15,-10,41,42,5,32,0,-1,-41,-11,-16,-5,-13,11,-33,31,-47,-2,-15,52,-19,15,2,46,-22,-45,54,-26,19,13,-8,20,8,26,-8,-9,26,23,19,12,16,30,-16,18,-13,1,-29,21,-14,10,8,0,46,-17,15,48,9,-26,3,-1,13,-15,-19,-8]
sig = c8c2ce3a29d329f7f12b61372bbef1c14f88005b8b2e162823cc873a91dc74c217984ffa5731835f174b0c5421ea81619334a941835537b0ea350516a9a1d5347491e8b917b334104ad7142f62207b01f9f798a362e3ec8e666c616a6524a5cbc6d4b69ab422281354814da87f649fe94877c883625eb2adc45b79725acad31c3813cbb13890db254e6ab44ac541c4425f5004d7805a938f3043ace425c531e6ba33012943772e25550000483dc216f82e382a9f7095d93cdba1481fa4ef64d03fc902af4d21e0e083290fd09c3cffff7bfbffbbfdfefffffeff6ffbbffdfe7fd7effffff7f7deddff6bf7dbbdf5ffffbffb0f000000000000
#### Verify (n=256):
salt = c8c2ce3a29d329f7f12b61372bbe
s1 = [-2,12,24,6,-10,-27,-5,-22,-2,26,0,11,21,27,-1,-23,-11,-16,-46,-11,0,11,-37,21,33,13,21,-10,3,26,5,-19,8,15,14,15,17,25,18,38,-17,-17,50,-15,-46,10,-29,5,-3,-4,40,-23,23,0,4,-32,23,-8,-7,-8,10,-18,13,28,12,-24,-4,13,-7,22,5,12,10,43,25,-9,18,-19,14,25,-7,-7,21,13,11,-14,18,22,2,1,-11,-7,33,10,-38,-17,-46,-3,-11,31,7,18,29,-20,9,-8,18,-47,-8,-37,15,16,-3,19,23,36,-28,22,18,-25,27,10,-31,-5,-8,13,-10,-26,19,38,-8,16,-52,-42,-13,25,17,-6,14,32,25,13,-24,-5,-15,-19,-27,8,-12,5,21,24,1,2,17,-6,-21,15,1,-11,-5,-57,-22,-2,8,13,-14,18,47,-5,12,-7,-37,-23,-19,-29,-38,-10,-18,35,-4,19,-44,23,-20,9,0,18,-19,-2,29,14,-15,-10,41,42,5,32,0,-1,-41,-11,-16,-5,-13,11,-33,31,-47,-2,-15,52,-19,15,2,46,-22,-45,54,-26,19,13,-8,20,8,26,-8,-9,26,23,19,12,16,30,-16,18,-13,1,-29,21,-14,10,8,0,46,-17,15,48,9,-26,3,-1,13,-15,-19,-8]
# hm = SHAKE256(message || hpub) (64 bytes)
hm = f507fed257d3b99d66f2c679ecdc78363bf8d27492b95bc9625fbc590e19012b23ce5da33df3e979fffc82e3f2f0874427a6e632afca1cf7af5cc030aa811596
# h = SHAKE256(hm || salt) (2*n bits)
h0 = [1,0,1,1,1,1,0,0,0,0,0,1,1,1,1,0,0,1,1,0,1,0,0,0,0,0,1,0,0,0,1,1,0,0,0,1,1,0,1,0,1,0,1,1,0,1,1,1,1,1,0,0,1,1,1,1,0,0,1,0,0,1,0,0,1,1,0,1,0,1,1,0,0,0,0,1,1,1,0,0,1,1,0,1,0,0,1,1,0,1,0,1,0,0,1,1,0,0,1,0,0,0,1,0,0,0,1,0,1,0,0,0,1,1,0,1,1,0,1,1,0,1,1,0,1,0,1,0,0,0,0,0,0,1,1,1,0,0,0,0,0,1,1,0,0,1,0,0,0,0,1,0,1,0,0,0,0,1,0,1,0,0,0,0,0,0,1,0,1,1,0,1,1,0,1,1,1,0,1,1,1,1,0,0,0,0,1,1,1,1,0,1,1,0,0,0,1,1,1,1,0,0,1,1,0,0,1,1,0,1,0,1,0,1,1,0,1,1,0,0,1,1,1,0,0,1,0,0,0,1,0,0,0,1,0,1,1,0,0,1,1,1,0,1,1,0,0,1,0,0,1,1,1,1,1,0]
h1 = [1,0,1,1,1,1,0,0,1,0,0,0,0,0,0,0,1,0,0,0,1,0,0,0,1,1,0,1,1,1,1,1,1,1,1,1,1,0,1,1,0,1,0,1,1,0,1,1,1,1,0,1,0,1,0,0,0,0,0,1,1,1,0,1,0,1,0,0,1,1,0,0,0,0,0,0,1,0,1,1,0,1,1,1,1,0,0,0,0,1,0,0,0,0,0,0,1,1,1,1,1,0,0,0,0,0,0,1,0,1,1,1,1,0,1,0,1,1,0,1,1,1,1,1,0,0,1,1,1,1,0,1,1,1,0,0,1,0,1,1,0,1,1,1,0,1,1,0,0,0,0,1,0,1,1,0,0,1,1,0,1,1,0,0,0,0,0,0,0,0,1,0,0,1,0,0,1,1,0,1,1,1,0,0,0,1,0,0,0,0,0,0,1,1,0,1,1,0,1,0,0,1,1,1,0,0,1,1,0,0,1,1,1,0,0,0,0,1,1,0,0,0,0,0,1,1,0,1,0,0,0,1,1,1,1,0,1,0,0,0,0,1,0,0,1,1,1,1,1,1,0,1,1,1,1,1]
# ft1 = FFT(h1 - 2*s1)
ft1 = [-582088,-3740926,-1569516,1602197,-740009,675667,-2146305,-1359740,2250893,-3029472,-1030460,1113808,441229,1039919,2059692,-2799458,333963,3207394,-1278022,141801,451476,691408,-562710,1827168,-1499328,-1232540,1778103,501609,2860442,-2061281,2171473,154481,872543,-2664121,57523,-46145,-534347,-4313918,1798367,-3905548,-3577303,1505484,1524443,-488938,-295863,2565786,497348,1577929,849144,-85851,-3193503,-1597463,307964,350334,826187,216444,808857,960801,1252060,-1256421,-1268329,-345047,315911,-1269549,-40150,3116331,3172578,5070,1971931,1209602,695977,1869433,-3461300,1513406,1772999,-1783628,4274873,-1977646,932507,-2079434,-1157839,-2063644,2667425,-2283328,1351154,-2256489,1851839,-574955,2366773,2164300,733473,-203897,1189568,337103,848193,-479623,-3626358,39016,1876819,3919810,-111729,331615,-481249,-2344373,-1949766,1025765,1034418,-2836608,2714518,-188740,-4915749,-2302595,-1035343,-2267883,-1728609,-600508,3488187,1253890,-1517221,2903961,1452580,-6881599,962357,358522,1139315,-128691,3226355,3012957,-1190391,2779743,-1638294,4042034,-553270,-380681,-1739540,1480039,5384859,1704749,-9434,1437838,2668235,-2216746,2216125,1125203,-1793753,-738337,2120576,747016,1031140,1263774,-1374466,609583,-1357083,-1431874,-2543185,1284953,-1821590,-3947241,-557434,285610,-1454836,1747179,-4202958,-479501,-2102479,1035177,-767967,-1263456,-1828681,-3121939,2966535,-928008,3862979,1024318,-2173688,657062,-594454,-373019,2091920,-270860,-1545655,-1152575,268226,-8760877,272314,-1178051,-1655890,-1673426,3406709,1619921,927356,358621,-1842376,900049,-1945196,-253302,-1966589,1112051,-1981895,-556786,-616704,4415773,572997,-326185,-1125563,-4158170,-307279,473608,483026,-3696171,-1475687,1893982,-1762072,-458368,3123437,158548,-4135331,-158748,-850293,124671,-90512,189287,1207625,-1295683,3972033,447267,-2322114,-421843,660053,562358,-406401,435190,-1919109,-2015871,1187377,132801,2912202,-2334650,5022597,3259724,2334632,708717,-2230606,-489789,1797594,2565329,-428387,-2393556,-2183287,-2271332,-1445206,-1073766,-1235352,-661632,-1739231,2925176]
# first half of q00 only
q00 = [556,8,-33,-1,22,-50,-25,-10,-23,-1,4,-8,-13,25,35,-23,25,0,-9,-18,0,-33,-28,33,17,-43,-13,-20,27,40,4,28,7,-8,21,-43,-8,23,-30,-24,0,-3,3,5,6,2,-31,22,13,-1,48,-20,-6,-9,-24,-25,13,3,26,-59,-17,-8,0,26,10,-19,6,15,-26,-54,-32,-16,4,-16,-28,9,44,-42,-4,52,8,14,-4,-13,-6,-14,27,38,-43,4,18,-12,36,34,10,-6,-14,-30,-2,-5,19,-7,-22,15,58,0,-23,25,-16,-36,27,4,25,-7,-3,-28,62,-18,-3,-9,14,0,-15,15,14,-18,8,17]
# fq00 = FFT(q00') (q00' = q00 except that q00'[0] = 0)
fq00 = [-3167040,4068299,6534251,-546020,3292849,-4080325,-405038,1739432,7897826,-1410396,1262626,-3474552,-1241127,-396676,1544595,2230666,39022,1002266,-2055346,-1313288,-3793937,-2753314,-4025451,-681400,2938201,-1519659,6604258,-3104352,1022471,3671003,-2341083,-3249773,-2905217,3914694,4890041,-1613510,2544406,5034154,-2466538,2194983,1618794,942691,-2344742,-1032084,-1074948,248843,-1636142,-1453949,-1147400,-2590455,9104172,-3383983,3329285,1132473,-948780,4833371,-3492947,-2963630,-2069270,4744491,-2790411,-1284594,-2572824,-3635473,1711258,1107282,483935,4536460,-156831,-3181757,-719810,-3043338,-1583435,-530242,-3091780,-1481147,-428743,4982266,4552389,-2946193,-1415933,275787,6915198,5124270,-2475745,-1653236,-821275,-3125127,-565401,-1666385,451199,-4390659,-2354031,-3910521,-3462934,971412,426374,-1287648,-384589,5020461,-2284565,-4240782,-3263164,117959,2109736,-785663,-2983431,6171995,5622531,-2639014,26919,1525671,-2033222,-925387,-165221,-1709921,953745,3973563,877232,3229208,-269217,8391139,-3916201,-2380069,1253982,-2290042,-1990903,-1673025,-4,0,-1,0,-2,0,-1,-1,-3,0,-1,0,-2,0,-1,-1,-2,-1,-1,-1,-2,0,0,-1,-2,-1,-1,0,-2,0,0,-1,-3,-1,-1,0,-2,0,-1,0,-2,0,-1,-1,-2,0,-1,-1,-3,0,-1,-1,-1,0,-1,-1,-1,-1,-1,-1,0,-1,-1,-1,-3,-1,-1,0,-2,-1,-1,0,-2,-1,-1,0,-1,-1,-1,0,-3,0,-2,0,-2,0,-1,0,-2,0,-1,-1,-1,0,-1,-1,-3,0,-1,-1,-2,0,-1,0,-2,0,-1,-1,-1,-1,-1,-1,-2,-1,-1,-1,-1,0,-1,-1,-1,-1,-1,-1,-1,0,-1,-2]
q01 = [0,234,19,38,-97,200,-85,-152,138,90,45,151,-79,-235,6,215,-11,-64,235,220,-327,-222,5,-257,164,79,13,-48,223,160,-34,-102,277,-14,-356,168,-11,-50,56,209,-244,27,409,-208,-19,140,-3,-470,203,297,51,-128,-135,4,73,176,-48,-213,283,186,-210,-114,110,112,-9,-21,153,-113,-151,-209,-304,19,234,132,-263,-8,209,-15,-26,31,-98,-175,-12,-135,-77,297,122,282,-178,49,-222,129,-189,-6,-35,172,-299,170,-48,68,61,62,-28,135,-30,-112,207,138,109,-140,-232,-87,172,152,3,136,210,-175,-23,-363,-127,61,-78,-149,-19,152,-45,-236,250,261,-115,-2,-175,-187,-8,160,273,199,55,-160,17,21,238,-211,-58,-117,77,-50,-270,249,-14,-225,-111,142,143,106,-201,-157,29,-60,-256,-315,-89,-13,238,328,178,-193,-96,19,87,-156,-382,154,-177,-262,25,284,361,-33,137,-282,-180,44,8,-208,217,497,-4,13,-80,152,187,-54,-280,-215,169,219,-110,35,-48,206,-55,191,-169,-92,-245,101,-227,-81,-32,92,-72,-72,229,81,-27,-14,131,209,50,167,-83,-183,-325,-84,190,-95,77,179,-40,48,232,-209,11,-111,-10,-111,-148,-190,138,248,217,-304,201,378,-233,-300,-120,91,-131,-60,-67,154,207,-233]
# fq01 = FFT(q01)
fq01 = [2114168,-695272,-3222464,2401274,997541,-442223,488001,9473726,1757251,-2198819,778846,-584069,-1553838,7241144,-141493,2888454,-1145645,-3229550,309225,-4178547,620689,1371104,-785511,-369668,10680754,-1717766,-2961247,-770794,7738804,2090669,-1449956,783450,303603,5598949,-3803464,-807320,-5022550,-123910,636876,3044697,4747889,-6431692,651525,2776763,449273,-2017646,-2352486,-353816,-659119,921214,-12583854,-1787177,-6453387,-3244326,-186512,-10359276,1042324,2686702,-1775732,2663755,-2212428,-5394892,-2779561,-1628376,2801523,-8199989,-958788,8421781,-3380195,-630992,-5412126,2349459,-17177,28092,-527879,3834826,323313,-4221244,-8856437,-915331,-1366917,-209130,-3051911,8202457,-2665643,-339561,1851316,-1223205,5673724,713639,-2027222,-41041,-3198555,670754,-1310670,5064503,-2150514,-437292,500747,13646370,-670371,-231435,-2472708,-4916902,-8086038,732818,354782,5203975,7798950,1210590,3878619,6073094,-2288948,-1408282,4611442,-894742,3784930,68422,-3416132,780289,2189180,6960392,-277575,-822786,-4133989,-270320,638737,828912,-764033,-2342261,-5554164,1598152,497769,-412450,4226869,-671602,-6318427,-4283902,-2388790,676598,4160813,2334402,6185134,18219,1301535,-4671865,343155,1494085,452881,-2320619,-168488,-4888005,1120435,2142772,-760894,560116,3123509,-1232040,-2819300,-814555,191000,4674331,6751572,6055983,11760692,4915865,-1006741,-650440,11935519,2998107,-413593,-5417667,-290595,-10329462,-657307,1880607,-711406,-487692,-1161956,1187668,252371,12811861,1465045,1305904,634994,-34736,-1214581,7417350,-590886,3925329,1084544,1158586,975449,5239597,-6104564,8499969,1927241,1475832,3158978,-726487,840291,1365763,971407,-2423338,-995667,7678543,-5097763,517052,-68673,-4042771,16142307,-11920497,-952207,934765,2575579,-1924013,-1522798,2643423,-4562845,6611,2770832,226972,1244722,294441,-1555204,-5228369,916388,-7927090,-1319411,-23448,-1210898,4118027,2405351,-638849,-1045815,6880605,-1888266,2127561,3109091,-2190432,1202281,627129,-764877,1515946,-6407439,2112688,-607587,3399117,3597875,-2542441,382815,-2871037,-231743,1835828,904519,-1559908]
# fz = (q01*t1)/q00
fz = [140473,350177,-471967,29773,-142257,-191515,-348230,36769,133081,297059,360572,-82986,15243,-70729,332769,-3959,-102338,-357469,183395,-210968,121701,77726,5930,198656,-14162,63385,-25726,163712,-57492,-233267,-207775,-342908,127034,-45217,79771,97180,150534,131058,66586,-167958,-87191,-368823,62399,-361456,24743,222166,279378,-87097,60295,212108,77920,-139275,-160709,-287805,-283457,88910,-186372,-157679,-113728,192438,28426,-62527,141546,-6279,-37741,-175046,-73859,-7032,-94324,-187192,25812,301161,55316,36739,-284705,9065,555895,3011,-155879,-120935,217941,-60535,-147676,-58413,-90122,65426,-128135,52122,-75861,-68680,49125,-146367,-180299,120912,70609,17105,-266384,-98395,-84818,288870,55277,-49125,-281680,300939,280570,-112717,-70347,-278585,-244853,94219,-108518,-106566,-5158,126101,30606,-160955,48037,-157733,-297910,52221,1842,-52207,64318,94216,-78596,-34844,298182,-173992,-71842,-196683,-98358,-116776,-67507,310282,-214224,171045,-233601,-204725,-47134,-270239,38981,-124035,178925,67187,108689,-142132,77708,-309359,-69840,-16588,27666,-28764,386174,104389,251646,-22685,374555,-33788,-47112,-11104,270305,167844,-139171,-176275,24591,135295,-273355,-75553,9188,76887,-65539,107519,429056,-100427,131933,-33848,33776,-155669,-175127,-412787,103238,271357,-26602,307086,2139,118428,-240595,31816,-7169,-343107,75493,344869,-158768,225346,32917,174021,-117700,-126208,44075,-43962,-112533,-42851,29630,39731,200844,-286727,29780,62445,116793,377959,190234,269306,-382985,-130100,-39792,-260074,-367811,205829,108352,327756,889,105612,-216025,-135172,176194,72540,-288576,-116712,-14319,-228327,34851,223126,294896,111668,180097,70574,50354,173993,-98288,-121881,-27775,138210,-182201,-152599,11080,419608,-155481,-39898,311243,8108,27644,-222415,-85242,-457820,13368,-225335]
# t0 = h0 - 2*s0
t0 = [-137,-342,461,-29,139,187,340,-36,-130,-290,-352,81,-15,69,-325,4,100,349,-179,206,-119,-76,-6,-194,14,-62,25,-160,56,228,203,335,-124,44,-78,-95,-147,-128,-65,164,85,360,-61,353,-24,-217,-273,85,-59,-207,-76,136,157,281,277,-87,182,154,111,-188,-28,61,-138,6,37,171,72,7,92,183,-25,-294,-54,-36,278,-9,-543,-3,152,118,-213,59,144,57,88,-64,125,-51,74,67,-48,143,176,-118,-69,-17,260,96,83,-282,-54,48,275,-294,-274,110,69,272,239,-92,106,104,5,-123,-30,157,-47,154,291,-51,-2,51,-63,-92,77,34,-291,170,70,192,96,114,66,-303,209,-167,228,200,46,264,-38,121,-175,-66,-106,139,-76,302,68,16,-27,28,-377,-102,-246,22,-366,33,46,11,-264,-164,136,172,-24,-132,267,74,-9,-75,64,-105,-419,98,-129,33,-33,152,171,403,-101,-265,26,-300,-2,-116,235,-31,7,335,-74,-337,155,-220,-32,-170,115,123,-43,43,110,42,-29,-39,-196,280,-29,-61,-114,-369,-186,-263,374,127,39,254,359,-201,-106,-320,-1,-103,211,132,-172,-71,282,114,14,223,-34,-218,-288,-109,-176,-69,-49,-170,96,119,27,-135,178,149,-11,-410,152,39,-304,-8,-27,217,83,447,-13,220]
# Qnorm(t)^2 mod 2147473409
qnt = 240512
# Qnorm(t)^2 mod 2147389441
qnt = 240512
