falcon-rs 0.2.4

//! Falcon key pair generation.
//! Ported from keygen.c.

#![allow(clippy::too_many_arguments)]

use alloc::{vec, vec::Vec};

use crate::{codec, fft, fpr::*, shake::InnerShake256Context, vrfy::compute_public};

const DEPTH_INT_FG: u32 = 4;

pub struct SmallPrime {
    pub p: u32,
    pub g: u32,
    pub s: u32,
}

pub static PRIMES: [SmallPrime; 521] = [
    SmallPrime {
        p: 2147473409,
        g: 383167813,
        s: 10239,
    },
    SmallPrime {
        p: 2147389441,
        g: 211808905,
        s: 471403745,
    },
    SmallPrime {
        p: 2147387393,
        g: 37672282,
        s: 1329335065,
    },
    SmallPrime {
        p: 2147377153,
        g: 1977035326,
        s: 968223422,
    },
    SmallPrime {
        p: 2147358721,
        g: 1067163706,
        s: 132460015,
    },
    SmallPrime {
        p: 2147352577,
        g: 1606082042,
        s: 598693809,
    },
    SmallPrime {
        p: 2147346433,
        g: 2033915641,
        s: 1056257184,
    },
    SmallPrime {
        p: 2147338241,
        g: 1653770625,
        s: 421286710,
    },
    SmallPrime {
        p: 2147309569,
        g: 631200819,
        s: 1111201074,
    },
    SmallPrime {
        p: 2147297281,
        g: 2038364663,
        s: 1042003613,
    },
    SmallPrime {
        p: 2147295233,
        g: 1962540515,
        s: 19440033,
    },
    SmallPrime {
        p: 2147239937,
        g: 2100082663,
        s: 353296760,
    },
    SmallPrime {
        p: 2147235841,
        g: 1991153006,
        s: 1703918027,
    },
    SmallPrime {
        p: 2147217409,
        g: 516405114,
        s: 1258919613,
    },
    SmallPrime {
        p: 2147205121,
        g: 409347988,
        s: 1089726929,
    },
    SmallPrime {
        p: 2147196929,
        g: 927788991,
        s: 1946238668,
    },
    SmallPrime {
        p: 2147178497,
        g: 1136922411,
        s: 1347028164,
    },
    SmallPrime {
        p: 2147100673,
        g: 868626236,
        s: 701164723,
    },
    SmallPrime {
        p: 2147082241,
        g: 1897279176,
        s: 617820870,
    },
    SmallPrime {
        p: 2147074049,
        g: 1888819123,
        s: 158382189,
    },
    SmallPrime {
        p: 2147051521,
        g: 25006327,
        s: 522758543,
    },
    SmallPrime {
        p: 2147043329,
        g: 327546255,
        s: 37227845,
    },
    SmallPrime {
        p: 2147039233,
        g: 766324424,
        s: 1133356428,
    },
    SmallPrime {
        p: 2146988033,
        g: 1862817362,
        s: 73861329,
    },
    SmallPrime {
        p: 2146963457,
        g: 404622040,
        s: 653019435,
    },
    SmallPrime {
        p: 2146959361,
        g: 1936581214,
        s: 995143093,
    },
    SmallPrime {
        p: 2146938881,
        g: 1559770096,
        s: 634921513,
    },
    SmallPrime {
        p: 2146908161,
        g: 422623708,
        s: 1985060172,
    },
    SmallPrime {
        p: 2146885633,
        g: 1751189170,
        s: 298238186,
    },
    SmallPrime {
        p: 2146871297,
        g: 578919515,
        s: 291810829,
    },
    SmallPrime {
        p: 2146846721,
        g: 1114060353,
        s: 915902322,
    },
    SmallPrime {
        p: 2146834433,
        g: 2069565474,
        s: 47859524,
    },
    SmallPrime {
        p: 2146818049,
        g: 1552824584,
        s: 646281055,
    },
    SmallPrime {
        p: 2146775041,
        g: 1906267847,
        s: 1597832891,
    },
    SmallPrime {
        p: 2146756609,
        g: 1847414714,
        s: 1228090888,
    },
    SmallPrime {
        p: 2146744321,
        g: 1818792070,
        s: 1176377637,
    },
    SmallPrime {
        p: 2146738177,
        g: 1118066398,
        s: 1054971214,
    },
    SmallPrime {
        p: 2146736129,
        g: 52057278,
        s: 933422153,
    },
    SmallPrime {
        p: 2146713601,
        g: 592259376,
        s: 1406621510,
    },
    SmallPrime {
        p: 2146695169,
        g: 263161877,
        s: 1514178701,
    },
    SmallPrime {
        p: 2146656257,
        g: 685363115,
        s: 384505091,
    },
    SmallPrime {
        p: 2146650113,
        g: 927727032,
        s: 537575289,
    },
    SmallPrime {
        p: 2146646017,
        g: 52575506,
        s: 1799464037,
    },
    SmallPrime {
        p: 2146643969,
        g: 1276803876,
        s: 1348954416,
    },
    SmallPrime {
        p: 2146603009,
        g: 814028633,
        s: 1521547704,
    },
    SmallPrime {
        p: 2146572289,
        g: 1846678872,
        s: 1310832121,
    },
    SmallPrime {
        p: 2146547713,
        g: 919368090,
        s: 1019041349,
    },
    SmallPrime {
        p: 2146508801,
        g: 671847612,
        s: 38582496,
    },
    SmallPrime {
        p: 2146492417,
        g: 283911680,
        s: 532424562,
    },
    SmallPrime {
        p: 2146490369,
        g: 1780044827,
        s: 896447978,
    },
    SmallPrime {
        p: 2146459649,
        g: 327980850,
        s: 1327906900,
    },
    SmallPrime {
        p: 2146447361,
        g: 1310561493,
        s: 958645253,
    },
    SmallPrime {
        p: 2146441217,
        g: 412148926,
        s: 287271128,
    },
    SmallPrime {
        p: 2146437121,
        g: 293186449,
        s: 2009822534,
    },
    SmallPrime {
        p: 2146430977,
        g: 179034356,
        s: 1359155584,
    },
    SmallPrime {
        p: 2146418689,
        g: 1517345488,
        s: 1790248672,
    },
    SmallPrime {
        p: 2146406401,
        g: 1615820390,
        s: 1584833571,
    },
    SmallPrime {
        p: 2146404353,
        g: 826651445,
        s: 607120498,
    },
    SmallPrime {
        p: 2146379777,
        g: 3816988,
        s: 1897049071,
    },
    SmallPrime {
        p: 2146363393,
        g: 1221409784,
        s: 1986921567,
    },
    SmallPrime {
        p: 2146355201,
        g: 1388081168,
        s: 849968120,
    },
    SmallPrime {
        p: 2146336769,
        g: 1803473237,
        s: 1655544036,
    },
    SmallPrime {
        p: 2146312193,
        g: 1023484977,
        s: 273671831,
    },
    SmallPrime {
        p: 2146293761,
        g: 1074591448,
        s: 467406983,
    },
    SmallPrime {
        p: 2146283521,
        g: 831604668,
        s: 1523950494,
    },
    SmallPrime {
        p: 2146203649,
        g: 712865423,
        s: 1170834574,
    },
    SmallPrime {
        p: 2146154497,
        g: 1764991362,
        s: 1064856763,
    },
    SmallPrime {
        p: 2146142209,
        g: 627386213,
        s: 1406840151,
    },
    SmallPrime {
        p: 2146127873,
        g: 1638674429,
        s: 2088393537,
    },
    SmallPrime {
        p: 2146099201,
        g: 1516001018,
        s: 690673370,
    },
    SmallPrime {
        p: 2146093057,
        g: 1294931393,
        s: 315136610,
    },
    SmallPrime {
        p: 2146091009,
        g: 1942399533,
        s: 973539425,
    },
    SmallPrime {
        p: 2146078721,
        g: 1843461814,
        s: 2132275436,
    },
    SmallPrime {
        p: 2146060289,
        g: 1098740778,
        s: 360423481,
    },
    SmallPrime {
        p: 2146048001,
        g: 1617213232,
        s: 1951981294,
    },
    SmallPrime {
        p: 2146041857,
        g: 1805783169,
        s: 2075683489,
    },
    SmallPrime {
        p: 2146019329,
        g: 272027909,
        s: 1753219918,
    },
    SmallPrime {
        p: 2145986561,
        g: 1206530344,
        s: 2034028118,
    },
    SmallPrime {
        p: 2145976321,
        g: 1243769360,
        s: 1173377644,
    },
    SmallPrime {
        p: 2145964033,
        g: 887200839,
        s: 1281344586,
    },
    SmallPrime {
        p: 2145906689,
        g: 1651026455,
        s: 906178216,
    },
    SmallPrime {
        p: 2145875969,
        g: 1673238256,
        s: 1043521212,
    },
    SmallPrime {
        p: 2145871873,
        g: 1226591210,
        s: 1399796492,
    },
    SmallPrime {
        p: 2145841153,
        g: 1465353397,
        s: 1324527802,
    },
    SmallPrime {
        p: 2145832961,
        g: 1150638905,
        s: 554084759,
    },
    SmallPrime {
        p: 2145816577,
        g: 221601706,
        s: 427340863,
    },
    SmallPrime {
        p: 2145785857,
        g: 608896761,
        s: 316590738,
    },
    SmallPrime {
        p: 2145755137,
        g: 1712054942,
        s: 1684294304,
    },
    SmallPrime {
        p: 2145742849,
        g: 1302302867,
        s: 724873116,
    },
    SmallPrime {
        p: 2145728513,
        g: 516717693,
        s: 431671476,
    },
    SmallPrime {
        p: 2145699841,
        g: 524575579,
        s: 1619722537,
    },
    SmallPrime {
        p: 2145691649,
        g: 1925625239,
        s: 982974435,
    },
    SmallPrime {
        p: 2145687553,
        g: 463795662,
        s: 1293154300,
    },
    SmallPrime {
        p: 2145673217,
        g: 771716636,
        s: 881778029,
    },
    SmallPrime {
        p: 2145630209,
        g: 1509556977,
        s: 837364988,
    },
    SmallPrime {
        p: 2145595393,
        g: 229091856,
        s: 851648427,
    },
    SmallPrime {
        p: 2145587201,
        g: 1796903241,
        s: 635342424,
    },
    SmallPrime {
        p: 2145525761,
        g: 715310882,
        s: 1677228081,
    },
    SmallPrime {
        p: 2145495041,
        g: 1040930522,
        s: 200685896,
    },
    SmallPrime {
        p: 2145466369,
        g: 949804237,
        s: 1809146322,
    },
    SmallPrime {
        p: 2145445889,
        g: 1673903706,
        s: 95316881,
    },
    SmallPrime {
        p: 2145390593,
        g: 806941852,
        s: 1428671135,
    },
    SmallPrime {
        p: 2145372161,
        g: 1402525292,
        s: 159350694,
    },
    SmallPrime {
        p: 2145361921,
        g: 2124760298,
        s: 1589134749,
    },
    SmallPrime {
        p: 2145359873,
        g: 1217503067,
        s: 1561543010,
    },
    SmallPrime {
        p: 2145355777,
        g: 338341402,
        s: 83865711,
    },
    SmallPrime {
        p: 2145343489,
        g: 1381532164,
        s: 641430002,
    },
    SmallPrime {
        p: 2145325057,
        g: 1883895478,
        s: 1528469895,
    },
    SmallPrime {
        p: 2145318913,
        g: 1335370424,
        s: 65809740,
    },
    SmallPrime {
        p: 2145312769,
        g: 2000008042,
        s: 1919775760,
    },
    SmallPrime {
        p: 2145300481,
        g: 961450962,
        s: 1229540578,
    },
    SmallPrime {
        p: 2145282049,
        g: 910466767,
        s: 1964062701,
    },
    SmallPrime {
        p: 2145232897,
        g: 816527501,
        s: 450152063,
    },
    SmallPrime {
        p: 2145218561,
        g: 1435128058,
        s: 1794509700,
    },
    SmallPrime {
        p: 2145187841,
        g: 33505311,
        s: 1272467582,
    },
    SmallPrime {
        p: 2145181697,
        g: 269767433,
        s: 1380363849,
    },
    SmallPrime {
        p: 2145175553,
        g: 56386299,
        s: 1316870546,
    },
    SmallPrime {
        p: 2145079297,
        g: 2106880293,
        s: 1391797340,
    },
    SmallPrime {
        p: 2145021953,
        g: 1347906152,
        s: 720510798,
    },
    SmallPrime {
        p: 2145015809,
        g: 206769262,
        s: 1651459955,
    },
    SmallPrime {
        p: 2145003521,
        g: 1885513236,
        s: 1393381284,
    },
    SmallPrime {
        p: 2144960513,
        g: 1810381315,
        s: 31937275,
    },
    SmallPrime {
        p: 2144944129,
        g: 1306487838,
        s: 2019419520,
    },
    SmallPrime {
        p: 2144935937,
        g: 37304730,
        s: 1841489054,
    },
    SmallPrime {
        p: 2144894977,
        g: 1601434616,
        s: 157985831,
    },
    SmallPrime {
        p: 2144888833,
        g: 98749330,
        s: 2128592228,
    },
    SmallPrime {
        p: 2144880641,
        g: 1772327002,
        s: 2076128344,
    },
    SmallPrime {
        p: 2144864257,
        g: 1404514762,
        s: 2029969964,
    },
    SmallPrime {
        p: 2144827393,
        g: 801236594,
        s: 406627220,
    },
    SmallPrime {
        p: 2144806913,
        g: 349217443,
        s: 1501080290,
    },
    SmallPrime {
        p: 2144796673,
        g: 1542656776,
        s: 2084736519,
    },
    SmallPrime {
        p: 2144778241,
        g: 1210734884,
        s: 1746416203,
    },
    SmallPrime {
        p: 2144759809,
        g: 1146598851,
        s: 716464489,
    },
    SmallPrime {
        p: 2144757761,
        g: 286328400,
        s: 1823728177,
    },
    SmallPrime {
        p: 2144729089,
        g: 1347555695,
        s: 1836644881,
    },
    SmallPrime {
        p: 2144727041,
        g: 1795703790,
        s: 520296412,
    },
    SmallPrime {
        p: 2144696321,
        g: 1302475157,
        s: 852964281,
    },
    SmallPrime {
        p: 2144667649,
        g: 1075877614,
        s: 504992927,
    },
    SmallPrime {
        p: 2144573441,
        g: 198765808,
        s: 1617144982,
    },
    SmallPrime {
        p: 2144555009,
        g: 321528767,
        s: 155821259,
    },
    SmallPrime {
        p: 2144550913,
        g: 814139516,
        s: 1819937644,
    },
    SmallPrime {
        p: 2144536577,
        g: 571143206,
        s: 962942255,
    },
    SmallPrime {
        p: 2144524289,
        g: 1746733766,
        s: 2471321,
    },
    SmallPrime {
        p: 2144512001,
        g: 1821415077,
        s: 124190939,
    },
    SmallPrime {
        p: 2144468993,
        g: 917871546,
        s: 1260072806,
    },
    SmallPrime {
        p: 2144458753,
        g: 378417981,
        s: 1569240563,
    },
    SmallPrime {
        p: 2144421889,
        g: 175229668,
        s: 1825620763,
    },
    SmallPrime {
        p: 2144409601,
        g: 1699216963,
        s: 351648117,
    },
    SmallPrime {
        p: 2144370689,
        g: 1071885991,
        s: 958186029,
    },
    SmallPrime {
        p: 2144348161,
        g: 1763151227,
        s: 540353574,
    },
    SmallPrime {
        p: 2144335873,
        g: 1060214804,
        s: 919598847,
    },
    SmallPrime {
        p: 2144329729,
        g: 663515846,
        s: 1448552668,
    },
    SmallPrime {
        p: 2144327681,
        g: 1057776305,
        s: 590222840,
    },
    SmallPrime {
        p: 2144309249,
        g: 1705149168,
        s: 1459294624,
    },
    SmallPrime {
        p: 2144296961,
        g: 325823721,
        s: 1649016934,
    },
    SmallPrime {
        p: 2144290817,
        g: 738775789,
        s: 447427206,
    },
    SmallPrime {
        p: 2144243713,
        g: 962347618,
        s: 893050215,
    },
    SmallPrime {
        p: 2144237569,
        g: 1655257077,
        s: 900860862,
    },
    SmallPrime {
        p: 2144161793,
        g: 242206694,
        s: 1567868672,
    },
    SmallPrime {
        p: 2144155649,
        g: 769415308,
        s: 1247993134,
    },
    SmallPrime {
        p: 2144137217,
        g: 320492023,
        s: 515841070,
    },
    SmallPrime {
        p: 2144120833,
        g: 1639388522,
        s: 770877302,
    },
    SmallPrime {
        p: 2144071681,
        g: 1761785233,
        s: 964296120,
    },
    SmallPrime {
        p: 2144065537,
        g: 419817825,
        s: 204564472,
    },
    SmallPrime {
        p: 2144028673,
        g: 666050597,
        s: 2091019760,
    },
    SmallPrime {
        p: 2144010241,
        g: 1413657615,
        s: 1518702610,
    },
    SmallPrime {
        p: 2143952897,
        g: 1238327946,
        s: 475672271,
    },
    SmallPrime {
        p: 2143940609,
        g: 307063413,
        s: 1176750846,
    },
    SmallPrime {
        p: 2143918081,
        g: 2062905559,
        s: 786785803,
    },
    SmallPrime {
        p: 2143899649,
        g: 1338112849,
        s: 1562292083,
    },
    SmallPrime {
        p: 2143891457,
        g: 68149545,
        s: 87166451,
    },
    SmallPrime {
        p: 2143885313,
        g: 921750778,
        s: 394460854,
    },
    SmallPrime {
        p: 2143854593,
        g: 719766593,
        s: 133877196,
    },
    SmallPrime {
        p: 2143836161,
        g: 1149399850,
        s: 1861591875,
    },
    SmallPrime {
        p: 2143762433,
        g: 1848739366,
        s: 1335934145,
    },
    SmallPrime {
        p: 2143756289,
        g: 1326674710,
        s: 102999236,
    },
    SmallPrime {
        p: 2143713281,
        g: 808061791,
        s: 1156900308,
    },
    SmallPrime {
        p: 2143690753,
        g: 388399459,
        s: 1926468019,
    },
    SmallPrime {
        p: 2143670273,
        g: 1427891374,
        s: 1756689401,
    },
    SmallPrime {
        p: 2143666177,
        g: 1912173949,
        s: 986629565,
    },
    SmallPrime {
        p: 2143645697,
        g: 2041160111,
        s: 371842865,
    },
    SmallPrime {
        p: 2143641601,
        g: 1279906897,
        s: 2023974350,
    },
    SmallPrime {
        p: 2143635457,
        g: 720473174,
        s: 1389027526,
    },
    SmallPrime {
        p: 2143621121,
        g: 1298309455,
        s: 1732632006,
    },
    SmallPrime {
        p: 2143598593,
        g: 1548762216,
        s: 1825417506,
    },
    SmallPrime {
        p: 2143567873,
        g: 620475784,
        s: 1073787233,
    },
    SmallPrime {
        p: 2143561729,
        g: 1932954575,
        s: 949167309,
    },
    SmallPrime {
        p: 2143553537,
        g: 354315656,
        s: 1652037534,
    },
    SmallPrime {
        p: 2143541249,
        g: 577424288,
        s: 1097027618,
    },
    SmallPrime {
        p: 2143531009,
        g: 357862822,
        s: 478640055,
    },
    SmallPrime {
        p: 2143522817,
        g: 2017706025,
        s: 1550531668,
    },
    SmallPrime {
        p: 2143506433,
        g: 2078127419,
        s: 1824320165,
    },
    SmallPrime {
        p: 2143488001,
        g: 613475285,
        s: 1604011510,
    },
    SmallPrime {
        p: 2143469569,
        g: 1466594987,
        s: 502095196,
    },
    SmallPrime {
        p: 2143426561,
        g: 1115430331,
        s: 1044637111,
    },
    SmallPrime {
        p: 2143383553,
        g: 9778045,
        s: 1902463734,
    },
    SmallPrime {
        p: 2143377409,
        g: 1557401276,
        s: 2056861771,
    },
    SmallPrime {
        p: 2143363073,
        g: 652036455,
        s: 1965915971,
    },
    SmallPrime {
        p: 2143260673,
        g: 1464581171,
        s: 1523257541,
    },
    SmallPrime {
        p: 2143246337,
        g: 1876119649,
        s: 764541916,
    },
    SmallPrime {
        p: 2143209473,
        g: 1614992673,
        s: 1920672844,
    },
    SmallPrime {
        p: 2143203329,
        g: 981052047,
        s: 2049774209,
    },
    SmallPrime {
        p: 2143160321,
        g: 1847355533,
        s: 728535665,
    },
    SmallPrime {
        p: 2143129601,
        g: 965558457,
        s: 603052992,
    },
    SmallPrime {
        p: 2143123457,
        g: 2140817191,
        s: 8348679,
    },
    SmallPrime {
        p: 2143100929,
        g: 1547263683,
        s: 694209023,
    },
    SmallPrime {
        p: 2143092737,
        g: 643459066,
        s: 1979934533,
    },
    SmallPrime {
        p: 2143082497,
        g: 188603778,
        s: 2026175670,
    },
    SmallPrime {
        p: 2143062017,
        g: 1657329695,
        s: 377451099,
    },
    SmallPrime {
        p: 2143051777,
        g: 114967950,
        s: 979255473,
    },
    SmallPrime {
        p: 2143025153,
        g: 1698431342,
        s: 1449196896,
    },
    SmallPrime {
        p: 2143006721,
        g: 1862741675,
        s: 1739650365,
    },
    SmallPrime {
        p: 2142996481,
        g: 756660457,
        s: 996160050,
    },
    SmallPrime {
        p: 2142976001,
        g: 927864010,
        s: 1166847574,
    },
    SmallPrime {
        p: 2142965761,
        g: 905070557,
        s: 661974566,
    },
    SmallPrime {
        p: 2142916609,
        g: 40932754,
        s: 1787161127,
    },
    SmallPrime {
        p: 2142892033,
        g: 1987985648,
        s: 675335382,
    },
    SmallPrime {
        p: 2142885889,
        g: 797497211,
        s: 1323096997,
    },
    SmallPrime {
        p: 2142871553,
        g: 2068025830,
        s: 1411877159,
    },
    SmallPrime {
        p: 2142861313,
        g: 1217177090,
        s: 1438410687,
    },
    SmallPrime {
        p: 2142830593,
        g: 409906375,
        s: 1767860634,
    },
    SmallPrime {
        p: 2142803969,
        g: 1197788993,
        s: 359782919,
    },
    SmallPrime {
        p: 2142785537,
        g: 643817365,
        s: 513932862,
    },
    SmallPrime {
        p: 2142779393,
        g: 1717046338,
        s: 218943121,
    },
    SmallPrime {
        p: 2142724097,
        g: 89336830,
        s: 416687049,
    },
    SmallPrime {
        p: 2142707713,
        g: 5944581,
        s: 1356813523,
    },
    SmallPrime {
        p: 2142658561,
        g: 887942135,
        s: 2074011722,
    },
    SmallPrime {
        p: 2142638081,
        g: 151851972,
        s: 1647339939,
    },
    SmallPrime {
        p: 2142564353,
        g: 1691505537,
        s: 1483107336,
    },
    SmallPrime {
        p: 2142533633,
        g: 1989920200,
        s: 1135938817,
    },
    SmallPrime {
        p: 2142529537,
        g: 959263126,
        s: 1531961857,
    },
    SmallPrime {
        p: 2142527489,
        g: 453251129,
        s: 1725566162,
    },
    SmallPrime {
        p: 2142502913,
        g: 1536028102,
        s: 182053257,
    },
    SmallPrime {
        p: 2142498817,
        g: 570138730,
        s: 701443447,
    },
    SmallPrime {
        p: 2142416897,
        g: 326965800,
        s: 411931819,
    },
    SmallPrime {
        p: 2142363649,
        g: 1675665410,
        s: 1517191733,
    },
    SmallPrime {
        p: 2142351361,
        g: 968529566,
        s: 1575712703,
    },
    SmallPrime {
        p: 2142330881,
        g: 1384953238,
        s: 1769087884,
    },
    SmallPrime {
        p: 2142314497,
        g: 1977173242,
        s: 1833745524,
    },
    SmallPrime {
        p: 2142289921,
        g: 95082313,
        s: 1714775493,
    },
    SmallPrime {
        p: 2142283777,
        g: 109377615,
        s: 1070584533,
    },
    SmallPrime {
        p: 2142277633,
        g: 16960510,
        s: 702157145,
    },
    SmallPrime {
        p: 2142263297,
        g: 553850819,
        s: 431364395,
    },
    SmallPrime {
        p: 2142208001,
        g: 241466367,
        s: 2053967982,
    },
    SmallPrime {
        p: 2142164993,
        g: 1795661326,
        s: 1031836848,
    },
    SmallPrime {
        p: 2142097409,
        g: 1212530046,
        s: 712772031,
    },
    SmallPrime {
        p: 2142087169,
        g: 1763869720,
        s: 822276067,
    },
    SmallPrime {
        p: 2142078977,
        g: 644065713,
        s: 1765268066,
    },
    SmallPrime {
        p: 2142074881,
        g: 112671944,
        s: 643204925,
    },
    SmallPrime {
        p: 2142044161,
        g: 1387785471,
        s: 1297890174,
    },
    SmallPrime {
        p: 2142025729,
        g: 783885537,
        s: 1000425730,
    },
    SmallPrime {
        p: 2142011393,
        g: 905662232,
        s: 1679401033,
    },
    SmallPrime {
        p: 2141974529,
        g: 799788433,
        s: 468119557,
    },
    SmallPrime {
        p: 2141943809,
        g: 1932544124,
        s: 449305555,
    },
    SmallPrime {
        p: 2141933569,
        g: 1527403256,
        s: 841867925,
    },
    SmallPrime {
        p: 2141931521,
        g: 1247076451,
        s: 743823916,
    },
    SmallPrime {
        p: 2141902849,
        g: 1199660531,
        s: 401687910,
    },
    SmallPrime {
        p: 2141890561,
        g: 150132350,
        s: 1720336972,
    },
    SmallPrime {
        p: 2141857793,
        g: 1287438162,
        s: 663880489,
    },
    SmallPrime {
        p: 2141833217,
        g: 618017731,
        s: 1819208266,
    },
    SmallPrime {
        p: 2141820929,
        g: 999578638,
        s: 1403090096,
    },
    SmallPrime {
        p: 2141786113,
        g: 81834325,
        s: 1523542501,
    },
    SmallPrime {
        p: 2141771777,
        g: 120001928,
        s: 463556492,
    },
    SmallPrime {
        p: 2141759489,
        g: 122455485,
        s: 2124928282,
    },
    SmallPrime {
        p: 2141749249,
        g: 141986041,
        s: 940339153,
    },
    SmallPrime {
        p: 2141685761,
        g: 889088734,
        s: 477141499,
    },
    SmallPrime {
        p: 2141673473,
        g: 324212681,
        s: 1122558298,
    },
    SmallPrime {
        p: 2141669377,
        g: 1175806187,
        s: 1373818177,
    },
    SmallPrime {
        p: 2141655041,
        g: 1113654822,
        s: 296887082,
    },
    SmallPrime {
        p: 2141587457,
        g: 991103258,
        s: 1585913875,
    },
    SmallPrime {
        p: 2141583361,
        g: 1401451409,
        s: 1802457360,
    },
    SmallPrime {
        p: 2141575169,
        g: 1571977166,
        s: 712760980,
    },
    SmallPrime {
        p: 2141546497,
        g: 1107849376,
        s: 1250270109,
    },
    SmallPrime {
        p: 2141515777,
        g: 196544219,
        s: 356001130,
    },
    SmallPrime {
        p: 2141495297,
        g: 1733571506,
        s: 1060744866,
    },
    SmallPrime {
        p: 2141483009,
        g: 321552363,
        s: 1168297026,
    },
    SmallPrime {
        p: 2141458433,
        g: 505818251,
        s: 733225819,
    },
    SmallPrime {
        p: 2141360129,
        g: 1026840098,
        s: 948342276,
    },
    SmallPrime {
        p: 2141325313,
        g: 945133744,
        s: 2129965998,
    },
    SmallPrime {
        p: 2141317121,
        g: 1871100260,
        s: 1843844634,
    },
    SmallPrime {
        p: 2141286401,
        g: 1790639498,
        s: 1750465696,
    },
    SmallPrime {
        p: 2141267969,
        g: 1376858592,
        s: 186160720,
    },
    SmallPrime {
        p: 2141255681,
        g: 2129698296,
        s: 1876677959,
    },
    SmallPrime {
        p: 2141243393,
        g: 2138900688,
        s: 1340009628,
    },
    SmallPrime {
        p: 2141214721,
        g: 1933049835,
        s: 1087819477,
    },
    SmallPrime {
        p: 2141212673,
        g: 1898664939,
        s: 1786328049,
    },
    SmallPrime {
        p: 2141202433,
        g: 990234828,
        s: 940682169,
    },
    SmallPrime {
        p: 2141175809,
        g: 1406392421,
        s: 993089586,
    },
    SmallPrime {
        p: 2141165569,
        g: 1263518371,
        s: 289019479,
    },
    SmallPrime {
        p: 2141073409,
        g: 1485624211,
        s: 507864514,
    },
    SmallPrime {
        p: 2141052929,
        g: 1885134788,
        s: 311252465,
    },
    SmallPrime {
        p: 2141040641,
        g: 1285021247,
        s: 280941862,
    },
    SmallPrime {
        p: 2141028353,
        g: 1527610374,
        s: 375035110,
    },
    SmallPrime {
        p: 2141011969,
        g: 1400626168,
        s: 164696620,
    },
    SmallPrime {
        p: 2140999681,
        g: 632959608,
        s: 966175067,
    },
    SmallPrime {
        p: 2140997633,
        g: 2045628978,
        s: 1290889438,
    },
    SmallPrime {
        p: 2140993537,
        g: 1412755491,
        s: 375366253,
    },
    SmallPrime {
        p: 2140942337,
        g: 719477232,
        s: 785367828,
    },
    SmallPrime {
        p: 2140925953,
        g: 45224252,
        s: 836552317,
    },
    SmallPrime {
        p: 2140917761,
        g: 1157376588,
        s: 1001839569,
    },
    SmallPrime {
        p: 2140887041,
        g: 278480752,
        s: 2098732796,
    },
    SmallPrime {
        p: 2140837889,
        g: 1663139953,
        s: 924094810,
    },
    SmallPrime {
        p: 2140788737,
        g: 802501511,
        s: 2045368990,
    },
    SmallPrime {
        p: 2140766209,
        g: 1820083885,
        s: 1800295504,
    },
    SmallPrime {
        p: 2140764161,
        g: 1169561905,
        s: 2106792035,
    },
    SmallPrime {
        p: 2140696577,
        g: 127781498,
        s: 1885987531,
    },
    SmallPrime {
        p: 2140684289,
        g: 16014477,
        s: 1098116827,
    },
    SmallPrime {
        p: 2140653569,
        g: 665960598,
        s: 1796728247,
    },
    SmallPrime {
        p: 2140594177,
        g: 1043085491,
        s: 377310938,
    },
    SmallPrime {
        p: 2140579841,
        g: 1732838211,
        s: 1504505945,
    },
    SmallPrime {
        p: 2140569601,
        g: 302071939,
        s: 358291016,
    },
    SmallPrime {
        p: 2140567553,
        g: 192393733,
        s: 1909137143,
    },
    SmallPrime {
        p: 2140557313,
        g: 406595731,
        s: 1175330270,
    },
    SmallPrime {
        p: 2140549121,
        g: 1748850918,
        s: 525007007,
    },
    SmallPrime {
        p: 2140477441,
        g: 499436566,
        s: 1031159814,
    },
    SmallPrime {
        p: 2140469249,
        g: 1886004401,
        s: 1029951320,
    },
    SmallPrime {
        p: 2140426241,
        g: 1483168100,
        s: 1676273461,
    },
    SmallPrime {
        p: 2140420097,
        g: 1779917297,
        s: 846024476,
    },
    SmallPrime {
        p: 2140413953,
        g: 522948893,
        s: 1816354149,
    },
    SmallPrime {
        p: 2140383233,
        g: 1931364473,
        s: 1296921241,
    },
    SmallPrime {
        p: 2140366849,
        g: 1917356555,
        s: 147196204,
    },
    SmallPrime {
        p: 2140354561,
        g: 16466177,
        s: 1349052107,
    },
    SmallPrime {
        p: 2140348417,
        g: 1875366972,
        s: 1860485634,
    },
    SmallPrime {
        p: 2140323841,
        g: 456498717,
        s: 1790256483,
    },
    SmallPrime {
        p: 2140321793,
        g: 1629493973,
        s: 150031888,
    },
    SmallPrime {
        p: 2140315649,
        g: 1904063898,
        s: 395510935,
    },
    SmallPrime {
        p: 2140280833,
        g: 1784104328,
        s: 831417909,
    },
    SmallPrime {
        p: 2140250113,
        g: 256087139,
        s: 697349101,
    },
    SmallPrime {
        p: 2140229633,
        g: 388553070,
        s: 243875754,
    },
    SmallPrime {
        p: 2140223489,
        g: 747459608,
        s: 1396270850,
    },
    SmallPrime {
        p: 2140200961,
        g: 507423743,
        s: 1895572209,
    },
    SmallPrime {
        p: 2140162049,
        g: 580106016,
        s: 2045297469,
    },
    SmallPrime {
        p: 2140149761,
        g: 712426444,
        s: 785217995,
    },
    SmallPrime {
        p: 2140137473,
        g: 1441607584,
        s: 536866543,
    },
    SmallPrime {
        p: 2140119041,
        g: 346538902,
        s: 1740434653,
    },
    SmallPrime {
        p: 2140090369,
        g: 282642885,
        s: 21051094,
    },
    SmallPrime {
        p: 2140076033,
        g: 1407456228,
        s: 319910029,
    },
    SmallPrime {
        p: 2140047361,
        g: 1619330500,
        s: 1488632070,
    },
    SmallPrime {
        p: 2140041217,
        g: 2089408064,
        s: 2012026134,
    },
    SmallPrime {
        p: 2140008449,
        g: 1705524800,
        s: 1613440760,
    },
    SmallPrime {
        p: 2139924481,
        g: 1846208233,
        s: 1280649481,
    },
    SmallPrime {
        p: 2139906049,
        g: 989438755,
        s: 1185646076,
    },
    SmallPrime {
        p: 2139867137,
        g: 1522314850,
        s: 372783595,
    },
    SmallPrime {
        p: 2139842561,
        g: 1681587377,
        s: 216848235,
    },
    SmallPrime {
        p: 2139826177,
        g: 2066284988,
        s: 1784999464,
    },
    SmallPrime {
        p: 2139824129,
        g: 480888214,
        s: 1513323027,
    },
    SmallPrime {
        p: 2139789313,
        g: 847937200,
        s: 858192859,
    },
    SmallPrime {
        p: 2139783169,
        g: 1642000434,
        s: 1583261448,
    },
    SmallPrime {
        p: 2139770881,
        g: 940699589,
        s: 179702100,
    },
    SmallPrime {
        p: 2139768833,
        g: 315623242,
        s: 964612676,
    },
    SmallPrime {
        p: 2139666433,
        g: 331649203,
        s: 764666914,
    },
    SmallPrime {
        p: 2139641857,
        g: 2118730799,
        s: 1313764644,
    },
    SmallPrime {
        p: 2139635713,
        g: 519149027,
        s: 519212449,
    },
    SmallPrime {
        p: 2139598849,
        g: 1526413634,
        s: 1769667104,
    },
    SmallPrime {
        p: 2139574273,
        g: 551148610,
        s: 820739925,
    },
    SmallPrime {
        p: 2139568129,
        g: 1386800242,
        s: 472447405,
    },
    SmallPrime {
        p: 2139549697,
        g: 813760130,
        s: 1412328531,
    },
    SmallPrime {
        p: 2139537409,
        g: 1615286260,
        s: 1609362979,
    },
    SmallPrime {
        p: 2139475969,
        g: 1352559299,
        s: 1696720421,
    },
    SmallPrime {
        p: 2139455489,
        g: 1048691649,
        s: 1584935400,
    },
    SmallPrime {
        p: 2139432961,
        g: 836025845,
        s: 950121150,
    },
    SmallPrime {
        p: 2139424769,
        g: 1558281165,
        s: 1635486858,
    },
    SmallPrime {
        p: 2139406337,
        g: 1728402143,
        s: 1674423301,
    },
    SmallPrime {
        p: 2139396097,
        g: 1727715782,
        s: 1483470544,
    },
    SmallPrime {
        p: 2139383809,
        g: 1092853491,
        s: 1741699084,
    },
    SmallPrime {
        p: 2139369473,
        g: 690776899,
        s: 1242798709,
    },
    SmallPrime {
        p: 2139351041,
        g: 1768782380,
        s: 2120712049,
    },
    SmallPrime {
        p: 2139334657,
        g: 1739968247,
        s: 1427249225,
    },
    SmallPrime {
        p: 2139332609,
        g: 1547189119,
        s: 623011170,
    },
    SmallPrime {
        p: 2139310081,
        g: 1346827917,
        s: 1605466350,
    },
    SmallPrime {
        p: 2139303937,
        g: 369317948,
        s: 828392831,
    },
    SmallPrime {
        p: 2139301889,
        g: 1560417239,
        s: 1788073219,
    },
    SmallPrime {
        p: 2139283457,
        g: 1303121623,
        s: 595079358,
    },
    SmallPrime {
        p: 2139248641,
        g: 1354555286,
        s: 573424177,
    },
    SmallPrime {
        p: 2139240449,
        g: 60974056,
        s: 885781403,
    },
    SmallPrime {
        p: 2139222017,
        g: 355573421,
        s: 1221054839,
    },
    SmallPrime {
        p: 2139215873,
        g: 566477826,
        s: 1724006500,
    },
    SmallPrime {
        p: 2139150337,
        g: 871437673,
        s: 1609133294,
    },
    SmallPrime {
        p: 2139144193,
        g: 1478130914,
        s: 1137491905,
    },
    SmallPrime {
        p: 2139117569,
        g: 1854880922,
        s: 964728507,
    },
    SmallPrime {
        p: 2139076609,
        g: 202405335,
        s: 756508944,
    },
    SmallPrime {
        p: 2139062273,
        g: 1399715741,
        s: 884826059,
    },
    SmallPrime {
        p: 2139045889,
        g: 1051045798,
        s: 1202295476,
    },
    SmallPrime {
        p: 2139033601,
        g: 1707715206,
        s: 632234634,
    },
    SmallPrime {
        p: 2139006977,
        g: 2035853139,
        s: 231626690,
    },
    SmallPrime {
        p: 2138951681,
        g: 183867876,
        s: 838350879,
    },
    SmallPrime {
        p: 2138945537,
        g: 1403254661,
        s: 404460202,
    },
    SmallPrime {
        p: 2138920961,
        g: 310865011,
        s: 1282911681,
    },
    SmallPrime {
        p: 2138910721,
        g: 1328496553,
        s: 103472415,
    },
    SmallPrime {
        p: 2138904577,
        g: 78831681,
        s: 993513549,
    },
    SmallPrime {
        p: 2138902529,
        g: 1319697451,
        s: 1055904361,
    },
    SmallPrime {
        p: 2138816513,
        g: 384338872,
        s: 1706202469,
    },
    SmallPrime {
        p: 2138810369,
        g: 1084868275,
        s: 405677177,
    },
    SmallPrime {
        p: 2138787841,
        g: 401181788,
        s: 1964773901,
    },
    SmallPrime {
        p: 2138775553,
        g: 1850532988,
        s: 1247087473,
    },
    SmallPrime {
        p: 2138767361,
        g: 874261901,
        s: 1576073565,
    },
    SmallPrime {
        p: 2138757121,
        g: 1187474742,
        s: 993541415,
    },
    SmallPrime {
        p: 2138748929,
        g: 1782458888,
        s: 1043206483,
    },
    SmallPrime {
        p: 2138744833,
        g: 1221500487,
        s: 800141243,
    },
    SmallPrime {
        p: 2138738689,
        g: 413465368,
        s: 1450660558,
    },
    SmallPrime {
        p: 2138695681,
        g: 739045140,
        s: 342611472,
    },
    SmallPrime {
        p: 2138658817,
        g: 1355845756,
        s: 672674190,
    },
    SmallPrime {
        p: 2138644481,
        g: 608379162,
        s: 1538874380,
    },
    SmallPrime {
        p: 2138632193,
        g: 1444914034,
        s: 686911254,
    },
    SmallPrime {
        p: 2138607617,
        g: 484707818,
        s: 1435142134,
    },
    SmallPrime {
        p: 2138591233,
        g: 539460669,
        s: 1290458549,
    },
    SmallPrime {
        p: 2138572801,
        g: 2093538990,
        s: 2011138646,
    },
    SmallPrime {
        p: 2138552321,
        g: 1149786988,
        s: 1076414907,
    },
    SmallPrime {
        p: 2138546177,
        g: 840688206,
        s: 2108985273,
    },
    SmallPrime {
        p: 2138533889,
        g: 209669619,
        s: 198172413,
    },
    SmallPrime {
        p: 2138523649,
        g: 1975879426,
        s: 1277003968,
    },
    SmallPrime {
        p: 2138490881,
        g: 1351891144,
        s: 1976858109,
    },
    SmallPrime {
        p: 2138460161,
        g: 1817321013,
        s: 1979278293,
    },
    SmallPrime {
        p: 2138429441,
        g: 1950077177,
        s: 203441928,
    },
    SmallPrime {
        p: 2138400769,
        g: 908970113,
        s: 628395069,
    },
    SmallPrime {
        p: 2138398721,
        g: 219890864,
        s: 758486760,
    },
    SmallPrime {
        p: 2138376193,
        g: 1306654379,
        s: 977554090,
    },
    SmallPrime {
        p: 2138351617,
        g: 298822498,
        s: 2004708503,
    },
    SmallPrime {
        p: 2138337281,
        g: 441457816,
        s: 1049002108,
    },
    SmallPrime {
        p: 2138320897,
        g: 1517731724,
        s: 1442269609,
    },
    SmallPrime {
        p: 2138290177,
        g: 1355911197,
        s: 1647139103,
    },
    SmallPrime {
        p: 2138234881,
        g: 531313247,
        s: 1746591962,
    },
    SmallPrime {
        p: 2138214401,
        g: 1899410930,
        s: 781416444,
    },
    SmallPrime {
        p: 2138202113,
        g: 1813477173,
        s: 1622508515,
    },
    SmallPrime {
        p: 2138191873,
        g: 1086458299,
        s: 1025408615,
    },
    SmallPrime {
        p: 2138183681,
        g: 1998800427,
        s: 827063290,
    },
    SmallPrime {
        p: 2138173441,
        g: 1921308898,
        s: 749670117,
    },
    SmallPrime {
        p: 2138103809,
        g: 1620902804,
        s: 2126787647,
    },
    SmallPrime {
        p: 2138099713,
        g: 828647069,
        s: 1892961817,
    },
    SmallPrime {
        p: 2138085377,
        g: 179405355,
        s: 1525506535,
    },
    SmallPrime {
        p: 2138060801,
        g: 615683235,
        s: 1259580138,
    },
    SmallPrime {
        p: 2138044417,
        g: 2030277840,
        s: 1731266562,
    },
    SmallPrime {
        p: 2138042369,
        g: 2087222316,
        s: 1627902259,
    },
    SmallPrime {
        p: 2138032129,
        g: 126388712,
        s: 1108640984,
    },
    SmallPrime {
        p: 2138011649,
        g: 715026550,
        s: 1017980050,
    },
    SmallPrime {
        p: 2137993217,
        g: 1693714349,
        s: 1351778704,
    },
    SmallPrime {
        p: 2137888769,
        g: 1289762259,
        s: 1053090405,
    },
    SmallPrime {
        p: 2137853953,
        g: 199991890,
        s: 1254192789,
    },
    SmallPrime {
        p: 2137833473,
        g: 941421685,
        s: 896995556,
    },
    SmallPrime {
        p: 2137817089,
        g: 750416446,
        s: 1251031181,
    },
    SmallPrime {
        p: 2137792513,
        g: 798075119,
        s: 368077456,
    },
    SmallPrime {
        p: 2137786369,
        g: 878543495,
        s: 1035375025,
    },
    SmallPrime {
        p: 2137767937,
        g: 9351178,
        s: 1156563902,
    },
    SmallPrime {
        p: 2137755649,
        g: 1382297614,
        s: 1686559583,
    },
    SmallPrime {
        p: 2137724929,
        g: 1345472850,
        s: 1681096331,
    },
    SmallPrime {
        p: 2137704449,
        g: 834666929,
        s: 630551727,
    },
    SmallPrime {
        p: 2137673729,
        g: 1646165729,
        s: 1892091571,
    },
    SmallPrime {
        p: 2137620481,
        g: 778943821,
        s: 48456461,
    },
    SmallPrime {
        p: 2137618433,
        g: 1730837875,
        s: 1713336725,
    },
    SmallPrime {
        p: 2137581569,
        g: 805610339,
        s: 1378891359,
    },
    SmallPrime {
        p: 2137538561,
        g: 204342388,
        s: 1950165220,
    },
    SmallPrime {
        p: 2137526273,
        g: 1947629754,
        s: 1500789441,
    },
    SmallPrime {
        p: 2137516033,
        g: 719902645,
        s: 1499525372,
    },
    SmallPrime {
        p: 2137491457,
        g: 230451261,
        s: 556382829,
    },
    SmallPrime {
        p: 2137440257,
        g: 979573541,
        s: 412760291,
    },
    SmallPrime {
        p: 2137374721,
        g: 927841248,
        s: 1954137185,
    },
    SmallPrime {
        p: 2137362433,
        g: 1243778559,
        s: 861024672,
    },
    SmallPrime {
        p: 2137313281,
        g: 1341338501,
        s: 980638386,
    },
    SmallPrime {
        p: 2137311233,
        g: 937415182,
        s: 1793212117,
    },
    SmallPrime {
        p: 2137255937,
        g: 795331324,
        s: 1410253405,
    },
    SmallPrime {
        p: 2137243649,
        g: 150756339,
        s: 1966999887,
    },
    SmallPrime {
        p: 2137182209,
        g: 163346914,
        s: 1939301431,
    },
    SmallPrime {
        p: 2137171969,
        g: 1952552395,
        s: 758913141,
    },
    SmallPrime {
        p: 2137159681,
        g: 570788721,
        s: 218668666,
    },
    SmallPrime {
        p: 2137147393,
        g: 1896656810,
        s: 2045670345,
    },
    SmallPrime {
        p: 2137141249,
        g: 358493842,
        s: 518199643,
    },
    SmallPrime {
        p: 2137139201,
        g: 1505023029,
        s: 674695848,
    },
    SmallPrime {
        p: 2137133057,
        g: 27911103,
        s: 830956306,
    },
    SmallPrime {
        p: 2137122817,
        g: 439771337,
        s: 1555268614,
    },
    SmallPrime {
        p: 2137116673,
        g: 790988579,
        s: 1871449599,
    },
    SmallPrime {
        p: 2137110529,
        g: 432109234,
        s: 811805080,
    },
    SmallPrime {
        p: 2137102337,
        g: 1357900653,
        s: 1184997641,
    },
    SmallPrime {
        p: 2137098241,
        g: 515119035,
        s: 1715693095,
    },
    SmallPrime {
        p: 2137090049,
        g: 408575203,
        s: 2085660657,
    },
    SmallPrime {
        p: 2137085953,
        g: 2097793407,
        s: 1349626963,
    },
    SmallPrime {
        p: 2137055233,
        g: 1556739954,
        s: 1449960883,
    },
    SmallPrime {
        p: 2137030657,
        g: 1545758650,
        s: 1369303716,
    },
    SmallPrime {
        p: 2136987649,
        g: 332602570,
        s: 103875114,
    },
    SmallPrime {
        p: 2136969217,
        g: 1499989506,
        s: 1662964115,
    },
    SmallPrime {
        p: 2136924161,
        g: 857040753,
        s: 4738842,
    },
    SmallPrime {
        p: 2136895489,
        g: 1948872712,
        s: 570436091,
    },
    SmallPrime {
        p: 2136893441,
        g: 58969960,
        s: 1568349634,
    },
    SmallPrime {
        p: 2136887297,
        g: 2127193379,
        s: 273612548,
    },
    SmallPrime {
        p: 2136850433,
        g: 111208983,
        s: 1181257116,
    },
    SmallPrime {
        p: 2136809473,
        g: 1627275942,
        s: 1680317971,
    },
    SmallPrime {
        p: 2136764417,
        g: 1574888217,
        s: 14011331,
    },
    SmallPrime {
        p: 2136741889,
        g: 14011055,
        s: 1129154251,
    },
    SmallPrime {
        p: 2136727553,
        g: 35862563,
        s: 1838555253,
    },
    SmallPrime {
        p: 2136721409,
        g: 310235666,
        s: 1363928244,
    },
    SmallPrime {
        p: 2136698881,
        g: 1612429202,
        s: 1560383828,
    },
    SmallPrime {
        p: 2136649729,
        g: 1138540131,
        s: 800014364,
    },
    SmallPrime {
        p: 2136606721,
        g: 602323503,
        s: 1433096652,
    },
    SmallPrime {
        p: 2136563713,
        g: 182209265,
        s: 1919611038,
    },
    SmallPrime {
        p: 2136555521,
        g: 324156477,
        s: 165591039,
    },
    SmallPrime {
        p: 2136549377,
        g: 195513113,
        s: 217165345,
    },
    SmallPrime {
        p: 2136526849,
        g: 1050768046,
        s: 939647887,
    },
    SmallPrime {
        p: 2136508417,
        g: 1886286237,
        s: 1619926572,
    },
    SmallPrime {
        p: 2136477697,
        g: 609647664,
        s: 35065157,
    },
    SmallPrime {
        p: 2136471553,
        g: 679352216,
        s: 1452259468,
    },
    SmallPrime {
        p: 2136457217,
        g: 128630031,
        s: 824816521,
    },
    SmallPrime {
        p: 2136422401,
        g: 19787464,
        s: 1526049830,
    },
    SmallPrime {
        p: 2136420353,
        g: 698316836,
        s: 1530623527,
    },
    SmallPrime {
        p: 2136371201,
        g: 1651862373,
        s: 1804812805,
    },
    SmallPrime {
        p: 2136334337,
        g: 326596005,
        s: 336977082,
    },
    SmallPrime {
        p: 2136322049,
        g: 63253370,
        s: 1904972151,
    },
    SmallPrime {
        p: 2136297473,
        g: 312176076,
        s: 172182411,
    },
    SmallPrime {
        p: 2136248321,
        g: 381261841,
        s: 369032670,
    },
    SmallPrime {
        p: 2136242177,
        g: 358688773,
        s: 1640007994,
    },
    SmallPrime {
        p: 2136229889,
        g: 512677188,
        s: 75585225,
    },
    SmallPrime {
        p: 2136219649,
        g: 2095003250,
        s: 1970086149,
    },
    SmallPrime {
        p: 2136207361,
        g: 1909650722,
        s: 537760675,
    },
    SmallPrime {
        p: 2136176641,
        g: 1334616195,
        s: 1533487619,
    },
    SmallPrime {
        p: 2136158209,
        g: 2096285632,
        s: 1793285210,
    },
    SmallPrime {
        p: 2136143873,
        g: 1897347517,
        s: 293843959,
    },
    SmallPrime {
        p: 2136133633,
        g: 923586222,
        s: 1022655978,
    },
    SmallPrime {
        p: 2136096769,
        g: 1464868191,
        s: 1515074410,
    },
    SmallPrime {
        p: 2136094721,
        g: 2020679520,
        s: 2061636104,
    },
    SmallPrime {
        p: 2136076289,
        g: 290798503,
        s: 1814726809,
    },
    SmallPrime {
        p: 2136041473,
        g: 156415894,
        s: 1250757633,
    },
    SmallPrime {
        p: 2135996417,
        g: 297459940,
        s: 1132158924,
    },
    SmallPrime {
        p: 2135955457,
        g: 538755304,
        s: 1688831340,
    },
];

static REV10: [u16; 1024] = [
    0, 512, 256, 768, 128, 640, 384, 896, 64, 576, 320, 832, 192, 704, 448, 960, 32, 544, 288, 800,
    160, 672, 416, 928, 96, 608, 352, 864, 224, 736, 480, 992, 16, 528, 272, 784, 144, 656, 400,
    912, 80, 592, 336, 848, 208, 720, 464, 976, 48, 560, 304, 816, 176, 688, 432, 944, 112, 624,
    368, 880, 240, 752, 496, 1008, 8, 520, 264, 776, 136, 648, 392, 904, 72, 584, 328, 840, 200,
    712, 456, 968, 40, 552, 296, 808, 168, 680, 424, 936, 104, 616, 360, 872, 232, 744, 488, 1000,
    24, 536, 280, 792, 152, 664, 408, 920, 88, 600, 344, 856, 216, 728, 472, 984, 56, 568, 312,
    824, 184, 696, 440, 952, 120, 632, 376, 888, 248, 760, 504, 1016, 4, 516, 260, 772, 132, 644,
    388, 900, 68, 580, 324, 836, 196, 708, 452, 964, 36, 548, 292, 804, 164, 676, 420, 932, 100,
    612, 356, 868, 228, 740, 484, 996, 20, 532, 276, 788, 148, 660, 404, 916, 84, 596, 340, 852,
    212, 724, 468, 980, 52, 564, 308, 820, 180, 692, 436, 948, 116, 628, 372, 884, 244, 756, 500,
    1012, 12, 524, 268, 780, 140, 652, 396, 908, 76, 588, 332, 844, 204, 716, 460, 972, 44, 556,
    300, 812, 172, 684, 428, 940, 108, 620, 364, 876, 236, 748, 492, 1004, 28, 540, 284, 796, 156,
    668, 412, 924, 92, 604, 348, 860, 220, 732, 476, 988, 60, 572, 316, 828, 188, 700, 444, 956,
    124, 636, 380, 892, 252, 764, 508, 1020, 2, 514, 258, 770, 130, 642, 386, 898, 66, 578, 322,
    834, 194, 706, 450, 962, 34, 546, 290, 802, 162, 674, 418, 930, 98, 610, 354, 866, 226, 738,
    482, 994, 18, 530, 274, 786, 146, 658, 402, 914, 82, 594, 338, 850, 210, 722, 466, 978, 50,
    562, 306, 818, 178, 690, 434, 946, 114, 626, 370, 882, 242, 754, 498, 1010, 10, 522, 266, 778,
    138, 650, 394, 906, 74, 586, 330, 842, 202, 714, 458, 970, 42, 554, 298, 810, 170, 682, 426,
    938, 106, 618, 362, 874, 234, 746, 490, 1002, 26, 538, 282, 794, 154, 666, 410, 922, 90, 602,
    346, 858, 218, 730, 474, 986, 58, 570, 314, 826, 186, 698, 442, 954, 122, 634, 378, 890, 250,
    762, 506, 1018, 6, 518, 262, 774, 134, 646, 390, 902, 70, 582, 326, 838, 198, 710, 454, 966,
    38, 550, 294, 806, 166, 678, 422, 934, 102, 614, 358, 870, 230, 742, 486, 998, 22, 534, 278,
    790, 150, 662, 406, 918, 86, 598, 342, 854, 214, 726, 470, 982, 54, 566, 310, 822, 182, 694,
    438, 950, 118, 630, 374, 886, 246, 758, 502, 1014, 14, 526, 270, 782, 142, 654, 398, 910, 78,
    590, 334, 846, 206, 718, 462, 974, 46, 558, 302, 814, 174, 686, 430, 942, 110, 622, 366, 878,
    238, 750, 494, 1006, 30, 542, 286, 798, 158, 670, 414, 926, 94, 606, 350, 862, 222, 734, 478,
    990, 62, 574, 318, 830, 190, 702, 446, 958, 126, 638, 382, 894, 254, 766, 510, 1022, 1, 513,
    257, 769, 129, 641, 385, 897, 65, 577, 321, 833, 193, 705, 449, 961, 33, 545, 289, 801, 161,
    673, 417, 929, 97, 609, 353, 865, 225, 737, 481, 993, 17, 529, 273, 785, 145, 657, 401, 913,
    81, 593, 337, 849, 209, 721, 465, 977, 49, 561, 305, 817, 177, 689, 433, 945, 113, 625, 369,
    881, 241, 753, 497, 1009, 9, 521, 265, 777, 137, 649, 393, 905, 73, 585, 329, 841, 201, 713,
    457, 969, 41, 553, 297, 809, 169, 681, 425, 937, 105, 617, 361, 873, 233, 745, 489, 1001, 25,
    537, 281, 793, 153, 665, 409, 921, 89, 601, 345, 857, 217, 729, 473, 985, 57, 569, 313, 825,
    185, 697, 441, 953, 121, 633, 377, 889, 249, 761, 505, 1017, 5, 517, 261, 773, 133, 645, 389,
    901, 69, 581, 325, 837, 197, 709, 453, 965, 37, 549, 293, 805, 165, 677, 421, 933, 101, 613,
    357, 869, 229, 741, 485, 997, 21, 533, 277, 789, 149, 661, 405, 917, 85, 597, 341, 853, 213,
    725, 469, 981, 53, 565, 309, 821, 181, 693, 437, 949, 117, 629, 373, 885, 245, 757, 501, 1013,
    13, 525, 269, 781, 141, 653, 397, 909, 77, 589, 333, 845, 205, 717, 461, 973, 45, 557, 301,
    813, 173, 685, 429, 941, 109, 621, 365, 877, 237, 749, 493, 1005, 29, 541, 285, 797, 157, 669,
    413, 925, 93, 605, 349, 861, 221, 733, 477, 989, 61, 573, 317, 829, 189, 701, 445, 957, 125,
    637, 381, 893, 253, 765, 509, 1021, 3, 515, 259, 771, 131, 643, 387, 899, 67, 579, 323, 835,
    195, 707, 451, 963, 35, 547, 291, 803, 163, 675, 419, 931, 99, 611, 355, 867, 227, 739, 483,
    995, 19, 531, 275, 787, 147, 659, 403, 915, 83, 595, 339, 851, 211, 723, 467, 979, 51, 563,
    307, 819, 179, 691, 435, 947, 115, 627, 371, 883, 243, 755, 499, 1011, 11, 523, 267, 779, 139,
    651, 395, 907, 75, 587, 331, 843, 203, 715, 459, 971, 43, 555, 299, 811, 171, 683, 427, 939,
    107, 619, 363, 875, 235, 747, 491, 1003, 27, 539, 283, 795, 155, 667, 411, 923, 91, 603, 347,
    859, 219, 731, 475, 987, 59, 571, 315, 827, 187, 699, 443, 955, 123, 635, 379, 891, 251, 763,
    507, 1019, 7, 519, 263, 775, 135, 647, 391, 903, 71, 583, 327, 839, 199, 711, 455, 967, 39,
    551, 295, 807, 167, 679, 423, 935, 103, 615, 359, 871, 231, 743, 487, 999, 23, 535, 279, 791,
    151, 663, 407, 919, 87, 599, 343, 855, 215, 727, 471, 983, 55, 567, 311, 823, 183, 695, 439,
    951, 119, 631, 375, 887, 247, 759, 503, 1015, 15, 527, 271, 783, 143, 655, 399, 911, 79, 591,
    335, 847, 207, 719, 463, 975, 47, 559, 303, 815, 175, 687, 431, 943, 111, 623, 367, 879, 239,
    751, 495, 1007, 31, 543, 287, 799, 159, 671, 415, 927, 95, 607, 351, 863, 223, 735, 479, 991,
    63, 575, 319, 831, 191, 703, 447, 959, 127, 639, 383, 895, 255, 767, 511, 1023,
];

static GAUSS_1024_12289: [u64; 27] = [
    1283868770400643928,
    6416574995475331444,
    4078260278032692663,
    2353523259288686585,
    1227179971273316331,
    575931623374121527,
    242543240509105209,
    91437049221049666,
    30799446349977173,
    9255276791179340,
    2478152334826140,
    590642893610164,
    125206034929641,
    23590435911403,
    3948334035941,
    586753615614,
    77391054539,
    9056793210,
    940121950,
    86539696,
    7062824,
    510971,
    32764,
    1862,
    94,
    4,
    0,
];

// ======================================================================
// Modular arithmetic (31-bit Montgomery)
// ======================================================================

#[inline(always)]
fn modp_set(x: i32, p: u32) -> u32 {
    let mut w = x as u32;
    w = w.wrapping_add(p & (w >> 31).wrapping_neg());
    w
}

#[inline(always)]
fn modp_norm(x: u32, p: u32) -> i32 {
    (x.wrapping_sub(p & (((x.wrapping_sub((p + 1) >> 1)) >> 31).wrapping_sub(1)))) as i32
}

fn modp_ninv31(p: u32) -> u32 {
    let mut y = 2u32.wrapping_sub(p);
    y = y.wrapping_mul(2u32.wrapping_sub(p.wrapping_mul(y)));
    y = y.wrapping_mul(2u32.wrapping_sub(p.wrapping_mul(y)));
    y = y.wrapping_mul(2u32.wrapping_sub(p.wrapping_mul(y)));
    y = y.wrapping_mul(2u32.wrapping_sub(p.wrapping_mul(y)));
    0x7FFFFFFFu32 & y.wrapping_neg()
}

#[inline(always)]
fn modp_r(p: u32) -> u32 {
    (1u32 << 31).wrapping_sub(p)
}

#[inline(always)]
fn modp_add(a: u32, b: u32, p: u32) -> u32 {
    let mut d = a.wrapping_add(b).wrapping_sub(p);
    d = d.wrapping_add(p & (d >> 31).wrapping_neg());
    d
}

#[inline(always)]
fn modp_sub(a: u32, b: u32, p: u32) -> u32 {
    let mut d = a.wrapping_sub(b);
    d = d.wrapping_add(p & (d >> 31).wrapping_neg());
    d
}

#[inline(always)]
fn modp_montymul(a: u32, b: u32, p: u32, p0i: u32) -> u32 {
    let z = (a as u64).wrapping_mul(b as u64);
    let w = ((z.wrapping_mul(p0i as u64)) & 0x7FFFFFFF).wrapping_mul(p as u64);
    let mut d = ((z.wrapping_add(w)) >> 31) as u32;
    d = d.wrapping_sub(p);
    d = d.wrapping_add(p & (d >> 31).wrapping_neg());
    d
}

fn modp_r2(p: u32, p0i: u32) -> u32 {
    let mut z = modp_r(p);
    z = modp_add(z, z, p);
    z = modp_montymul(z, z, p, p0i);
    z = modp_montymul(z, z, p, p0i);
    z = modp_montymul(z, z, p, p0i);
    z = modp_montymul(z, z, p, p0i);
    z = modp_montymul(z, z, p, p0i);
    z = (z.wrapping_add(p & (z & 1).wrapping_neg())) >> 1;
    z
}

fn modp_rx(x: u32, p: u32, p0i: u32, r2: u32) -> u32 {
    let x = x.wrapping_sub(1);
    let mut r = r2;
    let mut z = modp_r(p);
    let mut i = 0u32;
    while (1u32 << i) <= x {
        if (x & (1u32 << i)) != 0 {
            z = modp_montymul(z, r, p, p0i);
        }
        r = modp_montymul(r, r, p, p0i);
        i += 1;
    }
    z
}

fn modp_div(a: u32, b: u32, p: u32, p0i: u32, r: u32) -> u32 {
    let e = p.wrapping_sub(2);
    let mut z = r;
    for i in (0..=30i32).rev() {
        z = modp_montymul(z, z, p, p0i);
        let z2 = modp_montymul(z, b, p, p0i);
        z ^= (z ^ z2) & ((e >> i) & 1).wrapping_neg();
    }
    z = modp_montymul(z, 1, p, p0i);
    modp_montymul(a, z, p, p0i)
}

// ======================================================================
// NTT
// ======================================================================

fn modp_mkgm2(gm: &mut [u32], igm: &mut [u32], logn: u32, g: u32, p: u32, p0i: u32) {
    let n: usize = 1 << logn;
    let r2 = modp_r2(p, p0i);
    let mut g = modp_montymul(g, r2, p, p0i);
    for k in logn..10 {
        let _ = k;
        g = modp_montymul(g, g, p, p0i);
    }
    let ig = modp_div(r2, g, p, p0i, modp_r(p));
    let k = 10 - logn;
    let mut x1 = modp_r(p);
    let mut x2 = modp_r(p);
    for u in 0..n {
        let v = REV10[(u << k) as usize] as usize;
        gm[v] = x1;
        igm[v] = x2;
        x1 = modp_montymul(x1, g, p, p0i);
        x2 = modp_montymul(x2, ig, p, p0i);
    }
}

fn modp_ntt2_ext(a: &mut [u32], stride: usize, gm: &[u32], logn: u32, p: u32, p0i: u32) {
    if logn == 0 {
        return;
    }
    let n: usize = 1 << logn;
    let mut t = n;
    let mut m: usize = 1;
    while m < n {
        let ht = t >> 1;
        let mut v1: usize = 0;
        for u in 0..m {
            let s = gm[m + u];
            let mut r1 = v1 * stride;
            let mut r2 = r1 + ht * stride;
            for _ in 0..ht {
                let x = a[r1];
                let y = modp_montymul(a[r2], s, p, p0i);
                a[r1] = modp_add(x, y, p);
                a[r2] = modp_sub(x, y, p);
                r1 += stride;
                r2 += stride;
            }
            v1 += t;
        }
        t = ht;
        m <<= 1;
    }
}

fn modp_ntt2(a: &mut [u32], gm: &[u32], logn: u32, p: u32, p0i: u32) {
    modp_ntt2_ext(a, 1, gm, logn, p, p0i);
}

fn modp_intt2_ext(a: &mut [u32], stride: usize, igm: &[u32], logn: u32, p: u32, p0i: u32) {
    if logn == 0 {
        return;
    }
    let n: usize = 1 << logn;
    let mut t: usize = 1;
    let mut m = n;
    while m > 1 {
        let hm = m >> 1;
        let dt = t << 1;
        let mut v1: usize = 0;
        for u in 0..hm {
            let s = igm[hm + u];
            let mut r1 = v1 * stride;
            let mut r2 = r1 + t * stride;
            for _ in 0..t {
                let x = a[r1];
                let y = a[r2];
                a[r1] = modp_add(x, y, p);
                a[r2] = modp_montymul(modp_sub(x, y, p), s, p, p0i);
                r1 += stride;
                r2 += stride;
            }
            v1 += dt;
        }
        t = dt;
        m = hm;
    }
    let ni = 1u32 << (31 - logn);
    let mut r = 0;
    for _ in 0..n {
        a[r] = modp_montymul(a[r], ni, p, p0i);
        r += stride;
    }
}

fn modp_intt2(a: &mut [u32], igm: &[u32], logn: u32, p: u32, p0i: u32) {
    modp_intt2_ext(a, 1, igm, logn, p, p0i);
}

fn modp_poly_rec_res(f: &mut [u32], logn: u32, p: u32, p0i: u32, r2: u32) {
    let hn: usize = 1 << (logn - 1);
    for u in 0..hn {
        let w0 = f[(u << 1) + 0];
        let w1 = f[(u << 1) + 1];
        f[u] = modp_montymul(modp_montymul(w0, w1, p, p0i), r2, p, p0i);
    }
}

// ======================================================================
// Bignum operations
// ======================================================================

fn zint_sub(a: &mut [u32], b: &[u32], len: usize, ctl: u32) -> u32 {
    let mut cc: u32 = 0;
    let m = ctl.wrapping_neg();
    for u in 0..len {
        let aw = a[u];
        let w = aw.wrapping_sub(b[u]).wrapping_sub(cc);
        cc = w >> 31;
        a[u] = aw ^ (((w & 0x7FFFFFFF) ^ aw) & m);
    }
    cc
}

fn zint_mul_small(m: &mut [u32], mlen: usize, x: u32) -> u32 {
    let mut cc: u32 = 0;
    for u in 0..mlen {
        let z = (m[u] as u64).wrapping_mul(x as u64).wrapping_add(cc as u64);
        m[u] = (z as u32) & 0x7FFFFFFF;
        cc = (z >> 31) as u32;
    }
    cc
}

fn zint_mod_small_unsigned(d: &[u32], dlen: usize, p: u32, p0i: u32, r2: u32) -> u32 {
    let mut x: u32 = 0;
    let mut u = dlen;
    while u > 0 {
        u -= 1;
        x = modp_montymul(x, r2, p, p0i);
        let mut w = d[u].wrapping_sub(p);
        w = w.wrapping_add(p & (w >> 31).wrapping_neg());
        x = modp_add(x, w, p);
    }
    x
}

fn zint_mod_small_signed(d: &[u32], dlen: usize, p: u32, p0i: u32, r2: u32, rx: u32) -> u32 {
    if dlen == 0 {
        return 0;
    }
    let z = zint_mod_small_unsigned(d, dlen, p, p0i, r2);
    modp_sub(z, rx & (d[dlen - 1] >> 30).wrapping_neg(), p)
}

fn zint_add_mul_small(x: &mut [u32], y: &[u32], len: usize, s: u32) {
    let mut cc: u32 = 0;
    for u in 0..len {
        let z = (y[u] as u64)
            .wrapping_mul(s as u64)
            .wrapping_add(x[u] as u64)
            .wrapping_add(cc as u64);
        x[u] = (z as u32) & 0x7FFFFFFF;
        cc = (z >> 31) as u32;
    }
    x[len] = cc;
}

fn zint_norm_zero(x: &mut [u32], p: &[u32], len: usize) {
    let mut r: u32 = 0;
    let mut bb: u32 = 0;
    let mut u = len;
    while u > 0 {
        u -= 1;
        let wx = x[u];
        let wp = (p[u] >> 1) | (bb << 30);
        bb = p[u] & 1;
        let mut cc = wp.wrapping_sub(wx);
        cc = (cc.wrapping_neg() >> 31) | (cc >> 31).wrapping_neg();
        r |= cc & ((r & 1).wrapping_sub(1));
    }
    zint_sub(x, p, len, r >> 31);
}

fn zint_rebuild_crt(
    xx: &mut [u32],
    xlen: usize,
    xstride: usize,
    num: usize,
    primes: &[SmallPrime],
    normalize_signed: bool,
    tmp: &mut [u32],
) {
    tmp[0] = primes[0].p;
    for u in 1..xlen {
        let p = primes[u].p;
        let s = primes[u].s;
        let p0i = modp_ninv31(p);
        let r2 = modp_r2(p, p0i);
        for v in 0..num {
            let x_off = v * xstride;
            let xp = xx[x_off + u];
            let xq = zint_mod_small_unsigned(&xx[x_off..], u, p, p0i, r2);
            let xr = modp_montymul(s, modp_sub(xp, xq, p), p, p0i);
            // zint_add_mul_small on x[x_off..], tmp, u, xr
            let mut cc: u32 = 0;
            for i in 0..u {
                let z = (tmp[i] as u64)
                    .wrapping_mul(xr as u64)
                    .wrapping_add(xx[x_off + i] as u64)
                    .wrapping_add(cc as u64);
                xx[x_off + i] = (z as u32) & 0x7FFFFFFF;
                cc = (z >> 31) as u32;
            }
            xx[x_off + u] = cc;
        }
        tmp[u] = zint_mul_small(tmp, u, p);
    }
    if normalize_signed {
        for u in 0..num {
            let x_off = u * xstride;
            // zint_norm_zero inline
            let mut r: u32 = 0;
            let mut bb: u32 = 0;
            let mut j = xlen;
            while j > 0 {
                j -= 1;
                let wx = xx[x_off + j];
                let wp = (tmp[j] >> 1) | (bb << 30);
                bb = tmp[j] & 1;
                let mut cc = wp.wrapping_sub(wx);
                cc = (cc.wrapping_neg() >> 31) | (cc >> 31).wrapping_neg();
                r |= cc & ((r & 1).wrapping_sub(1));
            }
            // zint_sub if r >> 31
            let ctl = r >> 31;
            let m = ctl.wrapping_neg();
            let mut ccc: u32 = 0;
            for j in 0..xlen {
                let aw = xx[x_off + j];
                let w = aw.wrapping_sub(tmp[j]).wrapping_sub(ccc);
                ccc = w >> 31;
                xx[x_off + j] = aw ^ (((w & 0x7FFFFFFF) ^ aw) & m);
            }
        }
    }
}

fn zint_negate(a: &mut [u32], len: usize, ctl: u32) {
    let mut cc = ctl;
    let m = ctl.wrapping_neg() >> 1;
    for u in 0..len {
        let aw = (a[u] ^ m).wrapping_add(cc);
        a[u] = aw & 0x7FFFFFFF;
        cc = aw >> 31;
    }
}

fn zint_co_reduce(
    a: &mut [u32],
    b: &mut [u32],
    len: usize,
    xa: i64,
    xb: i64,
    ya: i64,
    yb: i64,
) -> u32 {
    let mut cca: i64 = 0;
    let mut ccb: i64 = 0;
    for u in 0..len {
        let wa = a[u] as u64;
        let wb = b[u] as u64;
        let za = (wa as i64)
            .wrapping_mul(xa)
            .wrapping_add((wb as i64).wrapping_mul(xb))
            .wrapping_add(cca);
        let zb = (wa as i64)
            .wrapping_mul(ya)
            .wrapping_add((wb as i64).wrapping_mul(yb))
            .wrapping_add(ccb);
        if u > 0 {
            a[u - 1] = (za as u32) & 0x7FFFFFFF;
            b[u - 1] = (zb as u32) & 0x7FFFFFFF;
        }
        cca = za >> 31;
        ccb = zb >> 31;
    }
    a[len - 1] = cca as u32;
    b[len - 1] = ccb as u32;
    let nega = ((cca as u64) >> 63) as u32;
    let negb = ((ccb as u64) >> 63) as u32;
    zint_negate(a, len, nega);
    zint_negate(b, len, negb);
    nega | (negb << 1)
}

fn zint_finish_mod(a: &mut [u32], len: usize, m: &[u32], neg: u32) {
    let mut cc: u32 = 0;
    for u in 0..len {
        cc = (a[u].wrapping_sub(m[u]).wrapping_sub(cc)) >> 31;
    }
    let xm = neg.wrapping_neg() >> 1;
    let ym = (neg | (1u32.wrapping_sub(cc))).wrapping_neg();
    cc = neg;
    for u in 0..len {
        let aw = a[u];
        let mw = (m[u] ^ xm) & ym;
        let w = aw.wrapping_sub(mw).wrapping_sub(cc);
        a[u] = w & 0x7FFFFFFF;
        cc = w >> 31;
    }
}

fn zint_co_reduce_mod(
    a: &mut [u32],
    b: &mut [u32],
    m: &[u32],
    len: usize,
    m0i: u32,
    xa: i64,
    xb: i64,
    ya: i64,
    yb: i64,
) {
    let fa = ((a[0]
        .wrapping_mul(xa as u32)
        .wrapping_add(b[0].wrapping_mul(xb as u32)))
    .wrapping_mul(m0i))
        & 0x7FFFFFFF;
    let fb = ((a[0]
        .wrapping_mul(ya as u32)
        .wrapping_add(b[0].wrapping_mul(yb as u32)))
    .wrapping_mul(m0i))
        & 0x7FFFFFFF;
    let mut cca: i64 = 0;
    let mut ccb: i64 = 0;
    for u in 0..len {
        let wa = a[u] as u64;
        let wb = b[u] as u64;
        let za = (wa as i64)
            .wrapping_mul(xa)
            .wrapping_add((wb as i64).wrapping_mul(xb))
            .wrapping_add((m[u] as i64).wrapping_mul(fa as i64))
            .wrapping_add(cca);
        let zb = (wa as i64)
            .wrapping_mul(ya)
            .wrapping_add((wb as i64).wrapping_mul(yb))
            .wrapping_add((m[u] as i64).wrapping_mul(fb as i64))
            .wrapping_add(ccb);
        if u > 0 {
            a[u - 1] = (za as u32) & 0x7FFFFFFF;
            b[u - 1] = (zb as u32) & 0x7FFFFFFF;
        }
        cca = za >> 31;
        ccb = zb >> 31;
    }
    a[len - 1] = cca as u32;
    b[len - 1] = ccb as u32;
    zint_finish_mod(a, len, m, ((cca as u64) >> 63) as u32);
    zint_finish_mod(b, len, m, ((ccb as u64) >> 63) as u32);
}

fn zint_bezout(
    u_out: &mut [u32],
    v_out: &mut [u32],
    x: &[u32],
    y: &[u32],
    len: usize,
    tmp: &mut [u32],
) -> bool {
    if len == 0 {
        return false;
    }
    let u0 = u_out;
    let v0 = v_out;
    let (u1, rest) = tmp.split_at_mut(len);
    let (v1, rest) = rest.split_at_mut(len);
    let (a, rest) = rest.split_at_mut(len);
    let (b, _) = rest.split_at_mut(len);

    let x0i = modp_ninv31(x[0]);
    let y0i = modp_ninv31(y[0]);

    a.copy_from_slice(&x[..len]);
    b.copy_from_slice(&y[..len]);
    u0[0] = 1;
    for i in 1..len {
        u0[i] = 0;
    }
    for i in 0..len {
        v0[i] = 0;
    }
    u1.copy_from_slice(&y[..len]);
    v1.copy_from_slice(&x[..len]);
    v1[0] -= 1;

    let mut num = 62 * (len as u32) + 30;
    while num >= 30 {
        let mut c0: u32 = u32::MAX;
        let mut c1: u32 = u32::MAX;
        let mut a0: u32 = 0;
        let mut a1: u32 = 0;
        let mut b0: u32 = 0;
        let mut b1: u32 = 0;
        let mut j = len;
        while j > 0 {
            j -= 1;
            let aw = a[j];
            let bw = b[j];
            a0 ^= (a0 ^ aw) & c0;
            a1 ^= (a1 ^ aw) & c1;
            b0 ^= (b0 ^ bw) & c0;
            b1 ^= (b1 ^ bw) & c1;
            c1 = c0;
            c0 &= (((aw | bw).wrapping_add(0x7FFFFFFF)) >> 31).wrapping_sub(1);
        }
        a1 |= a0 & c1;
        a0 &= !c1;
        b1 |= b0 & c1;
        b0 &= !c1;
        let mut a_hi: u64 = ((a0 as u64) << 31) + a1 as u64;
        let mut b_hi: u64 = ((b0 as u64) << 31) + b1 as u64;
        let mut a_lo = a[0];
        let mut b_lo = b[0];

        let mut pa: i64 = 1;
        let mut pb: i64 = 0;
        let mut qa: i64 = 0;
        let mut qb: i64 = 1;
        for i in 0..31u32 {
            let rz = b_hi.wrapping_sub(a_hi);
            let rt = ((rz ^ ((a_hi ^ b_hi) & (a_hi ^ rz))) >> 63) as u32;
            let oa = (a_lo >> i) & 1;
            let ob = (b_lo >> i) & 1;
            let c_ab = oa & ob & rt;
            let c_ba = oa & ob & !rt;
            let c_a = c_ab | (oa ^ 1);

            a_lo = a_lo.wrapping_sub(b_lo & c_ab.wrapping_neg());
            a_hi = a_hi.wrapping_sub(b_hi & (c_ab as u64).wrapping_neg());
            pa -= qa & (c_ab as i64).wrapping_neg();
            pb -= qb & (c_ab as i64).wrapping_neg();
            b_lo = b_lo.wrapping_sub(a_lo & c_ba.wrapping_neg());
            b_hi = b_hi.wrapping_sub(a_hi & (c_ba as u64).wrapping_neg());
            qa -= pa & (c_ba as i64).wrapping_neg();
            qb -= pb & (c_ba as i64).wrapping_neg();
            a_lo = a_lo.wrapping_add(a_lo & c_a.wrapping_sub(1));
            a_hi ^= (a_hi ^ (a_hi >> 1)) & (c_a as u64).wrapping_neg();
            pa += pa & ((c_a as i64).wrapping_sub(1));
            pb += pb & ((c_a as i64).wrapping_sub(1));
            b_lo = b_lo.wrapping_add(b_lo & c_a.wrapping_neg());
            b_hi ^= (b_hi ^ (b_hi >> 1)) & ((c_a as u64).wrapping_sub(1));
            qa += qa & (c_a as i64).wrapping_neg();
            qb += qb & (c_a as i64).wrapping_neg();
        }

        let r = zint_co_reduce(a, b, len, pa, pb, qa, qb);
        pa -= (pa + pa) & ((r & 1) as i64).wrapping_neg();
        pb -= (pb + pb) & ((r & 1) as i64).wrapping_neg();
        qa -= (qa + qa) & ((r >> 1) as i64).wrapping_neg();
        qb -= (qb + qb) & ((r >> 1) as i64).wrapping_neg();
        zint_co_reduce_mod(u0, u1, y, len, y0i, pa, pb, qa, qb);
        zint_co_reduce_mod(v0, v1, x, len, x0i, pa, pb, qa, qb);

        num -= 30;
    }

    let mut rc = a[0] ^ 1;
    for j in 1..len {
        rc |= a[j];
    }
    ((1u32.wrapping_sub((rc | rc.wrapping_neg()) >> 31)) & x[0] & y[0]) != 0
}

fn zint_add_scaled_mul_small(
    x: &mut [u32],
    xlen: usize,
    y: &[u32],
    ylen: usize,
    k: i32,
    sch: u32,
    scl: u32,
) {
    if ylen == 0 {
        return;
    }
    let ysign = (y[ylen - 1] >> 30).wrapping_neg() >> 1;
    let mut tw: u32 = 0;
    let mut cc: i32 = 0;
    for u in (sch as usize)..xlen {
        let v = u - sch as usize;
        let wy = if v < ylen { y[v] } else { ysign };
        let wys = ((wy << scl) & 0x7FFFFFFF) | tw;
        tw = wy >> (31 - scl);
        let z = (wys as i64)
            .wrapping_mul(k as i64)
            .wrapping_add(x[u] as i64)
            .wrapping_add(cc as i64);
        x[u] = (z as u32) & 0x7FFFFFFF;
        cc = ((z as u64) >> 31) as i32;
    }
}

fn zint_sub_scaled(x: &mut [u32], xlen: usize, y: &[u32], ylen: usize, sch: u32, scl: u32) {
    if ylen == 0 {
        return;
    }
    let ysign = (y[ylen - 1] >> 30).wrapping_neg() >> 1;
    let mut tw: u32 = 0;
    let mut cc: u32 = 0;
    for u in (sch as usize)..xlen {
        let v = u - sch as usize;
        let wy = if v < ylen { y[v] } else { ysign };
        let wys = ((wy << scl) & 0x7FFFFFFF) | tw;
        tw = wy >> (31 - scl);
        let w = x[u].wrapping_sub(wys).wrapping_sub(cc);
        x[u] = w & 0x7FFFFFFF;
        cc = w >> 31;
    }
}

#[inline]
fn zint_one_to_plain(x: &[u32]) -> i32 {
    let mut w = x[0];
    w |= (w & 0x40000000) << 1;
    w as i32
}

// ======================================================================
// Polynomial conversion utilities
// ======================================================================

fn poly_big_to_fp(d: &mut [Fpr], f: &[u32], flen: usize, fstride: usize, logn: u32) {
    let n: usize = 1 << logn;
    if flen == 0 {
        for u in 0..n {
            d[u] = FPR_ZERO;
        }
        return;
    }
    for u in 0..n {
        let f_off = u * fstride;
        let neg = (f[f_off + flen - 1] >> 30).wrapping_neg();
        let xm = neg >> 1;
        let mut cc = neg & 1;
        let mut x = FPR_ZERO;
        let mut fsc = FPR_ONE;
        for v in 0..flen {
            let mut w = (f[f_off + v] ^ xm).wrapping_add(cc);
            cc = w >> 31;
            w &= 0x7FFFFFFF;
            w = w.wrapping_sub((w << 1) & neg);
            x = fpr_add(x, fpr_mul(fpr_of(w as i32 as i64), fsc));
            fsc = fpr_mul(fsc, FPR_PTWO31);
        }
        d[u] = x;
    }
}

fn poly_big_to_small(d: &mut [i8], s: &[u32], lim: i32, logn: u32) -> bool {
    let n: usize = 1 << logn;
    for u in 0..n {
        let z = zint_one_to_plain(&s[u..]);
        if z < -lim || z > lim {
            return false;
        }
        d[u] = z as i8;
    }
    true
}

fn poly_small_sqnorm(f: &[i8], logn: u32) -> u32 {
    let n: usize = 1 << logn;
    let mut s: u32 = 0;
    let mut ng: u32 = 0;
    for u in 0..n {
        let z = f[u] as i32;
        s = s.wrapping_add((z * z) as u32);
        ng |= s;
    }
    s | (ng >> 31).wrapping_neg()
}

fn poly_small_to_fp(x: &mut [Fpr], f: &[i8], logn: u32) {
    let n: usize = 1 << logn;
    for u in 0..n {
        x[u] = fpr_of(f[u] as i64);
    }
}

// ======================================================================
// Size tables for NTRU solver
// ======================================================================

static MAX_BL_SMALL: [usize; 11] = [1, 1, 2, 2, 4, 7, 14, 27, 53, 106, 209];
static MAX_BL_LARGE: [usize; 10] = [2, 2, 5, 7, 12, 21, 40, 78, 157, 308];

struct BitLength {
    avg: i32,
    std: i32,
}

static BITLENGTH: [BitLength; 11] = [
    BitLength { avg: 4, std: 0 },
    BitLength { avg: 11, std: 1 },
    BitLength { avg: 24, std: 1 },
    BitLength { avg: 50, std: 1 },
    BitLength { avg: 102, std: 1 },
    BitLength { avg: 202, std: 2 },
    BitLength { avg: 401, std: 4 },
    BitLength { avg: 794, std: 5 },
    BitLength { avg: 1577, std: 8 },
    BitLength { avg: 3138, std: 13 },
    BitLength { avg: 6308, std: 25 },
];

// ======================================================================
// Gaussian sampling for key generation
// ======================================================================

/// Extract a 64-bit value from SHAKE256 in little-endian order,
/// matching the C reference's get_rng_u64() when FALCON_KG_CHACHA20=0.
fn get_rng_u64(rng: &mut InnerShake256Context) -> u64 {
    let mut tmp = [0u8; 8];
    crate::shake::i_shake256_extract(rng, &mut tmp);
    u64::from_le_bytes(tmp)
}

fn mkgauss(rng: &mut InnerShake256Context, logn: u32) -> i32 {
    let g = 1u32 << (10 - logn);
    let mut val: i32 = 0;
    for _ in 0..g {
        let mut r = get_rng_u64(rng);
        let neg = (r >> 63) as u32;
        r &= !(1u64 << 63);
        let f_init = ((r.wrapping_sub(GAUSS_1024_12289[0])) >> 63) as u32;

        let mut v: u32 = 0;
        let mut r2 = get_rng_u64(rng);
        r2 &= !(1u64 << 63);
        let mut f = f_init;
        for k in 1..GAUSS_1024_12289.len() {
            let t = (((r2.wrapping_sub(GAUSS_1024_12289[k])) >> 63) as u32) ^ 1;
            v |= (k as u32) & (t & (f ^ 1)).wrapping_neg();
            f |= t;
        }

        v = (v ^ neg.wrapping_neg()).wrapping_add(neg);
        val += v as i32;
    }
    val
}

fn poly_small_mkgauss(rng: &mut InnerShake256Context, f: &mut [i8], logn: u32) {
    let n: usize = 1 << logn;
    let mut mod2: u32 = 0;
    for u in 0..n {
        loop {
            let s = mkgauss(rng, logn);
            if s < -127 || s > 127 {
                continue;
            }
            if u == n - 1 {
                if (mod2 ^ (s as u32 & 1)) == 0 {
                    continue;
                }
            } else {
                mod2 ^= s as u32 & 1;
            }
            f[u] = s as i8;
            break;
        }
    }
}

// ======================================================================
// NTRU solver stubs and main keygen
// (Full NTRU solver implementation is complex; providing the main
//  keygen entry point and solver framework)
// ======================================================================

fn make_fg(data: &mut [u32], f: &[i8], g: &[i8], logn: u32, depth: u32, out_ntt: bool) {
    let n: usize = 1 << logn;
    let p0 = PRIMES[0].p;
    for u in 0..n {
        data[u] = modp_set(f[u] as i32, p0);
        data[n + u] = modp_set(g[u] as i32, p0);
    }
    if depth == 0 && out_ntt {
        let p = PRIMES[0].p;
        let p0i = modp_ninv31(p);
        let mut gm = vec![0u32; n];
        let mut igm = vec![0u32; n];
        modp_mkgm2(&mut gm, &mut igm, logn, PRIMES[0].g, p, p0i);
        modp_ntt2(&mut data[..n], &gm, logn, p, p0i);
        modp_ntt2(&mut data[n..2 * n], &gm, logn, p, p0i);
        return;
    }
    for d in 0..depth {
        make_fg_step(data, logn - d, d, d != 0, (d + 1) < depth || out_ntt);
    }
}

fn make_fg_step(data: &mut [u32], logn: u32, depth: u32, in_ntt: bool, out_ntt: bool) {
    let n: usize = 1 << logn;
    let hn = n >> 1;
    let slen = MAX_BL_SMALL[depth as usize];
    let tlen = MAX_BL_SMALL[(depth + 1) as usize];

    // This function operates in-place on data[] with complex memory layout.
    // For brevity, we use heap allocation for intermediate buffers.
    let mut fs = vec![0u32; 2 * n * slen];
    fs.copy_from_slice(&data[..2 * n * slen]);

    let mut fd = vec![0u32; hn * tlen];
    let mut gd = vec![0u32; hn * tlen];
    let mut gm_buf = vec![0u32; n];
    let mut igm_buf = vec![0u32; n];
    let mut t1 = vec![0u32; core::cmp::max(n, slen)];

    for u in 0..slen {
        let p = PRIMES[u].p;
        let p0i = modp_ninv31(p);
        let r2 = modp_r2(p, p0i);
        modp_mkgm2(&mut gm_buf, &mut igm_buf, logn, PRIMES[u].g, p, p0i);

        // Extract f column u from fs
        for v in 0..n {
            t1[v] = fs[v * slen + u];
        }
        if !in_ntt {
            modp_ntt2(&mut t1, &gm_buf, logn, p, p0i);
        }
        for v in 0..hn {
            let w0 = t1[(v << 1) + 0];
            let w1 = t1[(v << 1) + 1];
            fd[v * tlen + u] = modp_montymul(modp_montymul(w0, w1, p, p0i), r2, p, p0i);
        }
        if in_ntt {
            // de-NTT the fs column
            for v in 0..n {
                t1[v] = fs[v * slen + u];
            }
            modp_intt2(&mut t1, &igm_buf, logn, p, p0i);
            for v in 0..n {
                fs[v * slen + u] = t1[v];
            }
        }

        // Extract g column u from fs (second half)
        let g_base = n * slen;
        for v in 0..n {
            t1[v] = fs[g_base + v * slen + u];
        }
        if !in_ntt {
            modp_ntt2(&mut t1, &gm_buf, logn, p, p0i);
        }
        for v in 0..hn {
            let w0 = t1[(v << 1) + 0];
            let w1 = t1[(v << 1) + 1];
            gd[v * tlen + u] = modp_montymul(modp_montymul(w0, w1, p, p0i), r2, p, p0i);
        }
        if in_ntt {
            for v in 0..n {
                t1[v] = fs[g_base + v * slen + u];
            }
            modp_intt2(&mut t1, &igm_buf, logn, p, p0i);
            for v in 0..n {
                fs[g_base + v * slen + u] = t1[v];
            }
        }

        if !out_ntt {
            // de-NTT fd and gd columns
            for v in 0..hn {
                t1[v] = fd[v * tlen + u];
            }
            modp_intt2(&mut t1[..hn], &igm_buf, logn - 1, p, p0i);
            for v in 0..hn {
                fd[v * tlen + u] = t1[v];
            }

            for v in 0..hn {
                t1[v] = gd[v * tlen + u];
            }
            modp_intt2(&mut t1[..hn], &igm_buf, logn - 1, p, p0i);
            for v in 0..hn {
                gd[v * tlen + u] = t1[v];
            }
        }
    }

    // CRT rebuild
    zint_rebuild_crt(&mut fs[..n * slen], slen, slen, n, &PRIMES, true, &mut t1);
    zint_rebuild_crt(&mut fs[n * slen..], slen, slen, n, &PRIMES, true, &mut t1);

    // Remaining words: modular reductions
    for u in slen..tlen {
        let p = PRIMES[u].p;
        let p0i = modp_ninv31(p);
        let r2 = modp_r2(p, p0i);
        let rx = modp_rx(slen as u32, p, p0i, r2);
        modp_mkgm2(&mut gm_buf, &mut igm_buf, logn, PRIMES[u].g, p, p0i);

        for v in 0..n {
            t1[v] = zint_mod_small_signed(&fs[v * slen..], slen, p, p0i, r2, rx);
        }
        modp_ntt2(&mut t1, &gm_buf, logn, p, p0i);
        for v in 0..hn {
            let w0 = t1[(v << 1) + 0];
            let w1 = t1[(v << 1) + 1];
            fd[v * tlen + u] = modp_montymul(modp_montymul(w0, w1, p, p0i), r2, p, p0i);
        }

        let g_base = n * slen;
        for v in 0..n {
            t1[v] = zint_mod_small_signed(&fs[g_base + v * slen..], slen, p, p0i, r2, rx);
        }
        modp_ntt2(&mut t1, &gm_buf, logn, p, p0i);
        for v in 0..hn {
            let w0 = t1[(v << 1) + 0];
            let w1 = t1[(v << 1) + 1];
            gd[v * tlen + u] = modp_montymul(modp_montymul(w0, w1, p, p0i), r2, p, p0i);
        }

        if !out_ntt {
            for v in 0..hn {
                t1[v] = fd[v * tlen + u];
            }
            modp_intt2(&mut t1[..hn], &igm_buf, logn - 1, p, p0i);
            for v in 0..hn {
                fd[v * tlen + u] = t1[v];
            }

            for v in 0..hn {
                t1[v] = gd[v * tlen + u];
            }
            modp_intt2(&mut t1[..hn], &igm_buf, logn - 1, p, p0i);
            for v in 0..hn {
                gd[v * tlen + u] = t1[v];
            }
        }
    }

    // Write results back
    let out_len = hn * tlen;
    data[..out_len].copy_from_slice(&fd);
    data[out_len..2 * out_len].copy_from_slice(&gd);
}

fn poly_sub_scaled(
    f_data: &mut [u32],
    flen: usize,
    fstride: usize,
    f_src: &[u32],
    flen_src: usize,
    fstride_src: usize,
    k: &[i32],
    sch: u32,
    scl: u32,
    logn: u32,
) {
    let n: usize = 1 << logn;
    for u in 0..n {
        let mut kf = -k[u];
        let mut x_off = u * fstride;
        let mut y_off = 0usize;
        for v in 0..n {
            zint_add_scaled_mul_small(
                &mut f_data[x_off..],
                flen,
                &f_src[y_off..],
                flen_src,
                kf,
                sch,
                scl,
            );
            if u + v == n - 1 {
                x_off = 0;
                kf = -kf;
            } else {
                x_off += fstride;
            }
            y_off += fstride_src;
        }
    }
}

fn poly_sub_scaled_ntt(
    f_data: &mut [u32],
    flen: usize,
    fstride: usize,
    f_src: &[u32],
    flen_src: usize,
    fstride_src: usize,
    k: &[i32],
    sch: u32,
    scl: u32,
    logn: u32,
    tmp: &mut [u32],
) {
    let n: usize = 1 << logn;
    let tlen = flen_src + 1;

    // Layout in tmp: gm[n] igm[n] fk[n*tlen] t1[n]
    let _gm_off = 0;
    let _igm_off = n;
    let fk_off = 2 * n;
    let t1_off = fk_off + n * tlen;

    for u in 0..tlen {
        let p = PRIMES[u].p;
        let p0i = modp_ninv31(p);
        let r2 = modp_r2(p, p0i);
        let rx = modp_rx(flen_src as u32, p, p0i, r2);
        {
            let (gm_s, rest) = tmp.split_at_mut(n);
            let igm_s = &mut rest[..n];
            modp_mkgm2(gm_s, igm_s, logn, PRIMES[u].g, p, p0i);
        }

        // Set t1 to k modulo p
        for v in 0..n {
            tmp[t1_off + v] = modp_set(k[v], p);
        }
        {
            let (gm_part, rest) = tmp.split_at_mut(n);
            modp_ntt2(&mut rest[t1_off - n..t1_off - n + n], gm_part, logn, p, p0i);
        }

        // Reduce f_src into fk
        for v in 0..n {
            tmp[fk_off + v * tlen + u] =
                zint_mod_small_signed(&f_src[v * fstride_src..], flen_src, p, p0i, r2, rx);
        }

        // NTT of fk column
        {
            let (gm_part, rest) = tmp.split_at_mut(n);
            modp_ntt2_ext(&mut rest[fk_off - n + u..], tlen, gm_part, logn, p, p0i);
        }

        // Pointwise multiply
        for v in 0..n {
            let t1_val = tmp[t1_off + v];
            let fk_val = tmp[fk_off + v * tlen + u];
            tmp[fk_off + v * tlen + u] =
                modp_montymul(modp_montymul(t1_val, fk_val, p, p0i), r2, p, p0i);
        }

        // Inverse NTT
        {
            let (_, rest) = tmp.split_at_mut(n);
            let igm_s = rest[..n].to_vec();
            modp_intt2_ext(&mut rest[fk_off - n + u..], tlen, &igm_s, logn, p, p0i);
        }
    }

    // Rebuild CRT
    {
        let mut t1_buf = vec![0u32; n + tlen];
        zint_rebuild_crt(
            &mut tmp[fk_off..],
            tlen,
            tlen,
            n,
            &PRIMES,
            true,
            &mut t1_buf,
        );
    }

    // Subtract scaled
    for u in 0..n {
        zint_sub_scaled(
            &mut f_data[u * fstride..],
            flen,
            &tmp[fk_off + u * tlen..],
            tlen,
            sch,
            scl,
        );
    }
}

fn solve_ntru_deepest(logn_top: u32, f: &[i8], g: &[i8], tmp: &mut [u32]) -> bool {
    let len = MAX_BL_SMALL[logn_top as usize];

    // Layout: Fp[len] Gp[len] fp[len] gp[len] t1[...]
    let mut buf = vec![0u32; 5 * len + 2 * (1 << logn_top)];
    make_fg(&mut buf[2 * len..], f, g, logn_top, logn_top, false);

    // CRT rebuild
    let mut t1 = vec![0u32; len + 1];
    zint_rebuild_crt(&mut buf[2 * len..], len, len, 2, &PRIMES, false, &mut t1);

    // Binary GCD
    let mut fp = vec![0u32; len];
    let mut gp = vec![0u32; len];
    fp.copy_from_slice(&buf[2 * len..3 * len]);
    gp.copy_from_slice(&buf[3 * len..4 * len]);

    let fp_ref = fp.clone();
    let gp_ref = gp.clone();
    let mut u_buf = vec![0u32; len]; // Gp
    let mut v_buf = vec![0u32; len]; // Fp
    let mut bez_tmp = vec![0u32; 4 * len];

    if !zint_bezout(&mut u_buf, &mut v_buf, &fp_ref, &gp_ref, len, &mut bez_tmp) {
        return false;
    }

    // Multiply by q = 12289
    if zint_mul_small(&mut v_buf, len, 12289) != 0 {
        return false;
    }
    if zint_mul_small(&mut u_buf, len, 12289) != 0 {
        return false;
    }

    // Store Fp, Gp in tmp
    tmp[..len].copy_from_slice(&v_buf);
    tmp[len..2 * len].copy_from_slice(&u_buf);
    true
}

fn solve_ntru_intermediate(logn_top: u32, f: &[i8], g: &[i8], depth: u32, tmp: &mut [u32]) -> bool {
    let logn = logn_top - depth;
    let n: usize = 1 << logn;
    let hn = n >> 1;

    let slen = MAX_BL_SMALL[depth as usize];
    let dlen = MAX_BL_SMALL[(depth + 1) as usize];
    let llen = MAX_BL_LARGE[depth as usize];

    // Save Fd, Gd from tmp
    let fd_gd_len = 2 * hn * dlen;
    let mut fd_gd = vec![0u32; fd_gd_len];
    fd_gd.copy_from_slice(&tmp[..fd_gd_len]);

    // Compute f, g at this depth
    let n_top: usize = 1 << logn_top;
    let fg_step_size = 2 * n * slen + 4 * n;
    let fg_init_size = 2 * n_top;
    let mut fg_buf = vec![0u32; core::cmp::max(fg_step_size, fg_init_size)];
    make_fg(&mut fg_buf, f, g, logn_top, depth, true);

    // Working arrays
    let mut ft_buf = vec![0u32; n * llen]; // for F
    let mut gt_buf = vec![0u32; n * llen]; // for G

    // Reduce Fd, Gd modulo small primes into Ft, Gt
    for u in 0..llen {
        let p = PRIMES[u].p;
        let p0i = modp_ninv31(p);
        let r2 = modp_r2(p, p0i);
        let rx = modp_rx(dlen as u32, p, p0i, r2);
        for v in 0..hn {
            ft_buf[v * llen + u] = zint_mod_small_signed(&fd_gd[v * dlen..], dlen, p, p0i, r2, rx);
            gt_buf[v * llen + u] =
                zint_mod_small_signed(&fd_gd[hn * dlen + v * dlen..], dlen, p, p0i, r2, rx);
        }
    }

    // Compute F and G modulo small primes
    let mut fg_rns = fg_buf.clone(); // f,g in RNS
    for u in 0..llen {
        let p = PRIMES[u].p;
        let p0i = modp_ninv31(p);
        let r2 = modp_r2(p, p0i);

        if u == slen {
            let mut crt_tmp = vec![0u32; n + slen];
            zint_rebuild_crt(
                &mut fg_rns[..n * slen],
                slen,
                slen,
                n,
                &PRIMES,
                true,
                &mut crt_tmp,
            );
            zint_rebuild_crt(
                &mut fg_rns[n * slen..],
                slen,
                slen,
                n,
                &PRIMES,
                true,
                &mut crt_tmp,
            );
        }

        let mut gm = vec![0u32; n];
        let mut igm = vec![0u32; n];
        modp_mkgm2(&mut gm, &mut igm, logn, PRIMES[u].g, p, p0i);

        let mut fx = vec![0u32; n];
        let mut gx = vec![0u32; n];

        if u < slen {
            for v in 0..n {
                fx[v] = fg_rns[v * slen + u];
                gx[v] = fg_rns[n * slen + v * slen + u];
            }
            // De-NTT the column in fg_rns
            let mut col_f = vec![0u32; n];
            let mut col_g = vec![0u32; n];
            for v in 0..n {
                col_f[v] = fg_rns[v * slen + u];
            }
            for v in 0..n {
                col_g[v] = fg_rns[n * slen + v * slen + u];
            }
            modp_intt2(&mut col_f, &igm, logn, p, p0i);
            modp_intt2(&mut col_g, &igm, logn, p, p0i);
            for v in 0..n {
                fg_rns[v * slen + u] = col_f[v];
            }
            for v in 0..n {
                fg_rns[n * slen + v * slen + u] = col_g[v];
            }
        } else {
            let rx = modp_rx(slen as u32, p, p0i, r2);
            for v in 0..n {
                fx[v] = zint_mod_small_signed(&fg_rns[v * slen..], slen, p, p0i, r2, rx);
                gx[v] = zint_mod_small_signed(&fg_rns[n * slen + v * slen..], slen, p, p0i, r2, rx);
            }
            modp_ntt2(&mut fx, &gm, logn, p, p0i);
            modp_ntt2(&mut gx, &gm, logn, p, p0i);
        }

        // Get Fp, Gp from Ft, Gt
        let mut fp_arr = vec![0u32; hn];
        let mut gp_arr = vec![0u32; hn];
        for v in 0..hn {
            fp_arr[v] = ft_buf[v * llen + u];
            gp_arr[v] = gt_buf[v * llen + u];
        }
        modp_ntt2(&mut fp_arr, &gm, logn - 1, p, p0i);
        modp_ntt2(&mut gp_arr, &gm, logn - 1, p, p0i);

        // Compute F and G: F = F'(x^2) * adj(g), G = G'(x^2) * adj(f)
        for v in 0..hn {
            let ft_a = fx[(v << 1) + 0];
            let ft_b = fx[(v << 1) + 1];
            let gt_a = gx[(v << 1) + 0];
            let gt_b = gx[(v << 1) + 1];
            let m_fp = modp_montymul(fp_arr[v], r2, p, p0i);
            let m_gp = modp_montymul(gp_arr[v], r2, p, p0i);
            ft_buf[v * 2 * llen + u] = modp_montymul(gt_b, m_fp, p, p0i);
            ft_buf[(v * 2 + 1) * llen + u] = modp_montymul(gt_a, m_fp, p, p0i);
            gt_buf[v * 2 * llen + u] = modp_montymul(ft_b, m_gp, p, p0i);
            gt_buf[(v * 2 + 1) * llen + u] = modp_montymul(ft_a, m_gp, p, p0i);
        }

        // Inverse NTT on Ft, Gt columns
        let mut col = vec![0u32; n];
        for v in 0..n {
            col[v] = ft_buf[v * llen + u];
        }
        modp_intt2(&mut col, &igm, logn, p, p0i);
        for v in 0..n {
            ft_buf[v * llen + u] = col[v];
        }

        for v in 0..n {
            col[v] = gt_buf[v * llen + u];
        }
        modp_intt2(&mut col, &igm, logn, p, p0i);
        for v in 0..n {
            gt_buf[v * llen + u] = col[v];
        }
    }

    // Rebuild CRT for F and G
    {
        let mut crt_tmp = vec![0u32; n + llen];
        zint_rebuild_crt(&mut ft_buf, llen, llen, n, &PRIMES, true, &mut crt_tmp);
        zint_rebuild_crt(&mut gt_buf, llen, llen, n, &PRIMES, true, &mut crt_tmp);
    }

    // Rebuild CRT for f, g if not done yet
    if slen >= llen {
        let mut crt_tmp = vec![0u32; n + slen];
        zint_rebuild_crt(
            &mut fg_rns[..n * slen],
            slen,
            slen,
            n,
            &PRIMES,
            true,
            &mut crt_tmp,
        );
        zint_rebuild_crt(
            &mut fg_rns[n * slen..],
            slen,
            slen,
            n,
            &PRIMES,
            true,
            &mut crt_tmp,
        );
    }

    // Babai reduction
    let rlen = if slen > 10 { 10 } else { slen };
    let scale_fg = 31 * (slen as i32 - rlen as i32);

    let mut rt3 = vec![FPR_ZERO; n];
    let mut rt4 = vec![FPR_ZERO; n];
    let mut rt5 = vec![FPR_ZERO; n]; // only n/2 used

    // Convert f, g to FP
    poly_big_to_fp(&mut rt3, &fg_rns[slen - rlen..], rlen, slen, logn);
    poly_big_to_fp(
        &mut rt4,
        &fg_rns[n * slen + slen - rlen..],
        rlen,
        slen,
        logn,
    );

    let minbl_fg = BITLENGTH[depth as usize].avg - 6 * BITLENGTH[depth as usize].std;
    let maxbl_fg = BITLENGTH[depth as usize].avg + 6 * BITLENGTH[depth as usize].std;

    fft::fft(&mut rt3, logn);
    fft::fft(&mut rt4, logn);
    fft::poly_invnorm2_fft(&mut rt5, &rt3, &rt4, logn);
    fft::poly_adj_fft(&mut rt3, logn);
    fft::poly_adj_fft(&mut rt4, logn);

    let mut fg_len = llen;
    let mut maxbl_fg_val = 31 * llen as i32;
    let mut scale_k = maxbl_fg_val - minbl_fg;

    loop {
        let rlen2 = if fg_len > 10 { 10 } else { fg_len };
        let scale_fg2 = 31 * (fg_len as i32 - rlen2 as i32);

        let mut rt1 = vec![FPR_ZERO; n];
        let mut rt2 = vec![FPR_ZERO; n];

        poly_big_to_fp(&mut rt1, &ft_buf[fg_len - rlen2..], rlen2, llen, logn);
        poly_big_to_fp(&mut rt2, &gt_buf[fg_len - rlen2..], rlen2, llen, logn);

        fft::fft(&mut rt1, logn);
        fft::fft(&mut rt2, logn);
        fft::poly_mul_fft(&mut rt1, &rt3, logn);
        fft::poly_mul_fft(&mut rt2, &rt4, logn);
        fft::poly_add(&mut rt2, &rt1, logn);
        fft::poly_mul_autoadj_fft(&mut rt2, &rt5, logn);
        fft::ifft(&mut rt2, logn);

        // Compute scaling factor
        let mut dc = scale_k - scale_fg2 + scale_fg;
        let pt_base;
        if dc < 0 {
            dc = -dc;
            pt_base = FPR_TWO;
        } else {
            pt_base = FPR_ONEHALF;
        }
        let mut pdc = FPR_ONE;
        let mut pt = pt_base;
        let mut dcc = dc;
        while dcc != 0 {
            if (dcc & 1) != 0 {
                pdc = fpr_mul(pdc, pt);
            }
            dcc >>= 1;
            pt = fpr_sqr(pt);
        }

        let mut k_arr = vec![0i32; n];
        for u in 0..n {
            let xv = fpr_mul(rt2[u], pdc);
            if fpr_lt(FPR_MTWO31M1, xv) == 0 || fpr_lt(xv, FPR_PTWO31M1) == 0 {
                return false;
            }
            k_arr[u] = fpr_rint(xv) as i32;
        }

        let sch = (scale_k / 31) as u32;
        let scl = (scale_k % 31) as u32;

        if depth <= DEPTH_INT_FG {
            let mut sub_tmp = vec![0u32; 4 * n + 2 * n * (slen + 1)];
            poly_sub_scaled_ntt(
                &mut ft_buf,
                fg_len,
                llen,
                &fg_rns[..n * slen],
                slen,
                slen,
                &k_arr,
                sch,
                scl,
                logn,
                &mut sub_tmp,
            );
            poly_sub_scaled_ntt(
                &mut gt_buf,
                fg_len,
                llen,
                &fg_rns[n * slen..],
                slen,
                slen,
                &k_arr,
                sch,
                scl,
                logn,
                &mut sub_tmp,
            );
        } else {
            poly_sub_scaled(
                &mut ft_buf,
                fg_len,
                llen,
                &fg_rns[..n * slen],
                slen,
                slen,
                &k_arr,
                sch,
                scl,
                logn,
            );
            poly_sub_scaled(
                &mut gt_buf,
                fg_len,
                llen,
                &fg_rns[n * slen..],
                slen,
                slen,
                &k_arr,
                sch,
                scl,
                logn,
            );
        }

        let new_maxbl_fg = scale_k + maxbl_fg + 10;
        if new_maxbl_fg < maxbl_fg_val {
            maxbl_fg_val = new_maxbl_fg;
            if (fg_len as i32) * 31 >= maxbl_fg_val + 31 {
                fg_len -= 1;
            }
        }

        if scale_k <= 0 {
            break;
        }
        scale_k -= 25;
        if scale_k < 0 {
            scale_k = 0;
        }
    }

    // Sign-extend if FGlen < slen
    if fg_len < slen {
        for u in 0..n {
            let sw_f = (ft_buf[u * llen + fg_len - 1] >> 30).wrapping_neg() >> 1;
            for v in fg_len..slen {
                ft_buf[u * llen + v] = sw_f;
            }
            let sw_g = (gt_buf[u * llen + fg_len - 1] >> 30).wrapping_neg() >> 1;
            for v in fg_len..slen {
                gt_buf[u * llen + v] = sw_g;
            }
        }
    }

    // Compress to slen stride and write to tmp
    for u in 0..n {
        tmp[u * slen..u * slen + slen].copy_from_slice(&ft_buf[u * llen..u * llen + slen]);
    }
    for u in 0..n {
        tmp[n * slen + u * slen..n * slen + u * slen + slen]
            .copy_from_slice(&gt_buf[u * llen..u * llen + slen]);
    }

    true
}

fn solve_ntru_binary_depth1(logn_top: u32, f: &[i8], g: &[i8], tmp: &mut [u32]) -> bool {
    let depth: u32 = 1;
    let n_top: usize = 1 << logn_top;
    let logn = logn_top - depth;
    let n: usize = 1 << logn;
    let hn = n >> 1;

    let slen = MAX_BL_SMALL[depth as usize];
    let dlen = MAX_BL_SMALL[(depth + 1) as usize];
    let llen = MAX_BL_LARGE[depth as usize];

    // Save Fd, Gd from tmp
    let mut fd = vec![0u32; hn * dlen];
    let mut gd = vec![0u32; hn * dlen];
    fd.copy_from_slice(&tmp[..hn * dlen]);
    gd.copy_from_slice(&tmp[hn * dlen..2 * hn * dlen]);

    // Reduce Fd, Gd modulo primes into Ft, Gt
    let mut ft_buf = vec![0u32; n * llen];
    let mut gt_buf = vec![0u32; n * llen];

    for u in 0..llen {
        let p = PRIMES[u].p;
        let p0i = modp_ninv31(p);
        let r2 = modp_r2(p, p0i);
        let rx = modp_rx(dlen as u32, p, p0i, r2);
        for v in 0..hn {
            ft_buf[v * llen + u] = zint_mod_small_signed(&fd[v * dlen..], dlen, p, p0i, r2, rx);
            gt_buf[v * llen + u] = zint_mod_small_signed(&gd[v * dlen..], dlen, p, p0i, r2, rx);
        }
    }

    let mut ft_rns = vec![0u32; n * slen];
    let mut gt_rns = vec![0u32; n * slen];

    // Compute F, G modulo primes
    for u in 0..llen {
        let p = PRIMES[u].p;
        let p0i = modp_ninv31(p);
        let r2 = modp_r2(p, p0i);

        let mut gm = vec![0u32; n_top];
        let mut igm = vec![0u32; n_top];
        modp_mkgm2(&mut gm, &mut igm, logn_top, PRIMES[u].g, p, p0i);

        let mut fx = vec![0u32; n_top];
        let mut gx = vec![0u32; n_top];
        for v in 0..n_top {
            fx[v] = modp_set(f[v] as i32, p);
            gx[v] = modp_set(g[v] as i32, p);
        }
        modp_ntt2(&mut fx, &gm, logn_top, p, p0i);
        modp_ntt2(&mut gx, &gm, logn_top, p, p0i);

        let mut e = logn_top;
        while e > logn {
            modp_poly_rec_res(&mut fx, e, p, p0i, r2);
            modp_poly_rec_res(&mut gx, e, p, p0i, r2);
            e -= 1;
        }

        // Re-arrange memory: shrink gm/igm to size n
        let igm_n = igm[..n].to_vec();
        let fx_n = fx[..n].to_vec();
        let gx_n = gx[..n].to_vec();
        let mut fx_work = fx_n;
        let mut gx_work = gx_n;

        // Get Fp, Gp
        let mut fp_arr = vec![0u32; hn];
        let mut gp_arr = vec![0u32; hn];
        for v in 0..hn {
            fp_arr[v] = ft_buf[v * llen + u];
            gp_arr[v] = gt_buf[v * llen + u];
        }
        modp_ntt2(&mut fp_arr, &gm, logn - 1, p, p0i);
        modp_ntt2(&mut gp_arr, &gm, logn - 1, p, p0i);

        // Compute F and G
        for v in 0..hn {
            let ft_a = fx_work[(v << 1) + 0];
            let ft_b = fx_work[(v << 1) + 1];
            let gt_a = gx_work[(v << 1) + 0];
            let gt_b = gx_work[(v << 1) + 1];
            let m_fp = modp_montymul(fp_arr[v], r2, p, p0i);
            let m_gp = modp_montymul(gp_arr[v], r2, p, p0i);
            ft_buf[v * 2 * llen + u] = modp_montymul(gt_b, m_fp, p, p0i);
            ft_buf[(v * 2 + 1) * llen + u] = modp_montymul(gt_a, m_fp, p, p0i);
            gt_buf[v * 2 * llen + u] = modp_montymul(ft_b, m_gp, p, p0i);
            gt_buf[(v * 2 + 1) * llen + u] = modp_montymul(ft_a, m_gp, p, p0i);
        }

        // iNTT columns of Ft, Gt
        let mut col = vec![0u32; n];
        for v in 0..n {
            col[v] = ft_buf[v * llen + u];
        }
        modp_intt2(&mut col, &igm_n, logn, p, p0i);
        for v in 0..n {
            ft_buf[v * llen + u] = col[v];
        }

        for v in 0..n {
            col[v] = gt_buf[v * llen + u];
        }
        modp_intt2(&mut col, &igm_n, logn, p, p0i);
        for v in 0..n {
            gt_buf[v * llen + u] = col[v];
        }

        // Save f, g RNS
        if u < slen {
            modp_intt2(&mut fx_work, &igm_n, logn, p, p0i);
            modp_intt2(&mut gx_work, &igm_n, logn, p, p0i);
            for v in 0..n {
                ft_rns[v * slen + u] = fx_work[v];
                gt_rns[v * slen + u] = gx_work[v];
            }
        }
    }

    // Rebuild CRT for F and G (separately since they're not contiguous)
    {
        let mut crt_tmp = vec![0u32; 2 * n + llen];
        zint_rebuild_crt(&mut ft_buf, llen, llen, n, &PRIMES, true, &mut crt_tmp);
        zint_rebuild_crt(&mut gt_buf, llen, llen, n, &PRIMES, true, &mut crt_tmp);
    }
    {
        let mut crt_tmp = vec![0u32; 2 * n + slen];
        // ft_rns and gt_rns together
        let mut fg_combined = vec![0u32; 2 * n * slen];
        fg_combined[..n * slen].copy_from_slice(&ft_rns);
        fg_combined[n * slen..].copy_from_slice(&gt_rns);
        zint_rebuild_crt(
            &mut fg_combined,
            slen,
            slen,
            n << 1,
            &PRIMES,
            true,
            &mut crt_tmp,
        );
        ft_rns.copy_from_slice(&fg_combined[..n * slen]);
        gt_rns.copy_from_slice(&fg_combined[n * slen..]);
    }

    // Babai reduction (simplified for depth 1, single pass)
    let mut rt1 = vec![FPR_ZERO; n];
    let mut rt2 = vec![FPR_ZERO; n];
    poly_big_to_fp(&mut rt1, &ft_buf, llen, llen, logn);
    poly_big_to_fp(&mut rt2, &gt_buf, llen, llen, logn);

    let mut rt3 = vec![FPR_ZERO; n];
    let mut rt4 = vec![FPR_ZERO; n];
    poly_big_to_fp(&mut rt3, &ft_rns, slen, slen, logn);
    poly_big_to_fp(&mut rt4, &gt_rns, slen, slen, logn);

    fft::fft(&mut rt1, logn);
    fft::fft(&mut rt2, logn);
    fft::fft(&mut rt3, logn);
    fft::fft(&mut rt4, logn);

    let mut rt5 = vec![FPR_ZERO; n];
    let mut rt6 = vec![FPR_ZERO; n];
    fft::poly_add_muladj_fft(&mut rt5, &rt1, &rt2, &rt3, &rt4, logn);
    fft::poly_invnorm2_fft(&mut rt6, &rt3, &rt4, logn);
    fft::poly_mul_autoadj_fft(&mut rt5, &rt6, logn);

    fft::ifft(&mut rt5, logn);
    for u in 0..n {
        let z = rt5[u];
        if fpr_lt(z, FPR_PTWO63M1) == 0 || fpr_lt(FPR_MTWO63M1, z) == 0 {
            return false;
        }
        rt5[u] = fpr_of(fpr_rint(z));
    }
    fft::fft(&mut rt5, logn);

    fft::poly_mul_fft(&mut rt3, &rt5, logn);
    fft::poly_mul_fft(&mut rt4, &rt5, logn);
    fft::poly_sub(&mut rt1, &rt3, logn);
    fft::poly_sub(&mut rt2, &rt4, logn);
    fft::ifft(&mut rt1, logn);
    fft::ifft(&mut rt2, logn);

    // Convert back to integers
    for u in 0..n {
        tmp[u] = fpr_rint(rt1[u]) as u32;
    }
    for u in 0..n {
        tmp[n + u] = fpr_rint(rt2[u]) as u32;
    }

    true
}

fn solve_ntru_binary_depth0(logn: u32, f: &[i8], g: &[i8], tmp: &mut [u32]) -> bool {
    let n: usize = 1 << logn;
    let hn = n >> 1;

    let p = PRIMES[0].p;
    let p0i = modp_ninv31(p);
    let r2 = modp_r2(p, p0i);

    // Layout: Fp[hn] Gp[hn] ft[n] gt[n] gm[n] igm[n]
    // Fp and Gp are from tmp (previous level output, 1 word each)
    let mut fp_arr = vec![0u32; hn];
    let mut gp_arr = vec![0u32; hn];
    for u in 0..hn {
        fp_arr[u] = modp_set(zint_one_to_plain(&tmp[u..u + 1]), p);
        gp_arr[u] = modp_set(zint_one_to_plain(&tmp[hn + u..hn + u + 1]), p);
    }

    let mut gm = vec![0u32; n];
    let mut igm = vec![0u32; n];
    modp_mkgm2(&mut gm, &mut igm, logn, PRIMES[0].g, p, p0i);

    modp_ntt2(&mut fp_arr, &gm, logn - 1, p, p0i);
    modp_ntt2(&mut gp_arr, &gm, logn - 1, p, p0i);

    let mut ft = vec![0u32; n];
    let mut gt = vec![0u32; n];
    for u in 0..n {
        ft[u] = modp_set(f[u] as i32, p);
        gt[u] = modp_set(g[u] as i32, p);
    }
    modp_ntt2(&mut ft, &gm, logn, p, p0i);
    modp_ntt2(&mut gt, &gm, logn, p, p0i);

    // Build unreduced F, G
    let mut u = 0;
    while u < n {
        let ft_a = ft[u + 0];
        let ft_b = ft[u + 1];
        let gt_a = gt[u + 0];
        let gt_b = gt[u + 1];
        let m_fp = modp_montymul(fp_arr[u >> 1], r2, p, p0i);
        let m_gp = modp_montymul(gp_arr[u >> 1], r2, p, p0i);
        ft[u + 0] = modp_montymul(gt_b, m_fp, p, p0i);
        ft[u + 1] = modp_montymul(gt_a, m_fp, p, p0i);
        gt[u + 0] = modp_montymul(ft_b, m_gp, p, p0i);
        gt[u + 1] = modp_montymul(ft_a, m_gp, p, p0i);
        u += 2;
    }
    modp_intt2(&mut ft, &igm, logn, p, p0i);
    modp_intt2(&mut gt, &igm, logn, p, p0i);

    // Save F, G (these are the unreduced values)
    let mut fp_full = ft.clone();
    let mut gp_full = gt.clone();

    // Babai reduction using NTT modular arithmetic
    // Compute F*adj(f)+G*adj(g) and f*adj(f)+g*adj(g)
    modp_mkgm2(&mut gm, &mut igm, logn, PRIMES[0].g, p, p0i);

    modp_ntt2(&mut fp_full, &gm, logn, p, p0i);
    modp_ntt2(&mut gp_full, &gm, logn, p, p0i);

    // f and adj(f)
    let mut t4 = vec![0u32; n];
    let mut t5 = vec![0u32; n];
    t4[0] = modp_set(f[0] as i32, p);
    t5[0] = modp_set(f[0] as i32, p);
    for u in 1..n {
        t4[u] = modp_set(f[u] as i32, p);
        t5[n - u] = modp_set(-(f[u] as i32), p);
    }
    modp_ntt2(&mut t4, &gm, logn, p, p0i);
    modp_ntt2(&mut t5, &gm, logn, p, p0i);

    let mut t2 = vec![0u32; n]; // F*adj(f)
    let mut t3 = vec![0u32; n]; // f*adj(f)
    for u in 0..n {
        let w = modp_montymul(t5[u], r2, p, p0i);
        t2[u] = modp_montymul(w, fp_full[u], p, p0i);
        t3[u] = modp_montymul(w, t4[u], p, p0i);
    }

    // g and adj(g)
    t4[0] = modp_set(g[0] as i32, p);
    t5[0] = modp_set(g[0] as i32, p);
    for u in 1..n {
        t4[u] = modp_set(g[u] as i32, p);
        t5[n - u] = modp_set(-(g[u] as i32), p);
    }
    modp_ntt2(&mut t4, &gm, logn, p, p0i);
    modp_ntt2(&mut t5, &gm, logn, p, p0i);

    for u in 0..n {
        let w = modp_montymul(t5[u], r2, p, p0i);
        t2[u] = modp_add(t2[u], modp_montymul(w, gp_full[u], p, p0i), p);
        t3[u] = modp_add(t3[u], modp_montymul(w, t4[u], p, p0i), p);
    }

    // iNTT t2, t3
    modp_mkgm2(&mut gm, &mut igm, logn, PRIMES[0].g, p, p0i);
    modp_intt2(&mut t2, &igm, logn, p, p0i);
    modp_intt2(&mut t3, &igm, logn, p, p0i);

    let mut t1_norm = vec![0i32; n];
    let mut t2_norm = vec![0i32; n];
    for u in 0..n {
        t1_norm[u] = modp_norm(t2[u], p);
        t2_norm[u] = modp_norm(t3[u], p);
    }

    // FFT-based division
    let mut rt3 = vec![FPR_ZERO; n];
    for u in 0..n {
        rt3[u] = fpr_of(t2_norm[u] as i64);
    }
    fft::fft(&mut rt3, logn);
    let rt2_half: Vec<Fpr> = rt3[..hn].to_vec();

    let mut rt3b = vec![FPR_ZERO; n];
    for u in 0..n {
        rt3b[u] = fpr_of(t1_norm[u] as i64);
    }
    fft::fft(&mut rt3b, logn);

    fft::poly_div_autoadj_fft(&mut rt3b, &rt2_half, logn);
    fft::ifft(&mut rt3b, logn);

    let mut k_arr = vec![0u32; n];
    for u in 0..n {
        k_arr[u] = modp_set(fpr_rint(rt3b[u]) as i32, p);
    }

    // Subtract k*f from F, k*g from G
    modp_mkgm2(&mut gm, &mut igm, logn, PRIMES[0].g, p, p0i);
    let mut t4f = vec![0u32; n];
    let mut t5g = vec![0u32; n];
    for u in 0..n {
        t4f[u] = modp_set(f[u] as i32, p);
        t5g[u] = modp_set(g[u] as i32, p);
    }
    modp_ntt2(&mut k_arr, &gm, logn, p, p0i);
    modp_ntt2(&mut t4f, &gm, logn, p, p0i);
    modp_ntt2(&mut t5g, &gm, logn, p, p0i);

    for u in 0..n {
        let kw = modp_montymul(k_arr[u], r2, p, p0i);
        fp_full[u] = modp_sub(fp_full[u], modp_montymul(kw, t4f[u], p, p0i), p);
        gp_full[u] = modp_sub(gp_full[u], modp_montymul(kw, t5g[u], p, p0i), p);
    }
    modp_intt2(&mut fp_full, &igm, logn, p, p0i);
    modp_intt2(&mut gp_full, &igm, logn, p, p0i);

    for u in 0..n {
        tmp[u] = modp_norm(fp_full[u], p) as u32;
        tmp[n + u] = modp_norm(gp_full[u], p) as u32;
    }

    true
}

fn solve_ntru(
    logn: u32,
    big_f: &mut [i8],
    big_g: Option<&mut [i8]>,
    f: &[i8],
    g: &[i8],
    lim: i32,
    tmp: &mut [u32],
) -> bool {
    let n: usize = 1 << logn;

    if !solve_ntru_deepest(logn, f, g, tmp) {
        return false;
    }

    if logn <= 2 {
        let mut depth = logn;
        while depth > 0 {
            depth -= 1;
            if !solve_ntru_intermediate(logn, f, g, depth, tmp) {
                return false;
            }
        }
    } else {
        let mut depth = logn;
        while depth > 2 {
            depth -= 1;
            if !solve_ntru_intermediate(logn, f, g, depth, tmp) {
                return false;
            }
        }
        if !solve_ntru_binary_depth1(logn, f, g, tmp) {
            return false;
        }
        if !solve_ntru_binary_depth0(logn, f, g, tmp) {
            return false;
        }
    }

    // Extract results
    let mut g_buf = vec![0i8; n];
    let g_out = big_g.unwrap_or(&mut g_buf);

    if !poly_big_to_small(big_f, tmp, lim, logn) {
        return false;
    }
    if !poly_big_to_small(g_out, &tmp[n..], lim, logn) {
        return false;
    }

    // Verify that f*G - g*F = q (mod p)
    let p = PRIMES[0].p;
    let p0i = modp_ninv31(p);
    let mut gm = vec![0u32; 2 * n];
    let mut gt_v = vec![0u32; n];
    let mut ft_v = vec![0u32; n];
    let mut fv = vec![0u32; n];
    let mut gv = vec![0u32; n];
    let (gm_lo, gm_hi) = gm.split_at_mut(n);
    modp_mkgm2(gm_lo, gm_hi, logn, PRIMES[0].g, p, p0i);

    for u in 0..n {
        gt_v[u] = modp_set(g_out[u] as i32, p);
    }
    for u in 0..n {
        fv[u] = modp_set(f[u] as i32, p);
        gv[u] = modp_set(g[u] as i32, p);
        ft_v[u] = modp_set(big_f[u] as i32, p);
    }
    modp_ntt2(&mut fv, &gm[..n], logn, p, p0i);
    modp_ntt2(&mut gv, &gm[..n], logn, p, p0i);
    modp_ntt2(&mut ft_v, &gm[..n], logn, p, p0i);
    modp_ntt2(&mut gt_v, &gm[..n], logn, p, p0i);

    let r = modp_montymul(12289, 1, p, p0i);
    for u in 0..n {
        let z = modp_sub(
            modp_montymul(fv[u], gt_v[u], p, p0i),
            modp_montymul(gv[u], ft_v[u], p, p0i),
            p,
        );
        if z != r {
            return false;
        }
    }

    true
}

// ======================================================================
// Main key generation entry point
// ======================================================================

/// Generate a Falcon key pair.
///
/// rng: SHAKE256 context (flipped/ready for extraction)
/// f, g: secret key polynomials (output)
/// big_f: NTRU equation solution F (output)
/// big_g: NTRU equation solution G (output, may be None)
/// h: public key (output, may be None)
/// logn: log2 of degree (1..10)
/// tmp: temporary buffer (must be large enough)
pub fn keygen(
    rng: &mut InnerShake256Context,
    f: &mut [i8],
    g: &mut [i8],
    big_f: &mut [i8],
    mut big_g: Option<&mut [i8]>,
    mut h: Option<&mut [u16]>,
    logn: u32,
    tmp: &mut [u8],
) {
    let n: usize = 1 << logn;

    // Use raw pointer to allow reuse of tmp across loop iterations.
    let tmp_ptr = tmp.as_mut_ptr();
    let tmp_len = tmp.len();

    loop {
        // Generate f and g with Gaussian distribution
        // Uses SHAKE256 directly (matching C reference FALCON_KG_CHACHA20=0)
        poly_small_mkgauss(rng, f, logn);
        poly_small_mkgauss(rng, g, logn);

        // Check coefficient bounds
        let lim = 1i32 << (codec::MAX_FG_BITS[logn as usize] - 1);
        let mut bad = false;
        for u in 0..n {
            if f[u] as i32 >= lim
                || (f[u] as i32) <= -lim
                || g[u] as i32 >= lim
                || (g[u] as i32) <= -lim
            {
                bad = true;
                break;
            }
        }
        if bad {
            continue;
        }

        // Check squared norm
        let normf = poly_small_sqnorm(f, logn);
        let normg = poly_small_sqnorm(g, logn);
        let norm = (normf.wrapping_add(normg)) | ((normf | normg) >> 31).wrapping_neg();
        if norm >= 16823 {
            continue;
        }

        // Compute orthogonalized vector norm
        let fpr_tmp: &mut [Fpr] = unsafe {
            core::slice::from_raw_parts_mut(
                tmp_ptr as *mut Fpr,
                tmp_len / core::mem::size_of::<Fpr>(),
            )
        };
        let (rt1, rest) = fpr_tmp.split_at_mut(n);
        let (rt2, rest) = rest.split_at_mut(n);
        let (rt3, _) = rest.split_at_mut(n);

        poly_small_to_fp(rt1, f, logn);
        poly_small_to_fp(rt2, g, logn);
        fft::fft(rt1, logn);
        fft::fft(rt2, logn);
        fft::poly_invnorm2_fft(rt3, rt1, rt2, logn);
        fft::poly_adj_fft(rt1, logn);
        fft::poly_adj_fft(rt2, logn);
        fft::poly_mulconst(rt1, FPR_Q, logn);
        fft::poly_mulconst(rt2, FPR_Q, logn);
        fft::poly_mul_autoadj_fft(rt1, rt3, logn);
        fft::poly_mul_autoadj_fft(rt2, rt3, logn);
        fft::ifft(rt1, logn);
        fft::ifft(rt2, logn);
        let mut bnorm = FPR_ZERO;
        for u in 0..n {
            bnorm = fpr_add(bnorm, fpr_sqr(rt1[u]));
            bnorm = fpr_add(bnorm, fpr_sqr(rt2[u]));
        }
        if fpr_lt(bnorm, FPR_BNORM_MAX) == 0 {
            continue;
        }

        // Compute public key h = g/f mod phi mod q
        let mut h_buf = vec![0u16; n];
        let tmp_slice = unsafe { core::slice::from_raw_parts_mut(tmp_ptr, tmp_len) };
        if !compute_public(&mut h_buf, f, g, logn, tmp_slice) {
            continue;
        }
        if let Some(ref mut hh) = h {
            hh[..n].copy_from_slice(&h_buf[..n]);
        }

        // Solve the NTRU equation
        let lim2 = (1i32 << (codec::MAX_FG_BITS_UPPER[logn as usize] - 1)) - 1;
        let tmp_u32: &mut [u32] =
            unsafe { core::slice::from_raw_parts_mut(tmp_ptr as *mut u32, tmp_len / 4) };
        if !solve_ntru(logn, big_f, big_g.as_deref_mut(), f, g, lim2, tmp_u32) {
            continue;
        }

        break;
    }
}