Skip to main content

falcon/
keygen.rs

1//! Falcon key pair generation.
2//! Ported from keygen.c.
3
4#![allow(clippy::too_many_arguments)]
5
6use alloc::{vec, vec::Vec};
7
8use crate::{codec, fft, fpr::*, shake::InnerShake256Context, vrfy::compute_public};
9
10const DEPTH_INT_FG: u32 = 4;
11
12pub struct SmallPrime {
13    pub p: u32,
14    pub g: u32,
15    pub s: u32,
16}
17
18pub static PRIMES: [SmallPrime; 521] = [
19    SmallPrime {
20        p: 2147473409,
21        g: 383167813,
22        s: 10239,
23    },
24    SmallPrime {
25        p: 2147389441,
26        g: 211808905,
27        s: 471403745,
28    },
29    SmallPrime {
30        p: 2147387393,
31        g: 37672282,
32        s: 1329335065,
33    },
34    SmallPrime {
35        p: 2147377153,
36        g: 1977035326,
37        s: 968223422,
38    },
39    SmallPrime {
40        p: 2147358721,
41        g: 1067163706,
42        s: 132460015,
43    },
44    SmallPrime {
45        p: 2147352577,
46        g: 1606082042,
47        s: 598693809,
48    },
49    SmallPrime {
50        p: 2147346433,
51        g: 2033915641,
52        s: 1056257184,
53    },
54    SmallPrime {
55        p: 2147338241,
56        g: 1653770625,
57        s: 421286710,
58    },
59    SmallPrime {
60        p: 2147309569,
61        g: 631200819,
62        s: 1111201074,
63    },
64    SmallPrime {
65        p: 2147297281,
66        g: 2038364663,
67        s: 1042003613,
68    },
69    SmallPrime {
70        p: 2147295233,
71        g: 1962540515,
72        s: 19440033,
73    },
74    SmallPrime {
75        p: 2147239937,
76        g: 2100082663,
77        s: 353296760,
78    },
79    SmallPrime {
80        p: 2147235841,
81        g: 1991153006,
82        s: 1703918027,
83    },
84    SmallPrime {
85        p: 2147217409,
86        g: 516405114,
87        s: 1258919613,
88    },
89    SmallPrime {
90        p: 2147205121,
91        g: 409347988,
92        s: 1089726929,
93    },
94    SmallPrime {
95        p: 2147196929,
96        g: 927788991,
97        s: 1946238668,
98    },
99    SmallPrime {
100        p: 2147178497,
101        g: 1136922411,
102        s: 1347028164,
103    },
104    SmallPrime {
105        p: 2147100673,
106        g: 868626236,
107        s: 701164723,
108    },
109    SmallPrime {
110        p: 2147082241,
111        g: 1897279176,
112        s: 617820870,
113    },
114    SmallPrime {
115        p: 2147074049,
116        g: 1888819123,
117        s: 158382189,
118    },
119    SmallPrime {
120        p: 2147051521,
121        g: 25006327,
122        s: 522758543,
123    },
124    SmallPrime {
125        p: 2147043329,
126        g: 327546255,
127        s: 37227845,
128    },
129    SmallPrime {
130        p: 2147039233,
131        g: 766324424,
132        s: 1133356428,
133    },
134    SmallPrime {
135        p: 2146988033,
136        g: 1862817362,
137        s: 73861329,
138    },
139    SmallPrime {
140        p: 2146963457,
141        g: 404622040,
142        s: 653019435,
143    },
144    SmallPrime {
145        p: 2146959361,
146        g: 1936581214,
147        s: 995143093,
148    },
149    SmallPrime {
150        p: 2146938881,
151        g: 1559770096,
152        s: 634921513,
153    },
154    SmallPrime {
155        p: 2146908161,
156        g: 422623708,
157        s: 1985060172,
158    },
159    SmallPrime {
160        p: 2146885633,
161        g: 1751189170,
162        s: 298238186,
163    },
164    SmallPrime {
165        p: 2146871297,
166        g: 578919515,
167        s: 291810829,
168    },
169    SmallPrime {
170        p: 2146846721,
171        g: 1114060353,
172        s: 915902322,
173    },
174    SmallPrime {
175        p: 2146834433,
176        g: 2069565474,
177        s: 47859524,
178    },
179    SmallPrime {
180        p: 2146818049,
181        g: 1552824584,
182        s: 646281055,
183    },
184    SmallPrime {
185        p: 2146775041,
186        g: 1906267847,
187        s: 1597832891,
188    },
189    SmallPrime {
190        p: 2146756609,
191        g: 1847414714,
192        s: 1228090888,
193    },
194    SmallPrime {
195        p: 2146744321,
196        g: 1818792070,
197        s: 1176377637,
198    },
199    SmallPrime {
200        p: 2146738177,
201        g: 1118066398,
202        s: 1054971214,
203    },
204    SmallPrime {
205        p: 2146736129,
206        g: 52057278,
207        s: 933422153,
208    },
209    SmallPrime {
210        p: 2146713601,
211        g: 592259376,
212        s: 1406621510,
213    },
214    SmallPrime {
215        p: 2146695169,
216        g: 263161877,
217        s: 1514178701,
218    },
219    SmallPrime {
220        p: 2146656257,
221        g: 685363115,
222        s: 384505091,
223    },
224    SmallPrime {
225        p: 2146650113,
226        g: 927727032,
227        s: 537575289,
228    },
229    SmallPrime {
230        p: 2146646017,
231        g: 52575506,
232        s: 1799464037,
233    },
234    SmallPrime {
235        p: 2146643969,
236        g: 1276803876,
237        s: 1348954416,
238    },
239    SmallPrime {
240        p: 2146603009,
241        g: 814028633,
242        s: 1521547704,
243    },
244    SmallPrime {
245        p: 2146572289,
246        g: 1846678872,
247        s: 1310832121,
248    },
249    SmallPrime {
250        p: 2146547713,
251        g: 919368090,
252        s: 1019041349,
253    },
254    SmallPrime {
255        p: 2146508801,
256        g: 671847612,
257        s: 38582496,
258    },
259    SmallPrime {
260        p: 2146492417,
261        g: 283911680,
262        s: 532424562,
263    },
264    SmallPrime {
265        p: 2146490369,
266        g: 1780044827,
267        s: 896447978,
268    },
269    SmallPrime {
270        p: 2146459649,
271        g: 327980850,
272        s: 1327906900,
273    },
274    SmallPrime {
275        p: 2146447361,
276        g: 1310561493,
277        s: 958645253,
278    },
279    SmallPrime {
280        p: 2146441217,
281        g: 412148926,
282        s: 287271128,
283    },
284    SmallPrime {
285        p: 2146437121,
286        g: 293186449,
287        s: 2009822534,
288    },
289    SmallPrime {
290        p: 2146430977,
291        g: 179034356,
292        s: 1359155584,
293    },
294    SmallPrime {
295        p: 2146418689,
296        g: 1517345488,
297        s: 1790248672,
298    },
299    SmallPrime {
300        p: 2146406401,
301        g: 1615820390,
302        s: 1584833571,
303    },
304    SmallPrime {
305        p: 2146404353,
306        g: 826651445,
307        s: 607120498,
308    },
309    SmallPrime {
310        p: 2146379777,
311        g: 3816988,
312        s: 1897049071,
313    },
314    SmallPrime {
315        p: 2146363393,
316        g: 1221409784,
317        s: 1986921567,
318    },
319    SmallPrime {
320        p: 2146355201,
321        g: 1388081168,
322        s: 849968120,
323    },
324    SmallPrime {
325        p: 2146336769,
326        g: 1803473237,
327        s: 1655544036,
328    },
329    SmallPrime {
330        p: 2146312193,
331        g: 1023484977,
332        s: 273671831,
333    },
334    SmallPrime {
335        p: 2146293761,
336        g: 1074591448,
337        s: 467406983,
338    },
339    SmallPrime {
340        p: 2146283521,
341        g: 831604668,
342        s: 1523950494,
343    },
344    SmallPrime {
345        p: 2146203649,
346        g: 712865423,
347        s: 1170834574,
348    },
349    SmallPrime {
350        p: 2146154497,
351        g: 1764991362,
352        s: 1064856763,
353    },
354    SmallPrime {
355        p: 2146142209,
356        g: 627386213,
357        s: 1406840151,
358    },
359    SmallPrime {
360        p: 2146127873,
361        g: 1638674429,
362        s: 2088393537,
363    },
364    SmallPrime {
365        p: 2146099201,
366        g: 1516001018,
367        s: 690673370,
368    },
369    SmallPrime {
370        p: 2146093057,
371        g: 1294931393,
372        s: 315136610,
373    },
374    SmallPrime {
375        p: 2146091009,
376        g: 1942399533,
377        s: 973539425,
378    },
379    SmallPrime {
380        p: 2146078721,
381        g: 1843461814,
382        s: 2132275436,
383    },
384    SmallPrime {
385        p: 2146060289,
386        g: 1098740778,
387        s: 360423481,
388    },
389    SmallPrime {
390        p: 2146048001,
391        g: 1617213232,
392        s: 1951981294,
393    },
394    SmallPrime {
395        p: 2146041857,
396        g: 1805783169,
397        s: 2075683489,
398    },
399    SmallPrime {
400        p: 2146019329,
401        g: 272027909,
402        s: 1753219918,
403    },
404    SmallPrime {
405        p: 2145986561,
406        g: 1206530344,
407        s: 2034028118,
408    },
409    SmallPrime {
410        p: 2145976321,
411        g: 1243769360,
412        s: 1173377644,
413    },
414    SmallPrime {
415        p: 2145964033,
416        g: 887200839,
417        s: 1281344586,
418    },
419    SmallPrime {
420        p: 2145906689,
421        g: 1651026455,
422        s: 906178216,
423    },
424    SmallPrime {
425        p: 2145875969,
426        g: 1673238256,
427        s: 1043521212,
428    },
429    SmallPrime {
430        p: 2145871873,
431        g: 1226591210,
432        s: 1399796492,
433    },
434    SmallPrime {
435        p: 2145841153,
436        g: 1465353397,
437        s: 1324527802,
438    },
439    SmallPrime {
440        p: 2145832961,
441        g: 1150638905,
442        s: 554084759,
443    },
444    SmallPrime {
445        p: 2145816577,
446        g: 221601706,
447        s: 427340863,
448    },
449    SmallPrime {
450        p: 2145785857,
451        g: 608896761,
452        s: 316590738,
453    },
454    SmallPrime {
455        p: 2145755137,
456        g: 1712054942,
457        s: 1684294304,
458    },
459    SmallPrime {
460        p: 2145742849,
461        g: 1302302867,
462        s: 724873116,
463    },
464    SmallPrime {
465        p: 2145728513,
466        g: 516717693,
467        s: 431671476,
468    },
469    SmallPrime {
470        p: 2145699841,
471        g: 524575579,
472        s: 1619722537,
473    },
474    SmallPrime {
475        p: 2145691649,
476        g: 1925625239,
477        s: 982974435,
478    },
479    SmallPrime {
480        p: 2145687553,
481        g: 463795662,
482        s: 1293154300,
483    },
484    SmallPrime {
485        p: 2145673217,
486        g: 771716636,
487        s: 881778029,
488    },
489    SmallPrime {
490        p: 2145630209,
491        g: 1509556977,
492        s: 837364988,
493    },
494    SmallPrime {
495        p: 2145595393,
496        g: 229091856,
497        s: 851648427,
498    },
499    SmallPrime {
500        p: 2145587201,
501        g: 1796903241,
502        s: 635342424,
503    },
504    SmallPrime {
505        p: 2145525761,
506        g: 715310882,
507        s: 1677228081,
508    },
509    SmallPrime {
510        p: 2145495041,
511        g: 1040930522,
512        s: 200685896,
513    },
514    SmallPrime {
515        p: 2145466369,
516        g: 949804237,
517        s: 1809146322,
518    },
519    SmallPrime {
520        p: 2145445889,
521        g: 1673903706,
522        s: 95316881,
523    },
524    SmallPrime {
525        p: 2145390593,
526        g: 806941852,
527        s: 1428671135,
528    },
529    SmallPrime {
530        p: 2145372161,
531        g: 1402525292,
532        s: 159350694,
533    },
534    SmallPrime {
535        p: 2145361921,
536        g: 2124760298,
537        s: 1589134749,
538    },
539    SmallPrime {
540        p: 2145359873,
541        g: 1217503067,
542        s: 1561543010,
543    },
544    SmallPrime {
545        p: 2145355777,
546        g: 338341402,
547        s: 83865711,
548    },
549    SmallPrime {
550        p: 2145343489,
551        g: 1381532164,
552        s: 641430002,
553    },
554    SmallPrime {
555        p: 2145325057,
556        g: 1883895478,
557        s: 1528469895,
558    },
559    SmallPrime {
560        p: 2145318913,
561        g: 1335370424,
562        s: 65809740,
563    },
564    SmallPrime {
565        p: 2145312769,
566        g: 2000008042,
567        s: 1919775760,
568    },
569    SmallPrime {
570        p: 2145300481,
571        g: 961450962,
572        s: 1229540578,
573    },
574    SmallPrime {
575        p: 2145282049,
576        g: 910466767,
577        s: 1964062701,
578    },
579    SmallPrime {
580        p: 2145232897,
581        g: 816527501,
582        s: 450152063,
583    },
584    SmallPrime {
585        p: 2145218561,
586        g: 1435128058,
587        s: 1794509700,
588    },
589    SmallPrime {
590        p: 2145187841,
591        g: 33505311,
592        s: 1272467582,
593    },
594    SmallPrime {
595        p: 2145181697,
596        g: 269767433,
597        s: 1380363849,
598    },
599    SmallPrime {
600        p: 2145175553,
601        g: 56386299,
602        s: 1316870546,
603    },
604    SmallPrime {
605        p: 2145079297,
606        g: 2106880293,
607        s: 1391797340,
608    },
609    SmallPrime {
610        p: 2145021953,
611        g: 1347906152,
612        s: 720510798,
613    },
614    SmallPrime {
615        p: 2145015809,
616        g: 206769262,
617        s: 1651459955,
618    },
619    SmallPrime {
620        p: 2145003521,
621        g: 1885513236,
622        s: 1393381284,
623    },
624    SmallPrime {
625        p: 2144960513,
626        g: 1810381315,
627        s: 31937275,
628    },
629    SmallPrime {
630        p: 2144944129,
631        g: 1306487838,
632        s: 2019419520,
633    },
634    SmallPrime {
635        p: 2144935937,
636        g: 37304730,
637        s: 1841489054,
638    },
639    SmallPrime {
640        p: 2144894977,
641        g: 1601434616,
642        s: 157985831,
643    },
644    SmallPrime {
645        p: 2144888833,
646        g: 98749330,
647        s: 2128592228,
648    },
649    SmallPrime {
650        p: 2144880641,
651        g: 1772327002,
652        s: 2076128344,
653    },
654    SmallPrime {
655        p: 2144864257,
656        g: 1404514762,
657        s: 2029969964,
658    },
659    SmallPrime {
660        p: 2144827393,
661        g: 801236594,
662        s: 406627220,
663    },
664    SmallPrime {
665        p: 2144806913,
666        g: 349217443,
667        s: 1501080290,
668    },
669    SmallPrime {
670        p: 2144796673,
671        g: 1542656776,
672        s: 2084736519,
673    },
674    SmallPrime {
675        p: 2144778241,
676        g: 1210734884,
677        s: 1746416203,
678    },
679    SmallPrime {
680        p: 2144759809,
681        g: 1146598851,
682        s: 716464489,
683    },
684    SmallPrime {
685        p: 2144757761,
686        g: 286328400,
687        s: 1823728177,
688    },
689    SmallPrime {
690        p: 2144729089,
691        g: 1347555695,
692        s: 1836644881,
693    },
694    SmallPrime {
695        p: 2144727041,
696        g: 1795703790,
697        s: 520296412,
698    },
699    SmallPrime {
700        p: 2144696321,
701        g: 1302475157,
702        s: 852964281,
703    },
704    SmallPrime {
705        p: 2144667649,
706        g: 1075877614,
707        s: 504992927,
708    },
709    SmallPrime {
710        p: 2144573441,
711        g: 198765808,
712        s: 1617144982,
713    },
714    SmallPrime {
715        p: 2144555009,
716        g: 321528767,
717        s: 155821259,
718    },
719    SmallPrime {
720        p: 2144550913,
721        g: 814139516,
722        s: 1819937644,
723    },
724    SmallPrime {
725        p: 2144536577,
726        g: 571143206,
727        s: 962942255,
728    },
729    SmallPrime {
730        p: 2144524289,
731        g: 1746733766,
732        s: 2471321,
733    },
734    SmallPrime {
735        p: 2144512001,
736        g: 1821415077,
737        s: 124190939,
738    },
739    SmallPrime {
740        p: 2144468993,
741        g: 917871546,
742        s: 1260072806,
743    },
744    SmallPrime {
745        p: 2144458753,
746        g: 378417981,
747        s: 1569240563,
748    },
749    SmallPrime {
750        p: 2144421889,
751        g: 175229668,
752        s: 1825620763,
753    },
754    SmallPrime {
755        p: 2144409601,
756        g: 1699216963,
757        s: 351648117,
758    },
759    SmallPrime {
760        p: 2144370689,
761        g: 1071885991,
762        s: 958186029,
763    },
764    SmallPrime {
765        p: 2144348161,
766        g: 1763151227,
767        s: 540353574,
768    },
769    SmallPrime {
770        p: 2144335873,
771        g: 1060214804,
772        s: 919598847,
773    },
774    SmallPrime {
775        p: 2144329729,
776        g: 663515846,
777        s: 1448552668,
778    },
779    SmallPrime {
780        p: 2144327681,
781        g: 1057776305,
782        s: 590222840,
783    },
784    SmallPrime {
785        p: 2144309249,
786        g: 1705149168,
787        s: 1459294624,
788    },
789    SmallPrime {
790        p: 2144296961,
791        g: 325823721,
792        s: 1649016934,
793    },
794    SmallPrime {
795        p: 2144290817,
796        g: 738775789,
797        s: 447427206,
798    },
799    SmallPrime {
800        p: 2144243713,
801        g: 962347618,
802        s: 893050215,
803    },
804    SmallPrime {
805        p: 2144237569,
806        g: 1655257077,
807        s: 900860862,
808    },
809    SmallPrime {
810        p: 2144161793,
811        g: 242206694,
812        s: 1567868672,
813    },
814    SmallPrime {
815        p: 2144155649,
816        g: 769415308,
817        s: 1247993134,
818    },
819    SmallPrime {
820        p: 2144137217,
821        g: 320492023,
822        s: 515841070,
823    },
824    SmallPrime {
825        p: 2144120833,
826        g: 1639388522,
827        s: 770877302,
828    },
829    SmallPrime {
830        p: 2144071681,
831        g: 1761785233,
832        s: 964296120,
833    },
834    SmallPrime {
835        p: 2144065537,
836        g: 419817825,
837        s: 204564472,
838    },
839    SmallPrime {
840        p: 2144028673,
841        g: 666050597,
842        s: 2091019760,
843    },
844    SmallPrime {
845        p: 2144010241,
846        g: 1413657615,
847        s: 1518702610,
848    },
849    SmallPrime {
850        p: 2143952897,
851        g: 1238327946,
852        s: 475672271,
853    },
854    SmallPrime {
855        p: 2143940609,
856        g: 307063413,
857        s: 1176750846,
858    },
859    SmallPrime {
860        p: 2143918081,
861        g: 2062905559,
862        s: 786785803,
863    },
864    SmallPrime {
865        p: 2143899649,
866        g: 1338112849,
867        s: 1562292083,
868    },
869    SmallPrime {
870        p: 2143891457,
871        g: 68149545,
872        s: 87166451,
873    },
874    SmallPrime {
875        p: 2143885313,
876        g: 921750778,
877        s: 394460854,
878    },
879    SmallPrime {
880        p: 2143854593,
881        g: 719766593,
882        s: 133877196,
883    },
884    SmallPrime {
885        p: 2143836161,
886        g: 1149399850,
887        s: 1861591875,
888    },
889    SmallPrime {
890        p: 2143762433,
891        g: 1848739366,
892        s: 1335934145,
893    },
894    SmallPrime {
895        p: 2143756289,
896        g: 1326674710,
897        s: 102999236,
898    },
899    SmallPrime {
900        p: 2143713281,
901        g: 808061791,
902        s: 1156900308,
903    },
904    SmallPrime {
905        p: 2143690753,
906        g: 388399459,
907        s: 1926468019,
908    },
909    SmallPrime {
910        p: 2143670273,
911        g: 1427891374,
912        s: 1756689401,
913    },
914    SmallPrime {
915        p: 2143666177,
916        g: 1912173949,
917        s: 986629565,
918    },
919    SmallPrime {
920        p: 2143645697,
921        g: 2041160111,
922        s: 371842865,
923    },
924    SmallPrime {
925        p: 2143641601,
926        g: 1279906897,
927        s: 2023974350,
928    },
929    SmallPrime {
930        p: 2143635457,
931        g: 720473174,
932        s: 1389027526,
933    },
934    SmallPrime {
935        p: 2143621121,
936        g: 1298309455,
937        s: 1732632006,
938    },
939    SmallPrime {
940        p: 2143598593,
941        g: 1548762216,
942        s: 1825417506,
943    },
944    SmallPrime {
945        p: 2143567873,
946        g: 620475784,
947        s: 1073787233,
948    },
949    SmallPrime {
950        p: 2143561729,
951        g: 1932954575,
952        s: 949167309,
953    },
954    SmallPrime {
955        p: 2143553537,
956        g: 354315656,
957        s: 1652037534,
958    },
959    SmallPrime {
960        p: 2143541249,
961        g: 577424288,
962        s: 1097027618,
963    },
964    SmallPrime {
965        p: 2143531009,
966        g: 357862822,
967        s: 478640055,
968    },
969    SmallPrime {
970        p: 2143522817,
971        g: 2017706025,
972        s: 1550531668,
973    },
974    SmallPrime {
975        p: 2143506433,
976        g: 2078127419,
977        s: 1824320165,
978    },
979    SmallPrime {
980        p: 2143488001,
981        g: 613475285,
982        s: 1604011510,
983    },
984    SmallPrime {
985        p: 2143469569,
986        g: 1466594987,
987        s: 502095196,
988    },
989    SmallPrime {
990        p: 2143426561,
991        g: 1115430331,
992        s: 1044637111,
993    },
994    SmallPrime {
995        p: 2143383553,
996        g: 9778045,
997        s: 1902463734,
998    },
999    SmallPrime {
1000        p: 2143377409,
1001        g: 1557401276,
1002        s: 2056861771,
1003    },
1004    SmallPrime {
1005        p: 2143363073,
1006        g: 652036455,
1007        s: 1965915971,
1008    },
1009    SmallPrime {
1010        p: 2143260673,
1011        g: 1464581171,
1012        s: 1523257541,
1013    },
1014    SmallPrime {
1015        p: 2143246337,
1016        g: 1876119649,
1017        s: 764541916,
1018    },
1019    SmallPrime {
1020        p: 2143209473,
1021        g: 1614992673,
1022        s: 1920672844,
1023    },
1024    SmallPrime {
1025        p: 2143203329,
1026        g: 981052047,
1027        s: 2049774209,
1028    },
1029    SmallPrime {
1030        p: 2143160321,
1031        g: 1847355533,
1032        s: 728535665,
1033    },
1034    SmallPrime {
1035        p: 2143129601,
1036        g: 965558457,
1037        s: 603052992,
1038    },
1039    SmallPrime {
1040        p: 2143123457,
1041        g: 2140817191,
1042        s: 8348679,
1043    },
1044    SmallPrime {
1045        p: 2143100929,
1046        g: 1547263683,
1047        s: 694209023,
1048    },
1049    SmallPrime {
1050        p: 2143092737,
1051        g: 643459066,
1052        s: 1979934533,
1053    },
1054    SmallPrime {
1055        p: 2143082497,
1056        g: 188603778,
1057        s: 2026175670,
1058    },
1059    SmallPrime {
1060        p: 2143062017,
1061        g: 1657329695,
1062        s: 377451099,
1063    },
1064    SmallPrime {
1065        p: 2143051777,
1066        g: 114967950,
1067        s: 979255473,
1068    },
1069    SmallPrime {
1070        p: 2143025153,
1071        g: 1698431342,
1072        s: 1449196896,
1073    },
1074    SmallPrime {
1075        p: 2143006721,
1076        g: 1862741675,
1077        s: 1739650365,
1078    },
1079    SmallPrime {
1080        p: 2142996481,
1081        g: 756660457,
1082        s: 996160050,
1083    },
1084    SmallPrime {
1085        p: 2142976001,
1086        g: 927864010,
1087        s: 1166847574,
1088    },
1089    SmallPrime {
1090        p: 2142965761,
1091        g: 905070557,
1092        s: 661974566,
1093    },
1094    SmallPrime {
1095        p: 2142916609,
1096        g: 40932754,
1097        s: 1787161127,
1098    },
1099    SmallPrime {
1100        p: 2142892033,
1101        g: 1987985648,
1102        s: 675335382,
1103    },
1104    SmallPrime {
1105        p: 2142885889,
1106        g: 797497211,
1107        s: 1323096997,
1108    },
1109    SmallPrime {
1110        p: 2142871553,
1111        g: 2068025830,
1112        s: 1411877159,
1113    },
1114    SmallPrime {
1115        p: 2142861313,
1116        g: 1217177090,
1117        s: 1438410687,
1118    },
1119    SmallPrime {
1120        p: 2142830593,
1121        g: 409906375,
1122        s: 1767860634,
1123    },
1124    SmallPrime {
1125        p: 2142803969,
1126        g: 1197788993,
1127        s: 359782919,
1128    },
1129    SmallPrime {
1130        p: 2142785537,
1131        g: 643817365,
1132        s: 513932862,
1133    },
1134    SmallPrime {
1135        p: 2142779393,
1136        g: 1717046338,
1137        s: 218943121,
1138    },
1139    SmallPrime {
1140        p: 2142724097,
1141        g: 89336830,
1142        s: 416687049,
1143    },
1144    SmallPrime {
1145        p: 2142707713,
1146        g: 5944581,
1147        s: 1356813523,
1148    },
1149    SmallPrime {
1150        p: 2142658561,
1151        g: 887942135,
1152        s: 2074011722,
1153    },
1154    SmallPrime {
1155        p: 2142638081,
1156        g: 151851972,
1157        s: 1647339939,
1158    },
1159    SmallPrime {
1160        p: 2142564353,
1161        g: 1691505537,
1162        s: 1483107336,
1163    },
1164    SmallPrime {
1165        p: 2142533633,
1166        g: 1989920200,
1167        s: 1135938817,
1168    },
1169    SmallPrime {
1170        p: 2142529537,
1171        g: 959263126,
1172        s: 1531961857,
1173    },
1174    SmallPrime {
1175        p: 2142527489,
1176        g: 453251129,
1177        s: 1725566162,
1178    },
1179    SmallPrime {
1180        p: 2142502913,
1181        g: 1536028102,
1182        s: 182053257,
1183    },
1184    SmallPrime {
1185        p: 2142498817,
1186        g: 570138730,
1187        s: 701443447,
1188    },
1189    SmallPrime {
1190        p: 2142416897,
1191        g: 326965800,
1192        s: 411931819,
1193    },
1194    SmallPrime {
1195        p: 2142363649,
1196        g: 1675665410,
1197        s: 1517191733,
1198    },
1199    SmallPrime {
1200        p: 2142351361,
1201        g: 968529566,
1202        s: 1575712703,
1203    },
1204    SmallPrime {
1205        p: 2142330881,
1206        g: 1384953238,
1207        s: 1769087884,
1208    },
1209    SmallPrime {
1210        p: 2142314497,
1211        g: 1977173242,
1212        s: 1833745524,
1213    },
1214    SmallPrime {
1215        p: 2142289921,
1216        g: 95082313,
1217        s: 1714775493,
1218    },
1219    SmallPrime {
1220        p: 2142283777,
1221        g: 109377615,
1222        s: 1070584533,
1223    },
1224    SmallPrime {
1225        p: 2142277633,
1226        g: 16960510,
1227        s: 702157145,
1228    },
1229    SmallPrime {
1230        p: 2142263297,
1231        g: 553850819,
1232        s: 431364395,
1233    },
1234    SmallPrime {
1235        p: 2142208001,
1236        g: 241466367,
1237        s: 2053967982,
1238    },
1239    SmallPrime {
1240        p: 2142164993,
1241        g: 1795661326,
1242        s: 1031836848,
1243    },
1244    SmallPrime {
1245        p: 2142097409,
1246        g: 1212530046,
1247        s: 712772031,
1248    },
1249    SmallPrime {
1250        p: 2142087169,
1251        g: 1763869720,
1252        s: 822276067,
1253    },
1254    SmallPrime {
1255        p: 2142078977,
1256        g: 644065713,
1257        s: 1765268066,
1258    },
1259    SmallPrime {
1260        p: 2142074881,
1261        g: 112671944,
1262        s: 643204925,
1263    },
1264    SmallPrime {
1265        p: 2142044161,
1266        g: 1387785471,
1267        s: 1297890174,
1268    },
1269    SmallPrime {
1270        p: 2142025729,
1271        g: 783885537,
1272        s: 1000425730,
1273    },
1274    SmallPrime {
1275        p: 2142011393,
1276        g: 905662232,
1277        s: 1679401033,
1278    },
1279    SmallPrime {
1280        p: 2141974529,
1281        g: 799788433,
1282        s: 468119557,
1283    },
1284    SmallPrime {
1285        p: 2141943809,
1286        g: 1932544124,
1287        s: 449305555,
1288    },
1289    SmallPrime {
1290        p: 2141933569,
1291        g: 1527403256,
1292        s: 841867925,
1293    },
1294    SmallPrime {
1295        p: 2141931521,
1296        g: 1247076451,
1297        s: 743823916,
1298    },
1299    SmallPrime {
1300        p: 2141902849,
1301        g: 1199660531,
1302        s: 401687910,
1303    },
1304    SmallPrime {
1305        p: 2141890561,
1306        g: 150132350,
1307        s: 1720336972,
1308    },
1309    SmallPrime {
1310        p: 2141857793,
1311        g: 1287438162,
1312        s: 663880489,
1313    },
1314    SmallPrime {
1315        p: 2141833217,
1316        g: 618017731,
1317        s: 1819208266,
1318    },
1319    SmallPrime {
1320        p: 2141820929,
1321        g: 999578638,
1322        s: 1403090096,
1323    },
1324    SmallPrime {
1325        p: 2141786113,
1326        g: 81834325,
1327        s: 1523542501,
1328    },
1329    SmallPrime {
1330        p: 2141771777,
1331        g: 120001928,
1332        s: 463556492,
1333    },
1334    SmallPrime {
1335        p: 2141759489,
1336        g: 122455485,
1337        s: 2124928282,
1338    },
1339    SmallPrime {
1340        p: 2141749249,
1341        g: 141986041,
1342        s: 940339153,
1343    },
1344    SmallPrime {
1345        p: 2141685761,
1346        g: 889088734,
1347        s: 477141499,
1348    },
1349    SmallPrime {
1350        p: 2141673473,
1351        g: 324212681,
1352        s: 1122558298,
1353    },
1354    SmallPrime {
1355        p: 2141669377,
1356        g: 1175806187,
1357        s: 1373818177,
1358    },
1359    SmallPrime {
1360        p: 2141655041,
1361        g: 1113654822,
1362        s: 296887082,
1363    },
1364    SmallPrime {
1365        p: 2141587457,
1366        g: 991103258,
1367        s: 1585913875,
1368    },
1369    SmallPrime {
1370        p: 2141583361,
1371        g: 1401451409,
1372        s: 1802457360,
1373    },
1374    SmallPrime {
1375        p: 2141575169,
1376        g: 1571977166,
1377        s: 712760980,
1378    },
1379    SmallPrime {
1380        p: 2141546497,
1381        g: 1107849376,
1382        s: 1250270109,
1383    },
1384    SmallPrime {
1385        p: 2141515777,
1386        g: 196544219,
1387        s: 356001130,
1388    },
1389    SmallPrime {
1390        p: 2141495297,
1391        g: 1733571506,
1392        s: 1060744866,
1393    },
1394    SmallPrime {
1395        p: 2141483009,
1396        g: 321552363,
1397        s: 1168297026,
1398    },
1399    SmallPrime {
1400        p: 2141458433,
1401        g: 505818251,
1402        s: 733225819,
1403    },
1404    SmallPrime {
1405        p: 2141360129,
1406        g: 1026840098,
1407        s: 948342276,
1408    },
1409    SmallPrime {
1410        p: 2141325313,
1411        g: 945133744,
1412        s: 2129965998,
1413    },
1414    SmallPrime {
1415        p: 2141317121,
1416        g: 1871100260,
1417        s: 1843844634,
1418    },
1419    SmallPrime {
1420        p: 2141286401,
1421        g: 1790639498,
1422        s: 1750465696,
1423    },
1424    SmallPrime {
1425        p: 2141267969,
1426        g: 1376858592,
1427        s: 186160720,
1428    },
1429    SmallPrime {
1430        p: 2141255681,
1431        g: 2129698296,
1432        s: 1876677959,
1433    },
1434    SmallPrime {
1435        p: 2141243393,
1436        g: 2138900688,
1437        s: 1340009628,
1438    },
1439    SmallPrime {
1440        p: 2141214721,
1441        g: 1933049835,
1442        s: 1087819477,
1443    },
1444    SmallPrime {
1445        p: 2141212673,
1446        g: 1898664939,
1447        s: 1786328049,
1448    },
1449    SmallPrime {
1450        p: 2141202433,
1451        g: 990234828,
1452        s: 940682169,
1453    },
1454    SmallPrime {
1455        p: 2141175809,
1456        g: 1406392421,
1457        s: 993089586,
1458    },
1459    SmallPrime {
1460        p: 2141165569,
1461        g: 1263518371,
1462        s: 289019479,
1463    },
1464    SmallPrime {
1465        p: 2141073409,
1466        g: 1485624211,
1467        s: 507864514,
1468    },
1469    SmallPrime {
1470        p: 2141052929,
1471        g: 1885134788,
1472        s: 311252465,
1473    },
1474    SmallPrime {
1475        p: 2141040641,
1476        g: 1285021247,
1477        s: 280941862,
1478    },
1479    SmallPrime {
1480        p: 2141028353,
1481        g: 1527610374,
1482        s: 375035110,
1483    },
1484    SmallPrime {
1485        p: 2141011969,
1486        g: 1400626168,
1487        s: 164696620,
1488    },
1489    SmallPrime {
1490        p: 2140999681,
1491        g: 632959608,
1492        s: 966175067,
1493    },
1494    SmallPrime {
1495        p: 2140997633,
1496        g: 2045628978,
1497        s: 1290889438,
1498    },
1499    SmallPrime {
1500        p: 2140993537,
1501        g: 1412755491,
1502        s: 375366253,
1503    },
1504    SmallPrime {
1505        p: 2140942337,
1506        g: 719477232,
1507        s: 785367828,
1508    },
1509    SmallPrime {
1510        p: 2140925953,
1511        g: 45224252,
1512        s: 836552317,
1513    },
1514    SmallPrime {
1515        p: 2140917761,
1516        g: 1157376588,
1517        s: 1001839569,
1518    },
1519    SmallPrime {
1520        p: 2140887041,
1521        g: 278480752,
1522        s: 2098732796,
1523    },
1524    SmallPrime {
1525        p: 2140837889,
1526        g: 1663139953,
1527        s: 924094810,
1528    },
1529    SmallPrime {
1530        p: 2140788737,
1531        g: 802501511,
1532        s: 2045368990,
1533    },
1534    SmallPrime {
1535        p: 2140766209,
1536        g: 1820083885,
1537        s: 1800295504,
1538    },
1539    SmallPrime {
1540        p: 2140764161,
1541        g: 1169561905,
1542        s: 2106792035,
1543    },
1544    SmallPrime {
1545        p: 2140696577,
1546        g: 127781498,
1547        s: 1885987531,
1548    },
1549    SmallPrime {
1550        p: 2140684289,
1551        g: 16014477,
1552        s: 1098116827,
1553    },
1554    SmallPrime {
1555        p: 2140653569,
1556        g: 665960598,
1557        s: 1796728247,
1558    },
1559    SmallPrime {
1560        p: 2140594177,
1561        g: 1043085491,
1562        s: 377310938,
1563    },
1564    SmallPrime {
1565        p: 2140579841,
1566        g: 1732838211,
1567        s: 1504505945,
1568    },
1569    SmallPrime {
1570        p: 2140569601,
1571        g: 302071939,
1572        s: 358291016,
1573    },
1574    SmallPrime {
1575        p: 2140567553,
1576        g: 192393733,
1577        s: 1909137143,
1578    },
1579    SmallPrime {
1580        p: 2140557313,
1581        g: 406595731,
1582        s: 1175330270,
1583    },
1584    SmallPrime {
1585        p: 2140549121,
1586        g: 1748850918,
1587        s: 525007007,
1588    },
1589    SmallPrime {
1590        p: 2140477441,
1591        g: 499436566,
1592        s: 1031159814,
1593    },
1594    SmallPrime {
1595        p: 2140469249,
1596        g: 1886004401,
1597        s: 1029951320,
1598    },
1599    SmallPrime {
1600        p: 2140426241,
1601        g: 1483168100,
1602        s: 1676273461,
1603    },
1604    SmallPrime {
1605        p: 2140420097,
1606        g: 1779917297,
1607        s: 846024476,
1608    },
1609    SmallPrime {
1610        p: 2140413953,
1611        g: 522948893,
1612        s: 1816354149,
1613    },
1614    SmallPrime {
1615        p: 2140383233,
1616        g: 1931364473,
1617        s: 1296921241,
1618    },
1619    SmallPrime {
1620        p: 2140366849,
1621        g: 1917356555,
1622        s: 147196204,
1623    },
1624    SmallPrime {
1625        p: 2140354561,
1626        g: 16466177,
1627        s: 1349052107,
1628    },
1629    SmallPrime {
1630        p: 2140348417,
1631        g: 1875366972,
1632        s: 1860485634,
1633    },
1634    SmallPrime {
1635        p: 2140323841,
1636        g: 456498717,
1637        s: 1790256483,
1638    },
1639    SmallPrime {
1640        p: 2140321793,
1641        g: 1629493973,
1642        s: 150031888,
1643    },
1644    SmallPrime {
1645        p: 2140315649,
1646        g: 1904063898,
1647        s: 395510935,
1648    },
1649    SmallPrime {
1650        p: 2140280833,
1651        g: 1784104328,
1652        s: 831417909,
1653    },
1654    SmallPrime {
1655        p: 2140250113,
1656        g: 256087139,
1657        s: 697349101,
1658    },
1659    SmallPrime {
1660        p: 2140229633,
1661        g: 388553070,
1662        s: 243875754,
1663    },
1664    SmallPrime {
1665        p: 2140223489,
1666        g: 747459608,
1667        s: 1396270850,
1668    },
1669    SmallPrime {
1670        p: 2140200961,
1671        g: 507423743,
1672        s: 1895572209,
1673    },
1674    SmallPrime {
1675        p: 2140162049,
1676        g: 580106016,
1677        s: 2045297469,
1678    },
1679    SmallPrime {
1680        p: 2140149761,
1681        g: 712426444,
1682        s: 785217995,
1683    },
1684    SmallPrime {
1685        p: 2140137473,
1686        g: 1441607584,
1687        s: 536866543,
1688    },
1689    SmallPrime {
1690        p: 2140119041,
1691        g: 346538902,
1692        s: 1740434653,
1693    },
1694    SmallPrime {
1695        p: 2140090369,
1696        g: 282642885,
1697        s: 21051094,
1698    },
1699    SmallPrime {
1700        p: 2140076033,
1701        g: 1407456228,
1702        s: 319910029,
1703    },
1704    SmallPrime {
1705        p: 2140047361,
1706        g: 1619330500,
1707        s: 1488632070,
1708    },
1709    SmallPrime {
1710        p: 2140041217,
1711        g: 2089408064,
1712        s: 2012026134,
1713    },
1714    SmallPrime {
1715        p: 2140008449,
1716        g: 1705524800,
1717        s: 1613440760,
1718    },
1719    SmallPrime {
1720        p: 2139924481,
1721        g: 1846208233,
1722        s: 1280649481,
1723    },
1724    SmallPrime {
1725        p: 2139906049,
1726        g: 989438755,
1727        s: 1185646076,
1728    },
1729    SmallPrime {
1730        p: 2139867137,
1731        g: 1522314850,
1732        s: 372783595,
1733    },
1734    SmallPrime {
1735        p: 2139842561,
1736        g: 1681587377,
1737        s: 216848235,
1738    },
1739    SmallPrime {
1740        p: 2139826177,
1741        g: 2066284988,
1742        s: 1784999464,
1743    },
1744    SmallPrime {
1745        p: 2139824129,
1746        g: 480888214,
1747        s: 1513323027,
1748    },
1749    SmallPrime {
1750        p: 2139789313,
1751        g: 847937200,
1752        s: 858192859,
1753    },
1754    SmallPrime {
1755        p: 2139783169,
1756        g: 1642000434,
1757        s: 1583261448,
1758    },
1759    SmallPrime {
1760        p: 2139770881,
1761        g: 940699589,
1762        s: 179702100,
1763    },
1764    SmallPrime {
1765        p: 2139768833,
1766        g: 315623242,
1767        s: 964612676,
1768    },
1769    SmallPrime {
1770        p: 2139666433,
1771        g: 331649203,
1772        s: 764666914,
1773    },
1774    SmallPrime {
1775        p: 2139641857,
1776        g: 2118730799,
1777        s: 1313764644,
1778    },
1779    SmallPrime {
1780        p: 2139635713,
1781        g: 519149027,
1782        s: 519212449,
1783    },
1784    SmallPrime {
1785        p: 2139598849,
1786        g: 1526413634,
1787        s: 1769667104,
1788    },
1789    SmallPrime {
1790        p: 2139574273,
1791        g: 551148610,
1792        s: 820739925,
1793    },
1794    SmallPrime {
1795        p: 2139568129,
1796        g: 1386800242,
1797        s: 472447405,
1798    },
1799    SmallPrime {
1800        p: 2139549697,
1801        g: 813760130,
1802        s: 1412328531,
1803    },
1804    SmallPrime {
1805        p: 2139537409,
1806        g: 1615286260,
1807        s: 1609362979,
1808    },
1809    SmallPrime {
1810        p: 2139475969,
1811        g: 1352559299,
1812        s: 1696720421,
1813    },
1814    SmallPrime {
1815        p: 2139455489,
1816        g: 1048691649,
1817        s: 1584935400,
1818    },
1819    SmallPrime {
1820        p: 2139432961,
1821        g: 836025845,
1822        s: 950121150,
1823    },
1824    SmallPrime {
1825        p: 2139424769,
1826        g: 1558281165,
1827        s: 1635486858,
1828    },
1829    SmallPrime {
1830        p: 2139406337,
1831        g: 1728402143,
1832        s: 1674423301,
1833    },
1834    SmallPrime {
1835        p: 2139396097,
1836        g: 1727715782,
1837        s: 1483470544,
1838    },
1839    SmallPrime {
1840        p: 2139383809,
1841        g: 1092853491,
1842        s: 1741699084,
1843    },
1844    SmallPrime {
1845        p: 2139369473,
1846        g: 690776899,
1847        s: 1242798709,
1848    },
1849    SmallPrime {
1850        p: 2139351041,
1851        g: 1768782380,
1852        s: 2120712049,
1853    },
1854    SmallPrime {
1855        p: 2139334657,
1856        g: 1739968247,
1857        s: 1427249225,
1858    },
1859    SmallPrime {
1860        p: 2139332609,
1861        g: 1547189119,
1862        s: 623011170,
1863    },
1864    SmallPrime {
1865        p: 2139310081,
1866        g: 1346827917,
1867        s: 1605466350,
1868    },
1869    SmallPrime {
1870        p: 2139303937,
1871        g: 369317948,
1872        s: 828392831,
1873    },
1874    SmallPrime {
1875        p: 2139301889,
1876        g: 1560417239,
1877        s: 1788073219,
1878    },
1879    SmallPrime {
1880        p: 2139283457,
1881        g: 1303121623,
1882        s: 595079358,
1883    },
1884    SmallPrime {
1885        p: 2139248641,
1886        g: 1354555286,
1887        s: 573424177,
1888    },
1889    SmallPrime {
1890        p: 2139240449,
1891        g: 60974056,
1892        s: 885781403,
1893    },
1894    SmallPrime {
1895        p: 2139222017,
1896        g: 355573421,
1897        s: 1221054839,
1898    },
1899    SmallPrime {
1900        p: 2139215873,
1901        g: 566477826,
1902        s: 1724006500,
1903    },
1904    SmallPrime {
1905        p: 2139150337,
1906        g: 871437673,
1907        s: 1609133294,
1908    },
1909    SmallPrime {
1910        p: 2139144193,
1911        g: 1478130914,
1912        s: 1137491905,
1913    },
1914    SmallPrime {
1915        p: 2139117569,
1916        g: 1854880922,
1917        s: 964728507,
1918    },
1919    SmallPrime {
1920        p: 2139076609,
1921        g: 202405335,
1922        s: 756508944,
1923    },
1924    SmallPrime {
1925        p: 2139062273,
1926        g: 1399715741,
1927        s: 884826059,
1928    },
1929    SmallPrime {
1930        p: 2139045889,
1931        g: 1051045798,
1932        s: 1202295476,
1933    },
1934    SmallPrime {
1935        p: 2139033601,
1936        g: 1707715206,
1937        s: 632234634,
1938    },
1939    SmallPrime {
1940        p: 2139006977,
1941        g: 2035853139,
1942        s: 231626690,
1943    },
1944    SmallPrime {
1945        p: 2138951681,
1946        g: 183867876,
1947        s: 838350879,
1948    },
1949    SmallPrime {
1950        p: 2138945537,
1951        g: 1403254661,
1952        s: 404460202,
1953    },
1954    SmallPrime {
1955        p: 2138920961,
1956        g: 310865011,
1957        s: 1282911681,
1958    },
1959    SmallPrime {
1960        p: 2138910721,
1961        g: 1328496553,
1962        s: 103472415,
1963    },
1964    SmallPrime {
1965        p: 2138904577,
1966        g: 78831681,
1967        s: 993513549,
1968    },
1969    SmallPrime {
1970        p: 2138902529,
1971        g: 1319697451,
1972        s: 1055904361,
1973    },
1974    SmallPrime {
1975        p: 2138816513,
1976        g: 384338872,
1977        s: 1706202469,
1978    },
1979    SmallPrime {
1980        p: 2138810369,
1981        g: 1084868275,
1982        s: 405677177,
1983    },
1984    SmallPrime {
1985        p: 2138787841,
1986        g: 401181788,
1987        s: 1964773901,
1988    },
1989    SmallPrime {
1990        p: 2138775553,
1991        g: 1850532988,
1992        s: 1247087473,
1993    },
1994    SmallPrime {
1995        p: 2138767361,
1996        g: 874261901,
1997        s: 1576073565,
1998    },
1999    SmallPrime {
2000        p: 2138757121,
2001        g: 1187474742,
2002        s: 993541415,
2003    },
2004    SmallPrime {
2005        p: 2138748929,
2006        g: 1782458888,
2007        s: 1043206483,
2008    },
2009    SmallPrime {
2010        p: 2138744833,
2011        g: 1221500487,
2012        s: 800141243,
2013    },
2014    SmallPrime {
2015        p: 2138738689,
2016        g: 413465368,
2017        s: 1450660558,
2018    },
2019    SmallPrime {
2020        p: 2138695681,
2021        g: 739045140,
2022        s: 342611472,
2023    },
2024    SmallPrime {
2025        p: 2138658817,
2026        g: 1355845756,
2027        s: 672674190,
2028    },
2029    SmallPrime {
2030        p: 2138644481,
2031        g: 608379162,
2032        s: 1538874380,
2033    },
2034    SmallPrime {
2035        p: 2138632193,
2036        g: 1444914034,
2037        s: 686911254,
2038    },
2039    SmallPrime {
2040        p: 2138607617,
2041        g: 484707818,
2042        s: 1435142134,
2043    },
2044    SmallPrime {
2045        p: 2138591233,
2046        g: 539460669,
2047        s: 1290458549,
2048    },
2049    SmallPrime {
2050        p: 2138572801,
2051        g: 2093538990,
2052        s: 2011138646,
2053    },
2054    SmallPrime {
2055        p: 2138552321,
2056        g: 1149786988,
2057        s: 1076414907,
2058    },
2059    SmallPrime {
2060        p: 2138546177,
2061        g: 840688206,
2062        s: 2108985273,
2063    },
2064    SmallPrime {
2065        p: 2138533889,
2066        g: 209669619,
2067        s: 198172413,
2068    },
2069    SmallPrime {
2070        p: 2138523649,
2071        g: 1975879426,
2072        s: 1277003968,
2073    },
2074    SmallPrime {
2075        p: 2138490881,
2076        g: 1351891144,
2077        s: 1976858109,
2078    },
2079    SmallPrime {
2080        p: 2138460161,
2081        g: 1817321013,
2082        s: 1979278293,
2083    },
2084    SmallPrime {
2085        p: 2138429441,
2086        g: 1950077177,
2087        s: 203441928,
2088    },
2089    SmallPrime {
2090        p: 2138400769,
2091        g: 908970113,
2092        s: 628395069,
2093    },
2094    SmallPrime {
2095        p: 2138398721,
2096        g: 219890864,
2097        s: 758486760,
2098    },
2099    SmallPrime {
2100        p: 2138376193,
2101        g: 1306654379,
2102        s: 977554090,
2103    },
2104    SmallPrime {
2105        p: 2138351617,
2106        g: 298822498,
2107        s: 2004708503,
2108    },
2109    SmallPrime {
2110        p: 2138337281,
2111        g: 441457816,
2112        s: 1049002108,
2113    },
2114    SmallPrime {
2115        p: 2138320897,
2116        g: 1517731724,
2117        s: 1442269609,
2118    },
2119    SmallPrime {
2120        p: 2138290177,
2121        g: 1355911197,
2122        s: 1647139103,
2123    },
2124    SmallPrime {
2125        p: 2138234881,
2126        g: 531313247,
2127        s: 1746591962,
2128    },
2129    SmallPrime {
2130        p: 2138214401,
2131        g: 1899410930,
2132        s: 781416444,
2133    },
2134    SmallPrime {
2135        p: 2138202113,
2136        g: 1813477173,
2137        s: 1622508515,
2138    },
2139    SmallPrime {
2140        p: 2138191873,
2141        g: 1086458299,
2142        s: 1025408615,
2143    },
2144    SmallPrime {
2145        p: 2138183681,
2146        g: 1998800427,
2147        s: 827063290,
2148    },
2149    SmallPrime {
2150        p: 2138173441,
2151        g: 1921308898,
2152        s: 749670117,
2153    },
2154    SmallPrime {
2155        p: 2138103809,
2156        g: 1620902804,
2157        s: 2126787647,
2158    },
2159    SmallPrime {
2160        p: 2138099713,
2161        g: 828647069,
2162        s: 1892961817,
2163    },
2164    SmallPrime {
2165        p: 2138085377,
2166        g: 179405355,
2167        s: 1525506535,
2168    },
2169    SmallPrime {
2170        p: 2138060801,
2171        g: 615683235,
2172        s: 1259580138,
2173    },
2174    SmallPrime {
2175        p: 2138044417,
2176        g: 2030277840,
2177        s: 1731266562,
2178    },
2179    SmallPrime {
2180        p: 2138042369,
2181        g: 2087222316,
2182        s: 1627902259,
2183    },
2184    SmallPrime {
2185        p: 2138032129,
2186        g: 126388712,
2187        s: 1108640984,
2188    },
2189    SmallPrime {
2190        p: 2138011649,
2191        g: 715026550,
2192        s: 1017980050,
2193    },
2194    SmallPrime {
2195        p: 2137993217,
2196        g: 1693714349,
2197        s: 1351778704,
2198    },
2199    SmallPrime {
2200        p: 2137888769,
2201        g: 1289762259,
2202        s: 1053090405,
2203    },
2204    SmallPrime {
2205        p: 2137853953,
2206        g: 199991890,
2207        s: 1254192789,
2208    },
2209    SmallPrime {
2210        p: 2137833473,
2211        g: 941421685,
2212        s: 896995556,
2213    },
2214    SmallPrime {
2215        p: 2137817089,
2216        g: 750416446,
2217        s: 1251031181,
2218    },
2219    SmallPrime {
2220        p: 2137792513,
2221        g: 798075119,
2222        s: 368077456,
2223    },
2224    SmallPrime {
2225        p: 2137786369,
2226        g: 878543495,
2227        s: 1035375025,
2228    },
2229    SmallPrime {
2230        p: 2137767937,
2231        g: 9351178,
2232        s: 1156563902,
2233    },
2234    SmallPrime {
2235        p: 2137755649,
2236        g: 1382297614,
2237        s: 1686559583,
2238    },
2239    SmallPrime {
2240        p: 2137724929,
2241        g: 1345472850,
2242        s: 1681096331,
2243    },
2244    SmallPrime {
2245        p: 2137704449,
2246        g: 834666929,
2247        s: 630551727,
2248    },
2249    SmallPrime {
2250        p: 2137673729,
2251        g: 1646165729,
2252        s: 1892091571,
2253    },
2254    SmallPrime {
2255        p: 2137620481,
2256        g: 778943821,
2257        s: 48456461,
2258    },
2259    SmallPrime {
2260        p: 2137618433,
2261        g: 1730837875,
2262        s: 1713336725,
2263    },
2264    SmallPrime {
2265        p: 2137581569,
2266        g: 805610339,
2267        s: 1378891359,
2268    },
2269    SmallPrime {
2270        p: 2137538561,
2271        g: 204342388,
2272        s: 1950165220,
2273    },
2274    SmallPrime {
2275        p: 2137526273,
2276        g: 1947629754,
2277        s: 1500789441,
2278    },
2279    SmallPrime {
2280        p: 2137516033,
2281        g: 719902645,
2282        s: 1499525372,
2283    },
2284    SmallPrime {
2285        p: 2137491457,
2286        g: 230451261,
2287        s: 556382829,
2288    },
2289    SmallPrime {
2290        p: 2137440257,
2291        g: 979573541,
2292        s: 412760291,
2293    },
2294    SmallPrime {
2295        p: 2137374721,
2296        g: 927841248,
2297        s: 1954137185,
2298    },
2299    SmallPrime {
2300        p: 2137362433,
2301        g: 1243778559,
2302        s: 861024672,
2303    },
2304    SmallPrime {
2305        p: 2137313281,
2306        g: 1341338501,
2307        s: 980638386,
2308    },
2309    SmallPrime {
2310        p: 2137311233,
2311        g: 937415182,
2312        s: 1793212117,
2313    },
2314    SmallPrime {
2315        p: 2137255937,
2316        g: 795331324,
2317        s: 1410253405,
2318    },
2319    SmallPrime {
2320        p: 2137243649,
2321        g: 150756339,
2322        s: 1966999887,
2323    },
2324    SmallPrime {
2325        p: 2137182209,
2326        g: 163346914,
2327        s: 1939301431,
2328    },
2329    SmallPrime {
2330        p: 2137171969,
2331        g: 1952552395,
2332        s: 758913141,
2333    },
2334    SmallPrime {
2335        p: 2137159681,
2336        g: 570788721,
2337        s: 218668666,
2338    },
2339    SmallPrime {
2340        p: 2137147393,
2341        g: 1896656810,
2342        s: 2045670345,
2343    },
2344    SmallPrime {
2345        p: 2137141249,
2346        g: 358493842,
2347        s: 518199643,
2348    },
2349    SmallPrime {
2350        p: 2137139201,
2351        g: 1505023029,
2352        s: 674695848,
2353    },
2354    SmallPrime {
2355        p: 2137133057,
2356        g: 27911103,
2357        s: 830956306,
2358    },
2359    SmallPrime {
2360        p: 2137122817,
2361        g: 439771337,
2362        s: 1555268614,
2363    },
2364    SmallPrime {
2365        p: 2137116673,
2366        g: 790988579,
2367        s: 1871449599,
2368    },
2369    SmallPrime {
2370        p: 2137110529,
2371        g: 432109234,
2372        s: 811805080,
2373    },
2374    SmallPrime {
2375        p: 2137102337,
2376        g: 1357900653,
2377        s: 1184997641,
2378    },
2379    SmallPrime {
2380        p: 2137098241,
2381        g: 515119035,
2382        s: 1715693095,
2383    },
2384    SmallPrime {
2385        p: 2137090049,
2386        g: 408575203,
2387        s: 2085660657,
2388    },
2389    SmallPrime {
2390        p: 2137085953,
2391        g: 2097793407,
2392        s: 1349626963,
2393    },
2394    SmallPrime {
2395        p: 2137055233,
2396        g: 1556739954,
2397        s: 1449960883,
2398    },
2399    SmallPrime {
2400        p: 2137030657,
2401        g: 1545758650,
2402        s: 1369303716,
2403    },
2404    SmallPrime {
2405        p: 2136987649,
2406        g: 332602570,
2407        s: 103875114,
2408    },
2409    SmallPrime {
2410        p: 2136969217,
2411        g: 1499989506,
2412        s: 1662964115,
2413    },
2414    SmallPrime {
2415        p: 2136924161,
2416        g: 857040753,
2417        s: 4738842,
2418    },
2419    SmallPrime {
2420        p: 2136895489,
2421        g: 1948872712,
2422        s: 570436091,
2423    },
2424    SmallPrime {
2425        p: 2136893441,
2426        g: 58969960,
2427        s: 1568349634,
2428    },
2429    SmallPrime {
2430        p: 2136887297,
2431        g: 2127193379,
2432        s: 273612548,
2433    },
2434    SmallPrime {
2435        p: 2136850433,
2436        g: 111208983,
2437        s: 1181257116,
2438    },
2439    SmallPrime {
2440        p: 2136809473,
2441        g: 1627275942,
2442        s: 1680317971,
2443    },
2444    SmallPrime {
2445        p: 2136764417,
2446        g: 1574888217,
2447        s: 14011331,
2448    },
2449    SmallPrime {
2450        p: 2136741889,
2451        g: 14011055,
2452        s: 1129154251,
2453    },
2454    SmallPrime {
2455        p: 2136727553,
2456        g: 35862563,
2457        s: 1838555253,
2458    },
2459    SmallPrime {
2460        p: 2136721409,
2461        g: 310235666,
2462        s: 1363928244,
2463    },
2464    SmallPrime {
2465        p: 2136698881,
2466        g: 1612429202,
2467        s: 1560383828,
2468    },
2469    SmallPrime {
2470        p: 2136649729,
2471        g: 1138540131,
2472        s: 800014364,
2473    },
2474    SmallPrime {
2475        p: 2136606721,
2476        g: 602323503,
2477        s: 1433096652,
2478    },
2479    SmallPrime {
2480        p: 2136563713,
2481        g: 182209265,
2482        s: 1919611038,
2483    },
2484    SmallPrime {
2485        p: 2136555521,
2486        g: 324156477,
2487        s: 165591039,
2488    },
2489    SmallPrime {
2490        p: 2136549377,
2491        g: 195513113,
2492        s: 217165345,
2493    },
2494    SmallPrime {
2495        p: 2136526849,
2496        g: 1050768046,
2497        s: 939647887,
2498    },
2499    SmallPrime {
2500        p: 2136508417,
2501        g: 1886286237,
2502        s: 1619926572,
2503    },
2504    SmallPrime {
2505        p: 2136477697,
2506        g: 609647664,
2507        s: 35065157,
2508    },
2509    SmallPrime {
2510        p: 2136471553,
2511        g: 679352216,
2512        s: 1452259468,
2513    },
2514    SmallPrime {
2515        p: 2136457217,
2516        g: 128630031,
2517        s: 824816521,
2518    },
2519    SmallPrime {
2520        p: 2136422401,
2521        g: 19787464,
2522        s: 1526049830,
2523    },
2524    SmallPrime {
2525        p: 2136420353,
2526        g: 698316836,
2527        s: 1530623527,
2528    },
2529    SmallPrime {
2530        p: 2136371201,
2531        g: 1651862373,
2532        s: 1804812805,
2533    },
2534    SmallPrime {
2535        p: 2136334337,
2536        g: 326596005,
2537        s: 336977082,
2538    },
2539    SmallPrime {
2540        p: 2136322049,
2541        g: 63253370,
2542        s: 1904972151,
2543    },
2544    SmallPrime {
2545        p: 2136297473,
2546        g: 312176076,
2547        s: 172182411,
2548    },
2549    SmallPrime {
2550        p: 2136248321,
2551        g: 381261841,
2552        s: 369032670,
2553    },
2554    SmallPrime {
2555        p: 2136242177,
2556        g: 358688773,
2557        s: 1640007994,
2558    },
2559    SmallPrime {
2560        p: 2136229889,
2561        g: 512677188,
2562        s: 75585225,
2563    },
2564    SmallPrime {
2565        p: 2136219649,
2566        g: 2095003250,
2567        s: 1970086149,
2568    },
2569    SmallPrime {
2570        p: 2136207361,
2571        g: 1909650722,
2572        s: 537760675,
2573    },
2574    SmallPrime {
2575        p: 2136176641,
2576        g: 1334616195,
2577        s: 1533487619,
2578    },
2579    SmallPrime {
2580        p: 2136158209,
2581        g: 2096285632,
2582        s: 1793285210,
2583    },
2584    SmallPrime {
2585        p: 2136143873,
2586        g: 1897347517,
2587        s: 293843959,
2588    },
2589    SmallPrime {
2590        p: 2136133633,
2591        g: 923586222,
2592        s: 1022655978,
2593    },
2594    SmallPrime {
2595        p: 2136096769,
2596        g: 1464868191,
2597        s: 1515074410,
2598    },
2599    SmallPrime {
2600        p: 2136094721,
2601        g: 2020679520,
2602        s: 2061636104,
2603    },
2604    SmallPrime {
2605        p: 2136076289,
2606        g: 290798503,
2607        s: 1814726809,
2608    },
2609    SmallPrime {
2610        p: 2136041473,
2611        g: 156415894,
2612        s: 1250757633,
2613    },
2614    SmallPrime {
2615        p: 2135996417,
2616        g: 297459940,
2617        s: 1132158924,
2618    },
2619    SmallPrime {
2620        p: 2135955457,
2621        g: 538755304,
2622        s: 1688831340,
2623    },
2624];
2625
2626static REV10: [u16; 1024] = [
2627    0, 512, 256, 768, 128, 640, 384, 896, 64, 576, 320, 832, 192, 704, 448, 960, 32, 544, 288, 800,
2628    160, 672, 416, 928, 96, 608, 352, 864, 224, 736, 480, 992, 16, 528, 272, 784, 144, 656, 400,
2629    912, 80, 592, 336, 848, 208, 720, 464, 976, 48, 560, 304, 816, 176, 688, 432, 944, 112, 624,
2630    368, 880, 240, 752, 496, 1008, 8, 520, 264, 776, 136, 648, 392, 904, 72, 584, 328, 840, 200,
2631    712, 456, 968, 40, 552, 296, 808, 168, 680, 424, 936, 104, 616, 360, 872, 232, 744, 488, 1000,
2632    24, 536, 280, 792, 152, 664, 408, 920, 88, 600, 344, 856, 216, 728, 472, 984, 56, 568, 312,
2633    824, 184, 696, 440, 952, 120, 632, 376, 888, 248, 760, 504, 1016, 4, 516, 260, 772, 132, 644,
2634    388, 900, 68, 580, 324, 836, 196, 708, 452, 964, 36, 548, 292, 804, 164, 676, 420, 932, 100,
2635    612, 356, 868, 228, 740, 484, 996, 20, 532, 276, 788, 148, 660, 404, 916, 84, 596, 340, 852,
2636    212, 724, 468, 980, 52, 564, 308, 820, 180, 692, 436, 948, 116, 628, 372, 884, 244, 756, 500,
2637    1012, 12, 524, 268, 780, 140, 652, 396, 908, 76, 588, 332, 844, 204, 716, 460, 972, 44, 556,
2638    300, 812, 172, 684, 428, 940, 108, 620, 364, 876, 236, 748, 492, 1004, 28, 540, 284, 796, 156,
2639    668, 412, 924, 92, 604, 348, 860, 220, 732, 476, 988, 60, 572, 316, 828, 188, 700, 444, 956,
2640    124, 636, 380, 892, 252, 764, 508, 1020, 2, 514, 258, 770, 130, 642, 386, 898, 66, 578, 322,
2641    834, 194, 706, 450, 962, 34, 546, 290, 802, 162, 674, 418, 930, 98, 610, 354, 866, 226, 738,
2642    482, 994, 18, 530, 274, 786, 146, 658, 402, 914, 82, 594, 338, 850, 210, 722, 466, 978, 50,
2643    562, 306, 818, 178, 690, 434, 946, 114, 626, 370, 882, 242, 754, 498, 1010, 10, 522, 266, 778,
2644    138, 650, 394, 906, 74, 586, 330, 842, 202, 714, 458, 970, 42, 554, 298, 810, 170, 682, 426,
2645    938, 106, 618, 362, 874, 234, 746, 490, 1002, 26, 538, 282, 794, 154, 666, 410, 922, 90, 602,
2646    346, 858, 218, 730, 474, 986, 58, 570, 314, 826, 186, 698, 442, 954, 122, 634, 378, 890, 250,
2647    762, 506, 1018, 6, 518, 262, 774, 134, 646, 390, 902, 70, 582, 326, 838, 198, 710, 454, 966,
2648    38, 550, 294, 806, 166, 678, 422, 934, 102, 614, 358, 870, 230, 742, 486, 998, 22, 534, 278,
2649    790, 150, 662, 406, 918, 86, 598, 342, 854, 214, 726, 470, 982, 54, 566, 310, 822, 182, 694,
2650    438, 950, 118, 630, 374, 886, 246, 758, 502, 1014, 14, 526, 270, 782, 142, 654, 398, 910, 78,
2651    590, 334, 846, 206, 718, 462, 974, 46, 558, 302, 814, 174, 686, 430, 942, 110, 622, 366, 878,
2652    238, 750, 494, 1006, 30, 542, 286, 798, 158, 670, 414, 926, 94, 606, 350, 862, 222, 734, 478,
2653    990, 62, 574, 318, 830, 190, 702, 446, 958, 126, 638, 382, 894, 254, 766, 510, 1022, 1, 513,
2654    257, 769, 129, 641, 385, 897, 65, 577, 321, 833, 193, 705, 449, 961, 33, 545, 289, 801, 161,
2655    673, 417, 929, 97, 609, 353, 865, 225, 737, 481, 993, 17, 529, 273, 785, 145, 657, 401, 913,
2656    81, 593, 337, 849, 209, 721, 465, 977, 49, 561, 305, 817, 177, 689, 433, 945, 113, 625, 369,
2657    881, 241, 753, 497, 1009, 9, 521, 265, 777, 137, 649, 393, 905, 73, 585, 329, 841, 201, 713,
2658    457, 969, 41, 553, 297, 809, 169, 681, 425, 937, 105, 617, 361, 873, 233, 745, 489, 1001, 25,
2659    537, 281, 793, 153, 665, 409, 921, 89, 601, 345, 857, 217, 729, 473, 985, 57, 569, 313, 825,
2660    185, 697, 441, 953, 121, 633, 377, 889, 249, 761, 505, 1017, 5, 517, 261, 773, 133, 645, 389,
2661    901, 69, 581, 325, 837, 197, 709, 453, 965, 37, 549, 293, 805, 165, 677, 421, 933, 101, 613,
2662    357, 869, 229, 741, 485, 997, 21, 533, 277, 789, 149, 661, 405, 917, 85, 597, 341, 853, 213,
2663    725, 469, 981, 53, 565, 309, 821, 181, 693, 437, 949, 117, 629, 373, 885, 245, 757, 501, 1013,
2664    13, 525, 269, 781, 141, 653, 397, 909, 77, 589, 333, 845, 205, 717, 461, 973, 45, 557, 301,
2665    813, 173, 685, 429, 941, 109, 621, 365, 877, 237, 749, 493, 1005, 29, 541, 285, 797, 157, 669,
2666    413, 925, 93, 605, 349, 861, 221, 733, 477, 989, 61, 573, 317, 829, 189, 701, 445, 957, 125,
2667    637, 381, 893, 253, 765, 509, 1021, 3, 515, 259, 771, 131, 643, 387, 899, 67, 579, 323, 835,
2668    195, 707, 451, 963, 35, 547, 291, 803, 163, 675, 419, 931, 99, 611, 355, 867, 227, 739, 483,
2669    995, 19, 531, 275, 787, 147, 659, 403, 915, 83, 595, 339, 851, 211, 723, 467, 979, 51, 563,
2670    307, 819, 179, 691, 435, 947, 115, 627, 371, 883, 243, 755, 499, 1011, 11, 523, 267, 779, 139,
2671    651, 395, 907, 75, 587, 331, 843, 203, 715, 459, 971, 43, 555, 299, 811, 171, 683, 427, 939,
2672    107, 619, 363, 875, 235, 747, 491, 1003, 27, 539, 283, 795, 155, 667, 411, 923, 91, 603, 347,
2673    859, 219, 731, 475, 987, 59, 571, 315, 827, 187, 699, 443, 955, 123, 635, 379, 891, 251, 763,
2674    507, 1019, 7, 519, 263, 775, 135, 647, 391, 903, 71, 583, 327, 839, 199, 711, 455, 967, 39,
2675    551, 295, 807, 167, 679, 423, 935, 103, 615, 359, 871, 231, 743, 487, 999, 23, 535, 279, 791,
2676    151, 663, 407, 919, 87, 599, 343, 855, 215, 727, 471, 983, 55, 567, 311, 823, 183, 695, 439,
2677    951, 119, 631, 375, 887, 247, 759, 503, 1015, 15, 527, 271, 783, 143, 655, 399, 911, 79, 591,
2678    335, 847, 207, 719, 463, 975, 47, 559, 303, 815, 175, 687, 431, 943, 111, 623, 367, 879, 239,
2679    751, 495, 1007, 31, 543, 287, 799, 159, 671, 415, 927, 95, 607, 351, 863, 223, 735, 479, 991,
2680    63, 575, 319, 831, 191, 703, 447, 959, 127, 639, 383, 895, 255, 767, 511, 1023,
2681];
2682
2683static GAUSS_1024_12289: [u64; 27] = [
2684    1283868770400643928,
2685    6416574995475331444,
2686    4078260278032692663,
2687    2353523259288686585,
2688    1227179971273316331,
2689    575931623374121527,
2690    242543240509105209,
2691    91437049221049666,
2692    30799446349977173,
2693    9255276791179340,
2694    2478152334826140,
2695    590642893610164,
2696    125206034929641,
2697    23590435911403,
2698    3948334035941,
2699    586753615614,
2700    77391054539,
2701    9056793210,
2702    940121950,
2703    86539696,
2704    7062824,
2705    510971,
2706    32764,
2707    1862,
2708    94,
2709    4,
2710    0,
2711];
2712
2713// ======================================================================
2714// Modular arithmetic (31-bit Montgomery)
2715// ======================================================================
2716
2717#[inline(always)]
2718fn modp_set(x: i32, p: u32) -> u32 {
2719    let mut w = x as u32;
2720    w = w.wrapping_add(p & (w >> 31).wrapping_neg());
2721    w
2722}
2723
2724#[inline(always)]
2725fn modp_norm(x: u32, p: u32) -> i32 {
2726    (x.wrapping_sub(p & (((x.wrapping_sub((p + 1) >> 1)) >> 31).wrapping_sub(1)))) as i32
2727}
2728
2729fn modp_ninv31(p: u32) -> u32 {
2730    let mut y = 2u32.wrapping_sub(p);
2731    y = y.wrapping_mul(2u32.wrapping_sub(p.wrapping_mul(y)));
2732    y = y.wrapping_mul(2u32.wrapping_sub(p.wrapping_mul(y)));
2733    y = y.wrapping_mul(2u32.wrapping_sub(p.wrapping_mul(y)));
2734    y = y.wrapping_mul(2u32.wrapping_sub(p.wrapping_mul(y)));
2735    0x7FFFFFFFu32 & y.wrapping_neg()
2736}
2737
2738#[inline(always)]
2739fn modp_r(p: u32) -> u32 {
2740    (1u32 << 31).wrapping_sub(p)
2741}
2742
2743#[inline(always)]
2744fn modp_add(a: u32, b: u32, p: u32) -> u32 {
2745    let mut d = a.wrapping_add(b).wrapping_sub(p);
2746    d = d.wrapping_add(p & (d >> 31).wrapping_neg());
2747    d
2748}
2749
2750#[inline(always)]
2751fn modp_sub(a: u32, b: u32, p: u32) -> u32 {
2752    let mut d = a.wrapping_sub(b);
2753    d = d.wrapping_add(p & (d >> 31).wrapping_neg());
2754    d
2755}
2756
2757#[inline(always)]
2758fn modp_montymul(a: u32, b: u32, p: u32, p0i: u32) -> u32 {
2759    let z = (a as u64).wrapping_mul(b as u64);
2760    let w = ((z.wrapping_mul(p0i as u64)) & 0x7FFFFFFF).wrapping_mul(p as u64);
2761    let mut d = ((z.wrapping_add(w)) >> 31) as u32;
2762    d = d.wrapping_sub(p);
2763    d = d.wrapping_add(p & (d >> 31).wrapping_neg());
2764    d
2765}
2766
2767fn modp_r2(p: u32, p0i: u32) -> u32 {
2768    let mut z = modp_r(p);
2769    z = modp_add(z, z, p);
2770    z = modp_montymul(z, z, p, p0i);
2771    z = modp_montymul(z, z, p, p0i);
2772    z = modp_montymul(z, z, p, p0i);
2773    z = modp_montymul(z, z, p, p0i);
2774    z = modp_montymul(z, z, p, p0i);
2775    z = (z.wrapping_add(p & (z & 1).wrapping_neg())) >> 1;
2776    z
2777}
2778
2779fn modp_rx(x: u32, p: u32, p0i: u32, r2: u32) -> u32 {
2780    let x = x.wrapping_sub(1);
2781    let mut r = r2;
2782    let mut z = modp_r(p);
2783    let mut i = 0u32;
2784    while (1u32 << i) <= x {
2785        if (x & (1u32 << i)) != 0 {
2786            z = modp_montymul(z, r, p, p0i);
2787        }
2788        r = modp_montymul(r, r, p, p0i);
2789        i += 1;
2790    }
2791    z
2792}
2793
2794fn modp_div(a: u32, b: u32, p: u32, p0i: u32, r: u32) -> u32 {
2795    let e = p.wrapping_sub(2);
2796    let mut z = r;
2797    for i in (0..=30i32).rev() {
2798        z = modp_montymul(z, z, p, p0i);
2799        let z2 = modp_montymul(z, b, p, p0i);
2800        z ^= (z ^ z2) & ((e >> i) & 1).wrapping_neg();
2801    }
2802    z = modp_montymul(z, 1, p, p0i);
2803    modp_montymul(a, z, p, p0i)
2804}
2805
2806// ======================================================================
2807// NTT
2808// ======================================================================
2809
2810fn modp_mkgm2(gm: &mut [u32], igm: &mut [u32], logn: u32, g: u32, p: u32, p0i: u32) {
2811    let n: usize = 1 << logn;
2812    let r2 = modp_r2(p, p0i);
2813    let mut g = modp_montymul(g, r2, p, p0i);
2814    for k in logn..10 {
2815        let _ = k;
2816        g = modp_montymul(g, g, p, p0i);
2817    }
2818    let ig = modp_div(r2, g, p, p0i, modp_r(p));
2819    let k = 10 - logn;
2820    let mut x1 = modp_r(p);
2821    let mut x2 = modp_r(p);
2822    for u in 0..n {
2823        let v = REV10[(u << k) as usize] as usize;
2824        gm[v] = x1;
2825        igm[v] = x2;
2826        x1 = modp_montymul(x1, g, p, p0i);
2827        x2 = modp_montymul(x2, ig, p, p0i);
2828    }
2829}
2830
2831fn modp_ntt2_ext(a: &mut [u32], stride: usize, gm: &[u32], logn: u32, p: u32, p0i: u32) {
2832    if logn == 0 {
2833        return;
2834    }
2835    let n: usize = 1 << logn;
2836    let mut t = n;
2837    let mut m: usize = 1;
2838    while m < n {
2839        let ht = t >> 1;
2840        let mut v1: usize = 0;
2841        for u in 0..m {
2842            let s = gm[m + u];
2843            let mut r1 = v1 * stride;
2844            let mut r2 = r1 + ht * stride;
2845            for _ in 0..ht {
2846                let x = a[r1];
2847                let y = modp_montymul(a[r2], s, p, p0i);
2848                a[r1] = modp_add(x, y, p);
2849                a[r2] = modp_sub(x, y, p);
2850                r1 += stride;
2851                r2 += stride;
2852            }
2853            v1 += t;
2854        }
2855        t = ht;
2856        m <<= 1;
2857    }
2858}
2859
2860fn modp_ntt2(a: &mut [u32], gm: &[u32], logn: u32, p: u32, p0i: u32) {
2861    modp_ntt2_ext(a, 1, gm, logn, p, p0i);
2862}
2863
2864fn modp_intt2_ext(a: &mut [u32], stride: usize, igm: &[u32], logn: u32, p: u32, p0i: u32) {
2865    if logn == 0 {
2866        return;
2867    }
2868    let n: usize = 1 << logn;
2869    let mut t: usize = 1;
2870    let mut m = n;
2871    while m > 1 {
2872        let hm = m >> 1;
2873        let dt = t << 1;
2874        let mut v1: usize = 0;
2875        for u in 0..hm {
2876            let s = igm[hm + u];
2877            let mut r1 = v1 * stride;
2878            let mut r2 = r1 + t * stride;
2879            for _ in 0..t {
2880                let x = a[r1];
2881                let y = a[r2];
2882                a[r1] = modp_add(x, y, p);
2883                a[r2] = modp_montymul(modp_sub(x, y, p), s, p, p0i);
2884                r1 += stride;
2885                r2 += stride;
2886            }
2887            v1 += dt;
2888        }
2889        t = dt;
2890        m = hm;
2891    }
2892    let ni = 1u32 << (31 - logn);
2893    let mut r = 0;
2894    for _ in 0..n {
2895        a[r] = modp_montymul(a[r], ni, p, p0i);
2896        r += stride;
2897    }
2898}
2899
2900fn modp_intt2(a: &mut [u32], igm: &[u32], logn: u32, p: u32, p0i: u32) {
2901    modp_intt2_ext(a, 1, igm, logn, p, p0i);
2902}
2903
2904fn modp_poly_rec_res(f: &mut [u32], logn: u32, p: u32, p0i: u32, r2: u32) {
2905    let hn: usize = 1 << (logn - 1);
2906    for u in 0..hn {
2907        let w0 = f[(u << 1) + 0];
2908        let w1 = f[(u << 1) + 1];
2909        f[u] = modp_montymul(modp_montymul(w0, w1, p, p0i), r2, p, p0i);
2910    }
2911}
2912
2913// ======================================================================
2914// Bignum operations
2915// ======================================================================
2916
2917fn zint_sub(a: &mut [u32], b: &[u32], len: usize, ctl: u32) -> u32 {
2918    let mut cc: u32 = 0;
2919    let m = ctl.wrapping_neg();
2920    for u in 0..len {
2921        let aw = a[u];
2922        let w = aw.wrapping_sub(b[u]).wrapping_sub(cc);
2923        cc = w >> 31;
2924        a[u] = aw ^ (((w & 0x7FFFFFFF) ^ aw) & m);
2925    }
2926    cc
2927}
2928
2929fn zint_mul_small(m: &mut [u32], mlen: usize, x: u32) -> u32 {
2930    let mut cc: u32 = 0;
2931    for u in 0..mlen {
2932        let z = (m[u] as u64).wrapping_mul(x as u64).wrapping_add(cc as u64);
2933        m[u] = (z as u32) & 0x7FFFFFFF;
2934        cc = (z >> 31) as u32;
2935    }
2936    cc
2937}
2938
2939fn zint_mod_small_unsigned(d: &[u32], dlen: usize, p: u32, p0i: u32, r2: u32) -> u32 {
2940    let mut x: u32 = 0;
2941    let mut u = dlen;
2942    while u > 0 {
2943        u -= 1;
2944        x = modp_montymul(x, r2, p, p0i);
2945        let mut w = d[u].wrapping_sub(p);
2946        w = w.wrapping_add(p & (w >> 31).wrapping_neg());
2947        x = modp_add(x, w, p);
2948    }
2949    x
2950}
2951
2952fn zint_mod_small_signed(d: &[u32], dlen: usize, p: u32, p0i: u32, r2: u32, rx: u32) -> u32 {
2953    if dlen == 0 {
2954        return 0;
2955    }
2956    let z = zint_mod_small_unsigned(d, dlen, p, p0i, r2);
2957    modp_sub(z, rx & (d[dlen - 1] >> 30).wrapping_neg(), p)
2958}
2959
2960fn zint_add_mul_small(x: &mut [u32], y: &[u32], len: usize, s: u32) {
2961    let mut cc: u32 = 0;
2962    for u in 0..len {
2963        let z = (y[u] as u64)
2964            .wrapping_mul(s as u64)
2965            .wrapping_add(x[u] as u64)
2966            .wrapping_add(cc as u64);
2967        x[u] = (z as u32) & 0x7FFFFFFF;
2968        cc = (z >> 31) as u32;
2969    }
2970    x[len] = cc;
2971}
2972
2973fn zint_norm_zero(x: &mut [u32], p: &[u32], len: usize) {
2974    let mut r: u32 = 0;
2975    let mut bb: u32 = 0;
2976    let mut u = len;
2977    while u > 0 {
2978        u -= 1;
2979        let wx = x[u];
2980        let wp = (p[u] >> 1) | (bb << 30);
2981        bb = p[u] & 1;
2982        let mut cc = wp.wrapping_sub(wx);
2983        cc = (cc.wrapping_neg() >> 31) | (cc >> 31).wrapping_neg();
2984        r |= cc & ((r & 1).wrapping_sub(1));
2985    }
2986    zint_sub(x, p, len, r >> 31);
2987}
2988
2989fn zint_rebuild_crt(
2990    xx: &mut [u32],
2991    xlen: usize,
2992    xstride: usize,
2993    num: usize,
2994    primes: &[SmallPrime],
2995    normalize_signed: bool,
2996    tmp: &mut [u32],
2997) {
2998    tmp[0] = primes[0].p;
2999    for u in 1..xlen {
3000        let p = primes[u].p;
3001        let s = primes[u].s;
3002        let p0i = modp_ninv31(p);
3003        let r2 = modp_r2(p, p0i);
3004        for v in 0..num {
3005            let x_off = v * xstride;
3006            let xp = xx[x_off + u];
3007            let xq = zint_mod_small_unsigned(&xx[x_off..], u, p, p0i, r2);
3008            let xr = modp_montymul(s, modp_sub(xp, xq, p), p, p0i);
3009            // zint_add_mul_small on x[x_off..], tmp, u, xr
3010            let mut cc: u32 = 0;
3011            for i in 0..u {
3012                let z = (tmp[i] as u64)
3013                    .wrapping_mul(xr as u64)
3014                    .wrapping_add(xx[x_off + i] as u64)
3015                    .wrapping_add(cc as u64);
3016                xx[x_off + i] = (z as u32) & 0x7FFFFFFF;
3017                cc = (z >> 31) as u32;
3018            }
3019            xx[x_off + u] = cc;
3020        }
3021        tmp[u] = zint_mul_small(tmp, u, p);
3022    }
3023    if normalize_signed {
3024        for u in 0..num {
3025            let x_off = u * xstride;
3026            // zint_norm_zero inline
3027            let mut r: u32 = 0;
3028            let mut bb: u32 = 0;
3029            let mut j = xlen;
3030            while j > 0 {
3031                j -= 1;
3032                let wx = xx[x_off + j];
3033                let wp = (tmp[j] >> 1) | (bb << 30);
3034                bb = tmp[j] & 1;
3035                let mut cc = wp.wrapping_sub(wx);
3036                cc = (cc.wrapping_neg() >> 31) | (cc >> 31).wrapping_neg();
3037                r |= cc & ((r & 1).wrapping_sub(1));
3038            }
3039            // zint_sub if r >> 31
3040            let ctl = r >> 31;
3041            let m = ctl.wrapping_neg();
3042            let mut ccc: u32 = 0;
3043            for j in 0..xlen {
3044                let aw = xx[x_off + j];
3045                let w = aw.wrapping_sub(tmp[j]).wrapping_sub(ccc);
3046                ccc = w >> 31;
3047                xx[x_off + j] = aw ^ (((w & 0x7FFFFFFF) ^ aw) & m);
3048            }
3049        }
3050    }
3051}
3052
3053fn zint_negate(a: &mut [u32], len: usize, ctl: u32) {
3054    let mut cc = ctl;
3055    let m = ctl.wrapping_neg() >> 1;
3056    for u in 0..len {
3057        let aw = (a[u] ^ m).wrapping_add(cc);
3058        a[u] = aw & 0x7FFFFFFF;
3059        cc = aw >> 31;
3060    }
3061}
3062
3063fn zint_co_reduce(
3064    a: &mut [u32],
3065    b: &mut [u32],
3066    len: usize,
3067    xa: i64,
3068    xb: i64,
3069    ya: i64,
3070    yb: i64,
3071) -> u32 {
3072    let mut cca: i64 = 0;
3073    let mut ccb: i64 = 0;
3074    for u in 0..len {
3075        let wa = a[u] as u64;
3076        let wb = b[u] as u64;
3077        let za = (wa as i64)
3078            .wrapping_mul(xa)
3079            .wrapping_add((wb as i64).wrapping_mul(xb))
3080            .wrapping_add(cca);
3081        let zb = (wa as i64)
3082            .wrapping_mul(ya)
3083            .wrapping_add((wb as i64).wrapping_mul(yb))
3084            .wrapping_add(ccb);
3085        if u > 0 {
3086            a[u - 1] = (za as u32) & 0x7FFFFFFF;
3087            b[u - 1] = (zb as u32) & 0x7FFFFFFF;
3088        }
3089        cca = za >> 31;
3090        ccb = zb >> 31;
3091    }
3092    a[len - 1] = cca as u32;
3093    b[len - 1] = ccb as u32;
3094    let nega = ((cca as u64) >> 63) as u32;
3095    let negb = ((ccb as u64) >> 63) as u32;
3096    zint_negate(a, len, nega);
3097    zint_negate(b, len, negb);
3098    nega | (negb << 1)
3099}
3100
3101fn zint_finish_mod(a: &mut [u32], len: usize, m: &[u32], neg: u32) {
3102    let mut cc: u32 = 0;
3103    for u in 0..len {
3104        cc = (a[u].wrapping_sub(m[u]).wrapping_sub(cc)) >> 31;
3105    }
3106    let xm = neg.wrapping_neg() >> 1;
3107    let ym = (neg | (1u32.wrapping_sub(cc))).wrapping_neg();
3108    cc = neg;
3109    for u in 0..len {
3110        let aw = a[u];
3111        let mw = (m[u] ^ xm) & ym;
3112        let w = aw.wrapping_sub(mw).wrapping_sub(cc);
3113        a[u] = w & 0x7FFFFFFF;
3114        cc = w >> 31;
3115    }
3116}
3117
3118fn zint_co_reduce_mod(
3119    a: &mut [u32],
3120    b: &mut [u32],
3121    m: &[u32],
3122    len: usize,
3123    m0i: u32,
3124    xa: i64,
3125    xb: i64,
3126    ya: i64,
3127    yb: i64,
3128) {
3129    let fa = ((a[0]
3130        .wrapping_mul(xa as u32)
3131        .wrapping_add(b[0].wrapping_mul(xb as u32)))
3132    .wrapping_mul(m0i))
3133        & 0x7FFFFFFF;
3134    let fb = ((a[0]
3135        .wrapping_mul(ya as u32)
3136        .wrapping_add(b[0].wrapping_mul(yb as u32)))
3137    .wrapping_mul(m0i))
3138        & 0x7FFFFFFF;
3139    let mut cca: i64 = 0;
3140    let mut ccb: i64 = 0;
3141    for u in 0..len {
3142        let wa = a[u] as u64;
3143        let wb = b[u] as u64;
3144        let za = (wa as i64)
3145            .wrapping_mul(xa)
3146            .wrapping_add((wb as i64).wrapping_mul(xb))
3147            .wrapping_add((m[u] as i64).wrapping_mul(fa as i64))
3148            .wrapping_add(cca);
3149        let zb = (wa as i64)
3150            .wrapping_mul(ya)
3151            .wrapping_add((wb as i64).wrapping_mul(yb))
3152            .wrapping_add((m[u] as i64).wrapping_mul(fb as i64))
3153            .wrapping_add(ccb);
3154        if u > 0 {
3155            a[u - 1] = (za as u32) & 0x7FFFFFFF;
3156            b[u - 1] = (zb as u32) & 0x7FFFFFFF;
3157        }
3158        cca = za >> 31;
3159        ccb = zb >> 31;
3160    }
3161    a[len - 1] = cca as u32;
3162    b[len - 1] = ccb as u32;
3163    zint_finish_mod(a, len, m, ((cca as u64) >> 63) as u32);
3164    zint_finish_mod(b, len, m, ((ccb as u64) >> 63) as u32);
3165}
3166
3167fn zint_bezout(
3168    u_out: &mut [u32],
3169    v_out: &mut [u32],
3170    x: &[u32],
3171    y: &[u32],
3172    len: usize,
3173    tmp: &mut [u32],
3174) -> bool {
3175    if len == 0 {
3176        return false;
3177    }
3178    let u0 = u_out;
3179    let v0 = v_out;
3180    let (u1, rest) = tmp.split_at_mut(len);
3181    let (v1, rest) = rest.split_at_mut(len);
3182    let (a, rest) = rest.split_at_mut(len);
3183    let (b, _) = rest.split_at_mut(len);
3184
3185    let x0i = modp_ninv31(x[0]);
3186    let y0i = modp_ninv31(y[0]);
3187
3188    a.copy_from_slice(&x[..len]);
3189    b.copy_from_slice(&y[..len]);
3190    u0[0] = 1;
3191    for i in 1..len {
3192        u0[i] = 0;
3193    }
3194    for i in 0..len {
3195        v0[i] = 0;
3196    }
3197    u1.copy_from_slice(&y[..len]);
3198    v1.copy_from_slice(&x[..len]);
3199    v1[0] -= 1;
3200
3201    let mut num = 62 * (len as u32) + 30;
3202    while num >= 30 {
3203        let mut c0: u32 = u32::MAX;
3204        let mut c1: u32 = u32::MAX;
3205        let mut a0: u32 = 0;
3206        let mut a1: u32 = 0;
3207        let mut b0: u32 = 0;
3208        let mut b1: u32 = 0;
3209        let mut j = len;
3210        while j > 0 {
3211            j -= 1;
3212            let aw = a[j];
3213            let bw = b[j];
3214            a0 ^= (a0 ^ aw) & c0;
3215            a1 ^= (a1 ^ aw) & c1;
3216            b0 ^= (b0 ^ bw) & c0;
3217            b1 ^= (b1 ^ bw) & c1;
3218            c1 = c0;
3219            c0 &= (((aw | bw).wrapping_add(0x7FFFFFFF)) >> 31).wrapping_sub(1);
3220        }
3221        a1 |= a0 & c1;
3222        a0 &= !c1;
3223        b1 |= b0 & c1;
3224        b0 &= !c1;
3225        let mut a_hi: u64 = ((a0 as u64) << 31) + a1 as u64;
3226        let mut b_hi: u64 = ((b0 as u64) << 31) + b1 as u64;
3227        let mut a_lo = a[0];
3228        let mut b_lo = b[0];
3229
3230        let mut pa: i64 = 1;
3231        let mut pb: i64 = 0;
3232        let mut qa: i64 = 0;
3233        let mut qb: i64 = 1;
3234        for i in 0..31u32 {
3235            let rz = b_hi.wrapping_sub(a_hi);
3236            let rt = ((rz ^ ((a_hi ^ b_hi) & (a_hi ^ rz))) >> 63) as u32;
3237            let oa = (a_lo >> i) & 1;
3238            let ob = (b_lo >> i) & 1;
3239            let c_ab = oa & ob & rt;
3240            let c_ba = oa & ob & !rt;
3241            let c_a = c_ab | (oa ^ 1);
3242
3243            a_lo = a_lo.wrapping_sub(b_lo & c_ab.wrapping_neg());
3244            a_hi = a_hi.wrapping_sub(b_hi & (c_ab as u64).wrapping_neg());
3245            pa -= qa & (c_ab as i64).wrapping_neg();
3246            pb -= qb & (c_ab as i64).wrapping_neg();
3247            b_lo = b_lo.wrapping_sub(a_lo & c_ba.wrapping_neg());
3248            b_hi = b_hi.wrapping_sub(a_hi & (c_ba as u64).wrapping_neg());
3249            qa -= pa & (c_ba as i64).wrapping_neg();
3250            qb -= pb & (c_ba as i64).wrapping_neg();
3251            a_lo = a_lo.wrapping_add(a_lo & c_a.wrapping_sub(1));
3252            a_hi ^= (a_hi ^ (a_hi >> 1)) & (c_a as u64).wrapping_neg();
3253            pa += pa & ((c_a as i64).wrapping_sub(1));
3254            pb += pb & ((c_a as i64).wrapping_sub(1));
3255            b_lo = b_lo.wrapping_add(b_lo & c_a.wrapping_neg());
3256            b_hi ^= (b_hi ^ (b_hi >> 1)) & ((c_a as u64).wrapping_sub(1));
3257            qa += qa & (c_a as i64).wrapping_neg();
3258            qb += qb & (c_a as i64).wrapping_neg();
3259        }
3260
3261        let r = zint_co_reduce(a, b, len, pa, pb, qa, qb);
3262        pa -= (pa + pa) & ((r & 1) as i64).wrapping_neg();
3263        pb -= (pb + pb) & ((r & 1) as i64).wrapping_neg();
3264        qa -= (qa + qa) & ((r >> 1) as i64).wrapping_neg();
3265        qb -= (qb + qb) & ((r >> 1) as i64).wrapping_neg();
3266        zint_co_reduce_mod(u0, u1, y, len, y0i, pa, pb, qa, qb);
3267        zint_co_reduce_mod(v0, v1, x, len, x0i, pa, pb, qa, qb);
3268
3269        num -= 30;
3270    }
3271
3272    let mut rc = a[0] ^ 1;
3273    for j in 1..len {
3274        rc |= a[j];
3275    }
3276    ((1u32.wrapping_sub((rc | rc.wrapping_neg()) >> 31)) & x[0] & y[0]) != 0
3277}
3278
3279fn zint_add_scaled_mul_small(
3280    x: &mut [u32],
3281    xlen: usize,
3282    y: &[u32],
3283    ylen: usize,
3284    k: i32,
3285    sch: u32,
3286    scl: u32,
3287) {
3288    if ylen == 0 {
3289        return;
3290    }
3291    let ysign = (y[ylen - 1] >> 30).wrapping_neg() >> 1;
3292    let mut tw: u32 = 0;
3293    let mut cc: i32 = 0;
3294    for u in (sch as usize)..xlen {
3295        let v = u - sch as usize;
3296        let wy = if v < ylen { y[v] } else { ysign };
3297        let wys = ((wy << scl) & 0x7FFFFFFF) | tw;
3298        tw = wy >> (31 - scl);
3299        let z = (wys as i64)
3300            .wrapping_mul(k as i64)
3301            .wrapping_add(x[u] as i64)
3302            .wrapping_add(cc as i64);
3303        x[u] = (z as u32) & 0x7FFFFFFF;
3304        cc = ((z as u64) >> 31) as i32;
3305    }
3306}
3307
3308fn zint_sub_scaled(x: &mut [u32], xlen: usize, y: &[u32], ylen: usize, sch: u32, scl: u32) {
3309    if ylen == 0 {
3310        return;
3311    }
3312    let ysign = (y[ylen - 1] >> 30).wrapping_neg() >> 1;
3313    let mut tw: u32 = 0;
3314    let mut cc: u32 = 0;
3315    for u in (sch as usize)..xlen {
3316        let v = u - sch as usize;
3317        let wy = if v < ylen { y[v] } else { ysign };
3318        let wys = ((wy << scl) & 0x7FFFFFFF) | tw;
3319        tw = wy >> (31 - scl);
3320        let w = x[u].wrapping_sub(wys).wrapping_sub(cc);
3321        x[u] = w & 0x7FFFFFFF;
3322        cc = w >> 31;
3323    }
3324}
3325
3326#[inline]
3327fn zint_one_to_plain(x: &[u32]) -> i32 {
3328    let mut w = x[0];
3329    w |= (w & 0x40000000) << 1;
3330    w as i32
3331}
3332
3333// ======================================================================
3334// Polynomial conversion utilities
3335// ======================================================================
3336
3337fn poly_big_to_fp(d: &mut [Fpr], f: &[u32], flen: usize, fstride: usize, logn: u32) {
3338    let n: usize = 1 << logn;
3339    if flen == 0 {
3340        for u in 0..n {
3341            d[u] = FPR_ZERO;
3342        }
3343        return;
3344    }
3345    for u in 0..n {
3346        let f_off = u * fstride;
3347        let neg = (f[f_off + flen - 1] >> 30).wrapping_neg();
3348        let xm = neg >> 1;
3349        let mut cc = neg & 1;
3350        let mut x = FPR_ZERO;
3351        let mut fsc = FPR_ONE;
3352        for v in 0..flen {
3353            let mut w = (f[f_off + v] ^ xm).wrapping_add(cc);
3354            cc = w >> 31;
3355            w &= 0x7FFFFFFF;
3356            w = w.wrapping_sub((w << 1) & neg);
3357            x = fpr_add(x, fpr_mul(fpr_of(w as i32 as i64), fsc));
3358            fsc = fpr_mul(fsc, FPR_PTWO31);
3359        }
3360        d[u] = x;
3361    }
3362}
3363
3364fn poly_big_to_small(d: &mut [i8], s: &[u32], lim: i32, logn: u32) -> bool {
3365    let n: usize = 1 << logn;
3366    for u in 0..n {
3367        let z = zint_one_to_plain(&s[u..]);
3368        if z < -lim || z > lim {
3369            return false;
3370        }
3371        d[u] = z as i8;
3372    }
3373    true
3374}
3375
3376fn poly_small_sqnorm(f: &[i8], logn: u32) -> u32 {
3377    let n: usize = 1 << logn;
3378    let mut s: u32 = 0;
3379    let mut ng: u32 = 0;
3380    for u in 0..n {
3381        let z = f[u] as i32;
3382        s = s.wrapping_add((z * z) as u32);
3383        ng |= s;
3384    }
3385    s | (ng >> 31).wrapping_neg()
3386}
3387
3388fn poly_small_to_fp(x: &mut [Fpr], f: &[i8], logn: u32) {
3389    let n: usize = 1 << logn;
3390    for u in 0..n {
3391        x[u] = fpr_of(f[u] as i64);
3392    }
3393}
3394
3395// ======================================================================
3396// Size tables for NTRU solver
3397// ======================================================================
3398
3399static MAX_BL_SMALL: [usize; 11] = [1, 1, 2, 2, 4, 7, 14, 27, 53, 106, 209];
3400static MAX_BL_LARGE: [usize; 10] = [2, 2, 5, 7, 12, 21, 40, 78, 157, 308];
3401
3402struct BitLength {
3403    avg: i32,
3404    std: i32,
3405}
3406
3407static BITLENGTH: [BitLength; 11] = [
3408    BitLength { avg: 4, std: 0 },
3409    BitLength { avg: 11, std: 1 },
3410    BitLength { avg: 24, std: 1 },
3411    BitLength { avg: 50, std: 1 },
3412    BitLength { avg: 102, std: 1 },
3413    BitLength { avg: 202, std: 2 },
3414    BitLength { avg: 401, std: 4 },
3415    BitLength { avg: 794, std: 5 },
3416    BitLength { avg: 1577, std: 8 },
3417    BitLength { avg: 3138, std: 13 },
3418    BitLength { avg: 6308, std: 25 },
3419];
3420
3421// ======================================================================
3422// Gaussian sampling for key generation
3423// ======================================================================
3424
3425/// Extract a 64-bit value from SHAKE256 in little-endian order,
3426/// matching the C reference's get_rng_u64() when FALCON_KG_CHACHA20=0.
3427fn get_rng_u64(rng: &mut InnerShake256Context) -> u64 {
3428    let mut tmp = [0u8; 8];
3429    crate::shake::i_shake256_extract(rng, &mut tmp);
3430    u64::from_le_bytes(tmp)
3431}
3432
3433fn mkgauss(rng: &mut InnerShake256Context, logn: u32) -> i32 {
3434    let g = 1u32 << (10 - logn);
3435    let mut val: i32 = 0;
3436    for _ in 0..g {
3437        let mut r = get_rng_u64(rng);
3438        let neg = (r >> 63) as u32;
3439        r &= !(1u64 << 63);
3440        let f_init = ((r.wrapping_sub(GAUSS_1024_12289[0])) >> 63) as u32;
3441
3442        let mut v: u32 = 0;
3443        let mut r2 = get_rng_u64(rng);
3444        r2 &= !(1u64 << 63);
3445        let mut f = f_init;
3446        for k in 1..GAUSS_1024_12289.len() {
3447            let t = (((r2.wrapping_sub(GAUSS_1024_12289[k])) >> 63) as u32) ^ 1;
3448            v |= (k as u32) & (t & (f ^ 1)).wrapping_neg();
3449            f |= t;
3450        }
3451
3452        v = (v ^ neg.wrapping_neg()).wrapping_add(neg);
3453        val += v as i32;
3454    }
3455    val
3456}
3457
3458fn poly_small_mkgauss(rng: &mut InnerShake256Context, f: &mut [i8], logn: u32) {
3459    let n: usize = 1 << logn;
3460    let mut mod2: u32 = 0;
3461    for u in 0..n {
3462        loop {
3463            let s = mkgauss(rng, logn);
3464            if s < -127 || s > 127 {
3465                continue;
3466            }
3467            if u == n - 1 {
3468                if (mod2 ^ (s as u32 & 1)) == 0 {
3469                    continue;
3470                }
3471            } else {
3472                mod2 ^= s as u32 & 1;
3473            }
3474            f[u] = s as i8;
3475            break;
3476        }
3477    }
3478}
3479
3480// ======================================================================
3481// NTRU solver stubs and main keygen
3482// (Full NTRU solver implementation is complex; providing the main
3483//  keygen entry point and solver framework)
3484// ======================================================================
3485
3486fn make_fg(data: &mut [u32], f: &[i8], g: &[i8], logn: u32, depth: u32, out_ntt: bool) {
3487    let n: usize = 1 << logn;
3488    let p0 = PRIMES[0].p;
3489    for u in 0..n {
3490        data[u] = modp_set(f[u] as i32, p0);
3491        data[n + u] = modp_set(g[u] as i32, p0);
3492    }
3493    if depth == 0 && out_ntt {
3494        let p = PRIMES[0].p;
3495        let p0i = modp_ninv31(p);
3496        let mut gm = vec![0u32; n];
3497        let mut igm = vec![0u32; n];
3498        modp_mkgm2(&mut gm, &mut igm, logn, PRIMES[0].g, p, p0i);
3499        modp_ntt2(&mut data[..n], &gm, logn, p, p0i);
3500        modp_ntt2(&mut data[n..2 * n], &gm, logn, p, p0i);
3501        return;
3502    }
3503    for d in 0..depth {
3504        make_fg_step(data, logn - d, d, d != 0, (d + 1) < depth || out_ntt);
3505    }
3506}
3507
3508fn make_fg_step(data: &mut [u32], logn: u32, depth: u32, in_ntt: bool, out_ntt: bool) {
3509    let n: usize = 1 << logn;
3510    let hn = n >> 1;
3511    let slen = MAX_BL_SMALL[depth as usize];
3512    let tlen = MAX_BL_SMALL[(depth + 1) as usize];
3513
3514    // This function operates in-place on data[] with complex memory layout.
3515    // For brevity, we use heap allocation for intermediate buffers.
3516    let mut fs = vec![0u32; 2 * n * slen];
3517    fs.copy_from_slice(&data[..2 * n * slen]);
3518
3519    let mut fd = vec![0u32; hn * tlen];
3520    let mut gd = vec![0u32; hn * tlen];
3521    let mut gm_buf = vec![0u32; n];
3522    let mut igm_buf = vec![0u32; n];
3523    let mut t1 = vec![0u32; core::cmp::max(n, slen)];
3524
3525    for u in 0..slen {
3526        let p = PRIMES[u].p;
3527        let p0i = modp_ninv31(p);
3528        let r2 = modp_r2(p, p0i);
3529        modp_mkgm2(&mut gm_buf, &mut igm_buf, logn, PRIMES[u].g, p, p0i);
3530
3531        // Extract f column u from fs
3532        for v in 0..n {
3533            t1[v] = fs[v * slen + u];
3534        }
3535        if !in_ntt {
3536            modp_ntt2(&mut t1, &gm_buf, logn, p, p0i);
3537        }
3538        for v in 0..hn {
3539            let w0 = t1[(v << 1) + 0];
3540            let w1 = t1[(v << 1) + 1];
3541            fd[v * tlen + u] = modp_montymul(modp_montymul(w0, w1, p, p0i), r2, p, p0i);
3542        }
3543        if in_ntt {
3544            // de-NTT the fs column
3545            for v in 0..n {
3546                t1[v] = fs[v * slen + u];
3547            }
3548            modp_intt2(&mut t1, &igm_buf, logn, p, p0i);
3549            for v in 0..n {
3550                fs[v * slen + u] = t1[v];
3551            }
3552        }
3553
3554        // Extract g column u from fs (second half)
3555        let g_base = n * slen;
3556        for v in 0..n {
3557            t1[v] = fs[g_base + v * slen + u];
3558        }
3559        if !in_ntt {
3560            modp_ntt2(&mut t1, &gm_buf, logn, p, p0i);
3561        }
3562        for v in 0..hn {
3563            let w0 = t1[(v << 1) + 0];
3564            let w1 = t1[(v << 1) + 1];
3565            gd[v * tlen + u] = modp_montymul(modp_montymul(w0, w1, p, p0i), r2, p, p0i);
3566        }
3567        if in_ntt {
3568            for v in 0..n {
3569                t1[v] = fs[g_base + v * slen + u];
3570            }
3571            modp_intt2(&mut t1, &igm_buf, logn, p, p0i);
3572            for v in 0..n {
3573                fs[g_base + v * slen + u] = t1[v];
3574            }
3575        }
3576
3577        if !out_ntt {
3578            // de-NTT fd and gd columns
3579            for v in 0..hn {
3580                t1[v] = fd[v * tlen + u];
3581            }
3582            modp_intt2(&mut t1[..hn], &igm_buf, logn - 1, p, p0i);
3583            for v in 0..hn {
3584                fd[v * tlen + u] = t1[v];
3585            }
3586
3587            for v in 0..hn {
3588                t1[v] = gd[v * tlen + u];
3589            }
3590            modp_intt2(&mut t1[..hn], &igm_buf, logn - 1, p, p0i);
3591            for v in 0..hn {
3592                gd[v * tlen + u] = t1[v];
3593            }
3594        }
3595    }
3596
3597    // CRT rebuild
3598    zint_rebuild_crt(&mut fs[..n * slen], slen, slen, n, &PRIMES, true, &mut t1);
3599    zint_rebuild_crt(&mut fs[n * slen..], slen, slen, n, &PRIMES, true, &mut t1);
3600
3601    // Remaining words: modular reductions
3602    for u in slen..tlen {
3603        let p = PRIMES[u].p;
3604        let p0i = modp_ninv31(p);
3605        let r2 = modp_r2(p, p0i);
3606        let rx = modp_rx(slen as u32, p, p0i, r2);
3607        modp_mkgm2(&mut gm_buf, &mut igm_buf, logn, PRIMES[u].g, p, p0i);
3608
3609        for v in 0..n {
3610            t1[v] = zint_mod_small_signed(&fs[v * slen..], slen, p, p0i, r2, rx);
3611        }
3612        modp_ntt2(&mut t1, &gm_buf, logn, p, p0i);
3613        for v in 0..hn {
3614            let w0 = t1[(v << 1) + 0];
3615            let w1 = t1[(v << 1) + 1];
3616            fd[v * tlen + u] = modp_montymul(modp_montymul(w0, w1, p, p0i), r2, p, p0i);
3617        }
3618
3619        let g_base = n * slen;
3620        for v in 0..n {
3621            t1[v] = zint_mod_small_signed(&fs[g_base + v * slen..], slen, p, p0i, r2, rx);
3622        }
3623        modp_ntt2(&mut t1, &gm_buf, logn, p, p0i);
3624        for v in 0..hn {
3625            let w0 = t1[(v << 1) + 0];
3626            let w1 = t1[(v << 1) + 1];
3627            gd[v * tlen + u] = modp_montymul(modp_montymul(w0, w1, p, p0i), r2, p, p0i);
3628        }
3629
3630        if !out_ntt {
3631            for v in 0..hn {
3632                t1[v] = fd[v * tlen + u];
3633            }
3634            modp_intt2(&mut t1[..hn], &igm_buf, logn - 1, p, p0i);
3635            for v in 0..hn {
3636                fd[v * tlen + u] = t1[v];
3637            }
3638
3639            for v in 0..hn {
3640                t1[v] = gd[v * tlen + u];
3641            }
3642            modp_intt2(&mut t1[..hn], &igm_buf, logn - 1, p, p0i);
3643            for v in 0..hn {
3644                gd[v * tlen + u] = t1[v];
3645            }
3646        }
3647    }
3648
3649    // Write results back
3650    let out_len = hn * tlen;
3651    data[..out_len].copy_from_slice(&fd);
3652    data[out_len..2 * out_len].copy_from_slice(&gd);
3653}
3654
3655fn poly_sub_scaled(
3656    f_data: &mut [u32],
3657    flen: usize,
3658    fstride: usize,
3659    f_src: &[u32],
3660    flen_src: usize,
3661    fstride_src: usize,
3662    k: &[i32],
3663    sch: u32,
3664    scl: u32,
3665    logn: u32,
3666) {
3667    let n: usize = 1 << logn;
3668    for u in 0..n {
3669        let mut kf = -k[u];
3670        let mut x_off = u * fstride;
3671        let mut y_off = 0usize;
3672        for v in 0..n {
3673            zint_add_scaled_mul_small(
3674                &mut f_data[x_off..],
3675                flen,
3676                &f_src[y_off..],
3677                flen_src,
3678                kf,
3679                sch,
3680                scl,
3681            );
3682            if u + v == n - 1 {
3683                x_off = 0;
3684                kf = -kf;
3685            } else {
3686                x_off += fstride;
3687            }
3688            y_off += fstride_src;
3689        }
3690    }
3691}
3692
3693fn poly_sub_scaled_ntt(
3694    f_data: &mut [u32],
3695    flen: usize,
3696    fstride: usize,
3697    f_src: &[u32],
3698    flen_src: usize,
3699    fstride_src: usize,
3700    k: &[i32],
3701    sch: u32,
3702    scl: u32,
3703    logn: u32,
3704    tmp: &mut [u32],
3705) {
3706    let n: usize = 1 << logn;
3707    let tlen = flen_src + 1;
3708
3709    // Layout in tmp: gm[n] igm[n] fk[n*tlen] t1[n]
3710    let _gm_off = 0;
3711    let _igm_off = n;
3712    let fk_off = 2 * n;
3713    let t1_off = fk_off + n * tlen;
3714
3715    for u in 0..tlen {
3716        let p = PRIMES[u].p;
3717        let p0i = modp_ninv31(p);
3718        let r2 = modp_r2(p, p0i);
3719        let rx = modp_rx(flen_src as u32, p, p0i, r2);
3720        {
3721            let (gm_s, rest) = tmp.split_at_mut(n);
3722            let igm_s = &mut rest[..n];
3723            modp_mkgm2(gm_s, igm_s, logn, PRIMES[u].g, p, p0i);
3724        }
3725
3726        // Set t1 to k modulo p
3727        for v in 0..n {
3728            tmp[t1_off + v] = modp_set(k[v], p);
3729        }
3730        {
3731            let (gm_part, rest) = tmp.split_at_mut(n);
3732            modp_ntt2(&mut rest[t1_off - n..t1_off - n + n], gm_part, logn, p, p0i);
3733        }
3734
3735        // Reduce f_src into fk
3736        for v in 0..n {
3737            tmp[fk_off + v * tlen + u] =
3738                zint_mod_small_signed(&f_src[v * fstride_src..], flen_src, p, p0i, r2, rx);
3739        }
3740
3741        // NTT of fk column
3742        {
3743            let (gm_part, rest) = tmp.split_at_mut(n);
3744            modp_ntt2_ext(&mut rest[fk_off - n + u..], tlen, gm_part, logn, p, p0i);
3745        }
3746
3747        // Pointwise multiply
3748        for v in 0..n {
3749            let t1_val = tmp[t1_off + v];
3750            let fk_val = tmp[fk_off + v * tlen + u];
3751            tmp[fk_off + v * tlen + u] =
3752                modp_montymul(modp_montymul(t1_val, fk_val, p, p0i), r2, p, p0i);
3753        }
3754
3755        // Inverse NTT
3756        {
3757            let (_, rest) = tmp.split_at_mut(n);
3758            let igm_s = rest[..n].to_vec();
3759            modp_intt2_ext(&mut rest[fk_off - n + u..], tlen, &igm_s, logn, p, p0i);
3760        }
3761    }
3762
3763    // Rebuild CRT
3764    {
3765        let mut t1_buf = vec![0u32; n + tlen];
3766        zint_rebuild_crt(
3767            &mut tmp[fk_off..],
3768            tlen,
3769            tlen,
3770            n,
3771            &PRIMES,
3772            true,
3773            &mut t1_buf,
3774        );
3775    }
3776
3777    // Subtract scaled
3778    for u in 0..n {
3779        zint_sub_scaled(
3780            &mut f_data[u * fstride..],
3781            flen,
3782            &tmp[fk_off + u * tlen..],
3783            tlen,
3784            sch,
3785            scl,
3786        );
3787    }
3788}
3789
3790fn solve_ntru_deepest(logn_top: u32, f: &[i8], g: &[i8], tmp: &mut [u32]) -> bool {
3791    let len = MAX_BL_SMALL[logn_top as usize];
3792
3793    // Layout: Fp[len] Gp[len] fp[len] gp[len] t1[...]
3794    let mut buf = vec![0u32; 5 * len + 2 * (1 << logn_top)];
3795    make_fg(&mut buf[2 * len..], f, g, logn_top, logn_top, false);
3796
3797    // CRT rebuild
3798    let mut t1 = vec![0u32; len + 1];
3799    zint_rebuild_crt(&mut buf[2 * len..], len, len, 2, &PRIMES, false, &mut t1);
3800
3801    // Binary GCD
3802    let mut fp = vec![0u32; len];
3803    let mut gp = vec![0u32; len];
3804    fp.copy_from_slice(&buf[2 * len..3 * len]);
3805    gp.copy_from_slice(&buf[3 * len..4 * len]);
3806
3807    let fp_ref = fp.clone();
3808    let gp_ref = gp.clone();
3809    let mut u_buf = vec![0u32; len]; // Gp
3810    let mut v_buf = vec![0u32; len]; // Fp
3811    let mut bez_tmp = vec![0u32; 4 * len];
3812
3813    if !zint_bezout(&mut u_buf, &mut v_buf, &fp_ref, &gp_ref, len, &mut bez_tmp) {
3814        return false;
3815    }
3816
3817    // Multiply by q = 12289
3818    if zint_mul_small(&mut v_buf, len, 12289) != 0 {
3819        return false;
3820    }
3821    if zint_mul_small(&mut u_buf, len, 12289) != 0 {
3822        return false;
3823    }
3824
3825    // Store Fp, Gp in tmp
3826    tmp[..len].copy_from_slice(&v_buf);
3827    tmp[len..2 * len].copy_from_slice(&u_buf);
3828    true
3829}
3830
3831fn solve_ntru_intermediate(logn_top: u32, f: &[i8], g: &[i8], depth: u32, tmp: &mut [u32]) -> bool {
3832    let logn = logn_top - depth;
3833    let n: usize = 1 << logn;
3834    let hn = n >> 1;
3835
3836    let slen = MAX_BL_SMALL[depth as usize];
3837    let dlen = MAX_BL_SMALL[(depth + 1) as usize];
3838    let llen = MAX_BL_LARGE[depth as usize];
3839
3840    // Save Fd, Gd from tmp
3841    let fd_gd_len = 2 * hn * dlen;
3842    let mut fd_gd = vec![0u32; fd_gd_len];
3843    fd_gd.copy_from_slice(&tmp[..fd_gd_len]);
3844
3845    // Compute f, g at this depth
3846    let n_top: usize = 1 << logn_top;
3847    let fg_step_size = 2 * n * slen + 4 * n;
3848    let fg_init_size = 2 * n_top;
3849    let mut fg_buf = vec![0u32; core::cmp::max(fg_step_size, fg_init_size)];
3850    make_fg(&mut fg_buf, f, g, logn_top, depth, true);
3851
3852    // Working arrays
3853    let mut ft_buf = vec![0u32; n * llen]; // for F
3854    let mut gt_buf = vec![0u32; n * llen]; // for G
3855
3856    // Reduce Fd, Gd modulo small primes into Ft, Gt
3857    for u in 0..llen {
3858        let p = PRIMES[u].p;
3859        let p0i = modp_ninv31(p);
3860        let r2 = modp_r2(p, p0i);
3861        let rx = modp_rx(dlen as u32, p, p0i, r2);
3862        for v in 0..hn {
3863            ft_buf[v * llen + u] = zint_mod_small_signed(&fd_gd[v * dlen..], dlen, p, p0i, r2, rx);
3864            gt_buf[v * llen + u] =
3865                zint_mod_small_signed(&fd_gd[hn * dlen + v * dlen..], dlen, p, p0i, r2, rx);
3866        }
3867    }
3868
3869    // Compute F and G modulo small primes
3870    let mut fg_rns = fg_buf.clone(); // f,g in RNS
3871    for u in 0..llen {
3872        let p = PRIMES[u].p;
3873        let p0i = modp_ninv31(p);
3874        let r2 = modp_r2(p, p0i);
3875
3876        if u == slen {
3877            let mut crt_tmp = vec![0u32; n + slen];
3878            zint_rebuild_crt(
3879                &mut fg_rns[..n * slen],
3880                slen,
3881                slen,
3882                n,
3883                &PRIMES,
3884                true,
3885                &mut crt_tmp,
3886            );
3887            zint_rebuild_crt(
3888                &mut fg_rns[n * slen..],
3889                slen,
3890                slen,
3891                n,
3892                &PRIMES,
3893                true,
3894                &mut crt_tmp,
3895            );
3896        }
3897
3898        let mut gm = vec![0u32; n];
3899        let mut igm = vec![0u32; n];
3900        modp_mkgm2(&mut gm, &mut igm, logn, PRIMES[u].g, p, p0i);
3901
3902        let mut fx = vec![0u32; n];
3903        let mut gx = vec![0u32; n];
3904
3905        if u < slen {
3906            for v in 0..n {
3907                fx[v] = fg_rns[v * slen + u];
3908                gx[v] = fg_rns[n * slen + v * slen + u];
3909            }
3910            // De-NTT the column in fg_rns
3911            let mut col_f = vec![0u32; n];
3912            let mut col_g = vec![0u32; n];
3913            for v in 0..n {
3914                col_f[v] = fg_rns[v * slen + u];
3915            }
3916            for v in 0..n {
3917                col_g[v] = fg_rns[n * slen + v * slen + u];
3918            }
3919            modp_intt2(&mut col_f, &igm, logn, p, p0i);
3920            modp_intt2(&mut col_g, &igm, logn, p, p0i);
3921            for v in 0..n {
3922                fg_rns[v * slen + u] = col_f[v];
3923            }
3924            for v in 0..n {
3925                fg_rns[n * slen + v * slen + u] = col_g[v];
3926            }
3927        } else {
3928            let rx = modp_rx(slen as u32, p, p0i, r2);
3929            for v in 0..n {
3930                fx[v] = zint_mod_small_signed(&fg_rns[v * slen..], slen, p, p0i, r2, rx);
3931                gx[v] = zint_mod_small_signed(&fg_rns[n * slen + v * slen..], slen, p, p0i, r2, rx);
3932            }
3933            modp_ntt2(&mut fx, &gm, logn, p, p0i);
3934            modp_ntt2(&mut gx, &gm, logn, p, p0i);
3935        }
3936
3937        // Get Fp, Gp from Ft, Gt
3938        let mut fp_arr = vec![0u32; hn];
3939        let mut gp_arr = vec![0u32; hn];
3940        for v in 0..hn {
3941            fp_arr[v] = ft_buf[v * llen + u];
3942            gp_arr[v] = gt_buf[v * llen + u];
3943        }
3944        modp_ntt2(&mut fp_arr, &gm, logn - 1, p, p0i);
3945        modp_ntt2(&mut gp_arr, &gm, logn - 1, p, p0i);
3946
3947        // Compute F and G: F = F'(x^2) * adj(g), G = G'(x^2) * adj(f)
3948        for v in 0..hn {
3949            let ft_a = fx[(v << 1) + 0];
3950            let ft_b = fx[(v << 1) + 1];
3951            let gt_a = gx[(v << 1) + 0];
3952            let gt_b = gx[(v << 1) + 1];
3953            let m_fp = modp_montymul(fp_arr[v], r2, p, p0i);
3954            let m_gp = modp_montymul(gp_arr[v], r2, p, p0i);
3955            ft_buf[v * 2 * llen + u] = modp_montymul(gt_b, m_fp, p, p0i);
3956            ft_buf[(v * 2 + 1) * llen + u] = modp_montymul(gt_a, m_fp, p, p0i);
3957            gt_buf[v * 2 * llen + u] = modp_montymul(ft_b, m_gp, p, p0i);
3958            gt_buf[(v * 2 + 1) * llen + u] = modp_montymul(ft_a, m_gp, p, p0i);
3959        }
3960
3961        // Inverse NTT on Ft, Gt columns
3962        let mut col = vec![0u32; n];
3963        for v in 0..n {
3964            col[v] = ft_buf[v * llen + u];
3965        }
3966        modp_intt2(&mut col, &igm, logn, p, p0i);
3967        for v in 0..n {
3968            ft_buf[v * llen + u] = col[v];
3969        }
3970
3971        for v in 0..n {
3972            col[v] = gt_buf[v * llen + u];
3973        }
3974        modp_intt2(&mut col, &igm, logn, p, p0i);
3975        for v in 0..n {
3976            gt_buf[v * llen + u] = col[v];
3977        }
3978    }
3979
3980    // Rebuild CRT for F and G
3981    {
3982        let mut crt_tmp = vec![0u32; n + llen];
3983        zint_rebuild_crt(&mut ft_buf, llen, llen, n, &PRIMES, true, &mut crt_tmp);
3984        zint_rebuild_crt(&mut gt_buf, llen, llen, n, &PRIMES, true, &mut crt_tmp);
3985    }
3986
3987    // Rebuild CRT for f, g if not done yet
3988    if slen >= llen {
3989        let mut crt_tmp = vec![0u32; n + slen];
3990        zint_rebuild_crt(
3991            &mut fg_rns[..n * slen],
3992            slen,
3993            slen,
3994            n,
3995            &PRIMES,
3996            true,
3997            &mut crt_tmp,
3998        );
3999        zint_rebuild_crt(
4000            &mut fg_rns[n * slen..],
4001            slen,
4002            slen,
4003            n,
4004            &PRIMES,
4005            true,
4006            &mut crt_tmp,
4007        );
4008    }
4009
4010    // Babai reduction
4011    let rlen = if slen > 10 { 10 } else { slen };
4012    let scale_fg = 31 * (slen as i32 - rlen as i32);
4013
4014    let mut rt3 = vec![FPR_ZERO; n];
4015    let mut rt4 = vec![FPR_ZERO; n];
4016    let mut rt5 = vec![FPR_ZERO; n]; // only n/2 used
4017
4018    // Convert f, g to FP
4019    poly_big_to_fp(&mut rt3, &fg_rns[slen - rlen..], rlen, slen, logn);
4020    poly_big_to_fp(
4021        &mut rt4,
4022        &fg_rns[n * slen + slen - rlen..],
4023        rlen,
4024        slen,
4025        logn,
4026    );
4027
4028    let minbl_fg = BITLENGTH[depth as usize].avg - 6 * BITLENGTH[depth as usize].std;
4029    let maxbl_fg = BITLENGTH[depth as usize].avg + 6 * BITLENGTH[depth as usize].std;
4030
4031    fft::fft(&mut rt3, logn);
4032    fft::fft(&mut rt4, logn);
4033    fft::poly_invnorm2_fft(&mut rt5, &rt3, &rt4, logn);
4034    fft::poly_adj_fft(&mut rt3, logn);
4035    fft::poly_adj_fft(&mut rt4, logn);
4036
4037    let mut fg_len = llen;
4038    let mut maxbl_fg_val = 31 * llen as i32;
4039    let mut scale_k = maxbl_fg_val - minbl_fg;
4040
4041    loop {
4042        let rlen2 = if fg_len > 10 { 10 } else { fg_len };
4043        let scale_fg2 = 31 * (fg_len as i32 - rlen2 as i32);
4044
4045        let mut rt1 = vec![FPR_ZERO; n];
4046        let mut rt2 = vec![FPR_ZERO; n];
4047
4048        poly_big_to_fp(&mut rt1, &ft_buf[fg_len - rlen2..], rlen2, llen, logn);
4049        poly_big_to_fp(&mut rt2, &gt_buf[fg_len - rlen2..], rlen2, llen, logn);
4050
4051        fft::fft(&mut rt1, logn);
4052        fft::fft(&mut rt2, logn);
4053        fft::poly_mul_fft(&mut rt1, &rt3, logn);
4054        fft::poly_mul_fft(&mut rt2, &rt4, logn);
4055        fft::poly_add(&mut rt2, &rt1, logn);
4056        fft::poly_mul_autoadj_fft(&mut rt2, &rt5, logn);
4057        fft::ifft(&mut rt2, logn);
4058
4059        // Compute scaling factor
4060        let mut dc = scale_k - scale_fg2 + scale_fg;
4061        let pt_base;
4062        if dc < 0 {
4063            dc = -dc;
4064            pt_base = FPR_TWO;
4065        } else {
4066            pt_base = FPR_ONEHALF;
4067        }
4068        let mut pdc = FPR_ONE;
4069        let mut pt = pt_base;
4070        let mut dcc = dc;
4071        while dcc != 0 {
4072            if (dcc & 1) != 0 {
4073                pdc = fpr_mul(pdc, pt);
4074            }
4075            dcc >>= 1;
4076            pt = fpr_sqr(pt);
4077        }
4078
4079        let mut k_arr = vec![0i32; n];
4080        for u in 0..n {
4081            let xv = fpr_mul(rt2[u], pdc);
4082            if fpr_lt(FPR_MTWO31M1, xv) == 0 || fpr_lt(xv, FPR_PTWO31M1) == 0 {
4083                return false;
4084            }
4085            k_arr[u] = fpr_rint(xv) as i32;
4086        }
4087
4088        let sch = (scale_k / 31) as u32;
4089        let scl = (scale_k % 31) as u32;
4090
4091        if depth <= DEPTH_INT_FG {
4092            let mut sub_tmp = vec![0u32; 4 * n + 2 * n * (slen + 1)];
4093            poly_sub_scaled_ntt(
4094                &mut ft_buf,
4095                fg_len,
4096                llen,
4097                &fg_rns[..n * slen],
4098                slen,
4099                slen,
4100                &k_arr,
4101                sch,
4102                scl,
4103                logn,
4104                &mut sub_tmp,
4105            );
4106            poly_sub_scaled_ntt(
4107                &mut gt_buf,
4108                fg_len,
4109                llen,
4110                &fg_rns[n * slen..],
4111                slen,
4112                slen,
4113                &k_arr,
4114                sch,
4115                scl,
4116                logn,
4117                &mut sub_tmp,
4118            );
4119        } else {
4120            poly_sub_scaled(
4121                &mut ft_buf,
4122                fg_len,
4123                llen,
4124                &fg_rns[..n * slen],
4125                slen,
4126                slen,
4127                &k_arr,
4128                sch,
4129                scl,
4130                logn,
4131            );
4132            poly_sub_scaled(
4133                &mut gt_buf,
4134                fg_len,
4135                llen,
4136                &fg_rns[n * slen..],
4137                slen,
4138                slen,
4139                &k_arr,
4140                sch,
4141                scl,
4142                logn,
4143            );
4144        }
4145
4146        let new_maxbl_fg = scale_k + maxbl_fg + 10;
4147        if new_maxbl_fg < maxbl_fg_val {
4148            maxbl_fg_val = new_maxbl_fg;
4149            if (fg_len as i32) * 31 >= maxbl_fg_val + 31 {
4150                fg_len -= 1;
4151            }
4152        }
4153
4154        if scale_k <= 0 {
4155            break;
4156        }
4157        scale_k -= 25;
4158        if scale_k < 0 {
4159            scale_k = 0;
4160        }
4161    }
4162
4163    // Sign-extend if FGlen < slen
4164    if fg_len < slen {
4165        for u in 0..n {
4166            let sw_f = (ft_buf[u * llen + fg_len - 1] >> 30).wrapping_neg() >> 1;
4167            for v in fg_len..slen {
4168                ft_buf[u * llen + v] = sw_f;
4169            }
4170            let sw_g = (gt_buf[u * llen + fg_len - 1] >> 30).wrapping_neg() >> 1;
4171            for v in fg_len..slen {
4172                gt_buf[u * llen + v] = sw_g;
4173            }
4174        }
4175    }
4176
4177    // Compress to slen stride and write to tmp
4178    for u in 0..n {
4179        tmp[u * slen..u * slen + slen].copy_from_slice(&ft_buf[u * llen..u * llen + slen]);
4180    }
4181    for u in 0..n {
4182        tmp[n * slen + u * slen..n * slen + u * slen + slen]
4183            .copy_from_slice(&gt_buf[u * llen..u * llen + slen]);
4184    }
4185
4186    true
4187}
4188
4189fn solve_ntru_binary_depth1(logn_top: u32, f: &[i8], g: &[i8], tmp: &mut [u32]) -> bool {
4190    let depth: u32 = 1;
4191    let n_top: usize = 1 << logn_top;
4192    let logn = logn_top - depth;
4193    let n: usize = 1 << logn;
4194    let hn = n >> 1;
4195
4196    let slen = MAX_BL_SMALL[depth as usize];
4197    let dlen = MAX_BL_SMALL[(depth + 1) as usize];
4198    let llen = MAX_BL_LARGE[depth as usize];
4199
4200    // Save Fd, Gd from tmp
4201    let mut fd = vec![0u32; hn * dlen];
4202    let mut gd = vec![0u32; hn * dlen];
4203    fd.copy_from_slice(&tmp[..hn * dlen]);
4204    gd.copy_from_slice(&tmp[hn * dlen..2 * hn * dlen]);
4205
4206    // Reduce Fd, Gd modulo primes into Ft, Gt
4207    let mut ft_buf = vec![0u32; n * llen];
4208    let mut gt_buf = vec![0u32; n * llen];
4209
4210    for u in 0..llen {
4211        let p = PRIMES[u].p;
4212        let p0i = modp_ninv31(p);
4213        let r2 = modp_r2(p, p0i);
4214        let rx = modp_rx(dlen as u32, p, p0i, r2);
4215        for v in 0..hn {
4216            ft_buf[v * llen + u] = zint_mod_small_signed(&fd[v * dlen..], dlen, p, p0i, r2, rx);
4217            gt_buf[v * llen + u] = zint_mod_small_signed(&gd[v * dlen..], dlen, p, p0i, r2, rx);
4218        }
4219    }
4220
4221    let mut ft_rns = vec![0u32; n * slen];
4222    let mut gt_rns = vec![0u32; n * slen];
4223
4224    // Compute F, G modulo primes
4225    for u in 0..llen {
4226        let p = PRIMES[u].p;
4227        let p0i = modp_ninv31(p);
4228        let r2 = modp_r2(p, p0i);
4229
4230        let mut gm = vec![0u32; n_top];
4231        let mut igm = vec![0u32; n_top];
4232        modp_mkgm2(&mut gm, &mut igm, logn_top, PRIMES[u].g, p, p0i);
4233
4234        let mut fx = vec![0u32; n_top];
4235        let mut gx = vec![0u32; n_top];
4236        for v in 0..n_top {
4237            fx[v] = modp_set(f[v] as i32, p);
4238            gx[v] = modp_set(g[v] as i32, p);
4239        }
4240        modp_ntt2(&mut fx, &gm, logn_top, p, p0i);
4241        modp_ntt2(&mut gx, &gm, logn_top, p, p0i);
4242
4243        let mut e = logn_top;
4244        while e > logn {
4245            modp_poly_rec_res(&mut fx, e, p, p0i, r2);
4246            modp_poly_rec_res(&mut gx, e, p, p0i, r2);
4247            e -= 1;
4248        }
4249
4250        // Re-arrange memory: shrink gm/igm to size n
4251        let igm_n = igm[..n].to_vec();
4252        let fx_n = fx[..n].to_vec();
4253        let gx_n = gx[..n].to_vec();
4254        let mut fx_work = fx_n;
4255        let mut gx_work = gx_n;
4256
4257        // Get Fp, Gp
4258        let mut fp_arr = vec![0u32; hn];
4259        let mut gp_arr = vec![0u32; hn];
4260        for v in 0..hn {
4261            fp_arr[v] = ft_buf[v * llen + u];
4262            gp_arr[v] = gt_buf[v * llen + u];
4263        }
4264        modp_ntt2(&mut fp_arr, &gm, logn - 1, p, p0i);
4265        modp_ntt2(&mut gp_arr, &gm, logn - 1, p, p0i);
4266
4267        // Compute F and G
4268        for v in 0..hn {
4269            let ft_a = fx_work[(v << 1) + 0];
4270            let ft_b = fx_work[(v << 1) + 1];
4271            let gt_a = gx_work[(v << 1) + 0];
4272            let gt_b = gx_work[(v << 1) + 1];
4273            let m_fp = modp_montymul(fp_arr[v], r2, p, p0i);
4274            let m_gp = modp_montymul(gp_arr[v], r2, p, p0i);
4275            ft_buf[v * 2 * llen + u] = modp_montymul(gt_b, m_fp, p, p0i);
4276            ft_buf[(v * 2 + 1) * llen + u] = modp_montymul(gt_a, m_fp, p, p0i);
4277            gt_buf[v * 2 * llen + u] = modp_montymul(ft_b, m_gp, p, p0i);
4278            gt_buf[(v * 2 + 1) * llen + u] = modp_montymul(ft_a, m_gp, p, p0i);
4279        }
4280
4281        // iNTT columns of Ft, Gt
4282        let mut col = vec![0u32; n];
4283        for v in 0..n {
4284            col[v] = ft_buf[v * llen + u];
4285        }
4286        modp_intt2(&mut col, &igm_n, logn, p, p0i);
4287        for v in 0..n {
4288            ft_buf[v * llen + u] = col[v];
4289        }
4290
4291        for v in 0..n {
4292            col[v] = gt_buf[v * llen + u];
4293        }
4294        modp_intt2(&mut col, &igm_n, logn, p, p0i);
4295        for v in 0..n {
4296            gt_buf[v * llen + u] = col[v];
4297        }
4298
4299        // Save f, g RNS
4300        if u < slen {
4301            modp_intt2(&mut fx_work, &igm_n, logn, p, p0i);
4302            modp_intt2(&mut gx_work, &igm_n, logn, p, p0i);
4303            for v in 0..n {
4304                ft_rns[v * slen + u] = fx_work[v];
4305                gt_rns[v * slen + u] = gx_work[v];
4306            }
4307        }
4308    }
4309
4310    // Rebuild CRT for F and G (separately since they're not contiguous)
4311    {
4312        let mut crt_tmp = vec![0u32; 2 * n + llen];
4313        zint_rebuild_crt(&mut ft_buf, llen, llen, n, &PRIMES, true, &mut crt_tmp);
4314        zint_rebuild_crt(&mut gt_buf, llen, llen, n, &PRIMES, true, &mut crt_tmp);
4315    }
4316    {
4317        let mut crt_tmp = vec![0u32; 2 * n + slen];
4318        // ft_rns and gt_rns together
4319        let mut fg_combined = vec![0u32; 2 * n * slen];
4320        fg_combined[..n * slen].copy_from_slice(&ft_rns);
4321        fg_combined[n * slen..].copy_from_slice(&gt_rns);
4322        zint_rebuild_crt(
4323            &mut fg_combined,
4324            slen,
4325            slen,
4326            n << 1,
4327            &PRIMES,
4328            true,
4329            &mut crt_tmp,
4330        );
4331        ft_rns.copy_from_slice(&fg_combined[..n * slen]);
4332        gt_rns.copy_from_slice(&fg_combined[n * slen..]);
4333    }
4334
4335    // Babai reduction (simplified for depth 1, single pass)
4336    let mut rt1 = vec![FPR_ZERO; n];
4337    let mut rt2 = vec![FPR_ZERO; n];
4338    poly_big_to_fp(&mut rt1, &ft_buf, llen, llen, logn);
4339    poly_big_to_fp(&mut rt2, &gt_buf, llen, llen, logn);
4340
4341    let mut rt3 = vec![FPR_ZERO; n];
4342    let mut rt4 = vec![FPR_ZERO; n];
4343    poly_big_to_fp(&mut rt3, &ft_rns, slen, slen, logn);
4344    poly_big_to_fp(&mut rt4, &gt_rns, slen, slen, logn);
4345
4346    fft::fft(&mut rt1, logn);
4347    fft::fft(&mut rt2, logn);
4348    fft::fft(&mut rt3, logn);
4349    fft::fft(&mut rt4, logn);
4350
4351    let mut rt5 = vec![FPR_ZERO; n];
4352    let mut rt6 = vec![FPR_ZERO; n];
4353    fft::poly_add_muladj_fft(&mut rt5, &rt1, &rt2, &rt3, &rt4, logn);
4354    fft::poly_invnorm2_fft(&mut rt6, &rt3, &rt4, logn);
4355    fft::poly_mul_autoadj_fft(&mut rt5, &rt6, logn);
4356
4357    fft::ifft(&mut rt5, logn);
4358    for u in 0..n {
4359        let z = rt5[u];
4360        if fpr_lt(z, FPR_PTWO63M1) == 0 || fpr_lt(FPR_MTWO63M1, z) == 0 {
4361            return false;
4362        }
4363        rt5[u] = fpr_of(fpr_rint(z));
4364    }
4365    fft::fft(&mut rt5, logn);
4366
4367    fft::poly_mul_fft(&mut rt3, &rt5, logn);
4368    fft::poly_mul_fft(&mut rt4, &rt5, logn);
4369    fft::poly_sub(&mut rt1, &rt3, logn);
4370    fft::poly_sub(&mut rt2, &rt4, logn);
4371    fft::ifft(&mut rt1, logn);
4372    fft::ifft(&mut rt2, logn);
4373
4374    // Convert back to integers
4375    for u in 0..n {
4376        tmp[u] = fpr_rint(rt1[u]) as u32;
4377    }
4378    for u in 0..n {
4379        tmp[n + u] = fpr_rint(rt2[u]) as u32;
4380    }
4381
4382    true
4383}
4384
4385fn solve_ntru_binary_depth0(logn: u32, f: &[i8], g: &[i8], tmp: &mut [u32]) -> bool {
4386    let n: usize = 1 << logn;
4387    let hn = n >> 1;
4388
4389    let p = PRIMES[0].p;
4390    let p0i = modp_ninv31(p);
4391    let r2 = modp_r2(p, p0i);
4392
4393    // Layout: Fp[hn] Gp[hn] ft[n] gt[n] gm[n] igm[n]
4394    // Fp and Gp are from tmp (previous level output, 1 word each)
4395    let mut fp_arr = vec![0u32; hn];
4396    let mut gp_arr = vec![0u32; hn];
4397    for u in 0..hn {
4398        fp_arr[u] = modp_set(zint_one_to_plain(&tmp[u..u + 1]), p);
4399        gp_arr[u] = modp_set(zint_one_to_plain(&tmp[hn + u..hn + u + 1]), p);
4400    }
4401
4402    let mut gm = vec![0u32; n];
4403    let mut igm = vec![0u32; n];
4404    modp_mkgm2(&mut gm, &mut igm, logn, PRIMES[0].g, p, p0i);
4405
4406    modp_ntt2(&mut fp_arr, &gm, logn - 1, p, p0i);
4407    modp_ntt2(&mut gp_arr, &gm, logn - 1, p, p0i);
4408
4409    let mut ft = vec![0u32; n];
4410    let mut gt = vec![0u32; n];
4411    for u in 0..n {
4412        ft[u] = modp_set(f[u] as i32, p);
4413        gt[u] = modp_set(g[u] as i32, p);
4414    }
4415    modp_ntt2(&mut ft, &gm, logn, p, p0i);
4416    modp_ntt2(&mut gt, &gm, logn, p, p0i);
4417
4418    // Build unreduced F, G
4419    let mut u = 0;
4420    while u < n {
4421        let ft_a = ft[u + 0];
4422        let ft_b = ft[u + 1];
4423        let gt_a = gt[u + 0];
4424        let gt_b = gt[u + 1];
4425        let m_fp = modp_montymul(fp_arr[u >> 1], r2, p, p0i);
4426        let m_gp = modp_montymul(gp_arr[u >> 1], r2, p, p0i);
4427        ft[u + 0] = modp_montymul(gt_b, m_fp, p, p0i);
4428        ft[u + 1] = modp_montymul(gt_a, m_fp, p, p0i);
4429        gt[u + 0] = modp_montymul(ft_b, m_gp, p, p0i);
4430        gt[u + 1] = modp_montymul(ft_a, m_gp, p, p0i);
4431        u += 2;
4432    }
4433    modp_intt2(&mut ft, &igm, logn, p, p0i);
4434    modp_intt2(&mut gt, &igm, logn, p, p0i);
4435
4436    // Save F, G (these are the unreduced values)
4437    let mut fp_full = ft.clone();
4438    let mut gp_full = gt.clone();
4439
4440    // Babai reduction using NTT modular arithmetic
4441    // Compute F*adj(f)+G*adj(g) and f*adj(f)+g*adj(g)
4442    modp_mkgm2(&mut gm, &mut igm, logn, PRIMES[0].g, p, p0i);
4443
4444    modp_ntt2(&mut fp_full, &gm, logn, p, p0i);
4445    modp_ntt2(&mut gp_full, &gm, logn, p, p0i);
4446
4447    // f and adj(f)
4448    let mut t4 = vec![0u32; n];
4449    let mut t5 = vec![0u32; n];
4450    t4[0] = modp_set(f[0] as i32, p);
4451    t5[0] = modp_set(f[0] as i32, p);
4452    for u in 1..n {
4453        t4[u] = modp_set(f[u] as i32, p);
4454        t5[n - u] = modp_set(-(f[u] as i32), p);
4455    }
4456    modp_ntt2(&mut t4, &gm, logn, p, p0i);
4457    modp_ntt2(&mut t5, &gm, logn, p, p0i);
4458
4459    let mut t2 = vec![0u32; n]; // F*adj(f)
4460    let mut t3 = vec![0u32; n]; // f*adj(f)
4461    for u in 0..n {
4462        let w = modp_montymul(t5[u], r2, p, p0i);
4463        t2[u] = modp_montymul(w, fp_full[u], p, p0i);
4464        t3[u] = modp_montymul(w, t4[u], p, p0i);
4465    }
4466
4467    // g and adj(g)
4468    t4[0] = modp_set(g[0] as i32, p);
4469    t5[0] = modp_set(g[0] as i32, p);
4470    for u in 1..n {
4471        t4[u] = modp_set(g[u] as i32, p);
4472        t5[n - u] = modp_set(-(g[u] as i32), p);
4473    }
4474    modp_ntt2(&mut t4, &gm, logn, p, p0i);
4475    modp_ntt2(&mut t5, &gm, logn, p, p0i);
4476
4477    for u in 0..n {
4478        let w = modp_montymul(t5[u], r2, p, p0i);
4479        t2[u] = modp_add(t2[u], modp_montymul(w, gp_full[u], p, p0i), p);
4480        t3[u] = modp_add(t3[u], modp_montymul(w, t4[u], p, p0i), p);
4481    }
4482
4483    // iNTT t2, t3
4484    modp_mkgm2(&mut gm, &mut igm, logn, PRIMES[0].g, p, p0i);
4485    modp_intt2(&mut t2, &igm, logn, p, p0i);
4486    modp_intt2(&mut t3, &igm, logn, p, p0i);
4487
4488    let mut t1_norm = vec![0i32; n];
4489    let mut t2_norm = vec![0i32; n];
4490    for u in 0..n {
4491        t1_norm[u] = modp_norm(t2[u], p);
4492        t2_norm[u] = modp_norm(t3[u], p);
4493    }
4494
4495    // FFT-based division
4496    let mut rt3 = vec![FPR_ZERO; n];
4497    for u in 0..n {
4498        rt3[u] = fpr_of(t2_norm[u] as i64);
4499    }
4500    fft::fft(&mut rt3, logn);
4501    let rt2_half: Vec<Fpr> = rt3[..hn].to_vec();
4502
4503    let mut rt3b = vec![FPR_ZERO; n];
4504    for u in 0..n {
4505        rt3b[u] = fpr_of(t1_norm[u] as i64);
4506    }
4507    fft::fft(&mut rt3b, logn);
4508
4509    fft::poly_div_autoadj_fft(&mut rt3b, &rt2_half, logn);
4510    fft::ifft(&mut rt3b, logn);
4511
4512    let mut k_arr = vec![0u32; n];
4513    for u in 0..n {
4514        k_arr[u] = modp_set(fpr_rint(rt3b[u]) as i32, p);
4515    }
4516
4517    // Subtract k*f from F, k*g from G
4518    modp_mkgm2(&mut gm, &mut igm, logn, PRIMES[0].g, p, p0i);
4519    let mut t4f = vec![0u32; n];
4520    let mut t5g = vec![0u32; n];
4521    for u in 0..n {
4522        t4f[u] = modp_set(f[u] as i32, p);
4523        t5g[u] = modp_set(g[u] as i32, p);
4524    }
4525    modp_ntt2(&mut k_arr, &gm, logn, p, p0i);
4526    modp_ntt2(&mut t4f, &gm, logn, p, p0i);
4527    modp_ntt2(&mut t5g, &gm, logn, p, p0i);
4528
4529    for u in 0..n {
4530        let kw = modp_montymul(k_arr[u], r2, p, p0i);
4531        fp_full[u] = modp_sub(fp_full[u], modp_montymul(kw, t4f[u], p, p0i), p);
4532        gp_full[u] = modp_sub(gp_full[u], modp_montymul(kw, t5g[u], p, p0i), p);
4533    }
4534    modp_intt2(&mut fp_full, &igm, logn, p, p0i);
4535    modp_intt2(&mut gp_full, &igm, logn, p, p0i);
4536
4537    for u in 0..n {
4538        tmp[u] = modp_norm(fp_full[u], p) as u32;
4539        tmp[n + u] = modp_norm(gp_full[u], p) as u32;
4540    }
4541
4542    true
4543}
4544
4545fn solve_ntru(
4546    logn: u32,
4547    big_f: &mut [i8],
4548    big_g: Option<&mut [i8]>,
4549    f: &[i8],
4550    g: &[i8],
4551    lim: i32,
4552    tmp: &mut [u32],
4553) -> bool {
4554    let n: usize = 1 << logn;
4555
4556    if !solve_ntru_deepest(logn, f, g, tmp) {
4557        return false;
4558    }
4559
4560    if logn <= 2 {
4561        let mut depth = logn;
4562        while depth > 0 {
4563            depth -= 1;
4564            if !solve_ntru_intermediate(logn, f, g, depth, tmp) {
4565                return false;
4566            }
4567        }
4568    } else {
4569        let mut depth = logn;
4570        while depth > 2 {
4571            depth -= 1;
4572            if !solve_ntru_intermediate(logn, f, g, depth, tmp) {
4573                return false;
4574            }
4575        }
4576        if !solve_ntru_binary_depth1(logn, f, g, tmp) {
4577            return false;
4578        }
4579        if !solve_ntru_binary_depth0(logn, f, g, tmp) {
4580            return false;
4581        }
4582    }
4583
4584    // Extract results
4585    let mut g_buf = vec![0i8; n];
4586    let g_out = big_g.unwrap_or(&mut g_buf);
4587
4588    if !poly_big_to_small(big_f, tmp, lim, logn) {
4589        return false;
4590    }
4591    if !poly_big_to_small(g_out, &tmp[n..], lim, logn) {
4592        return false;
4593    }
4594
4595    // Verify that f*G - g*F = q (mod p)
4596    let p = PRIMES[0].p;
4597    let p0i = modp_ninv31(p);
4598    let mut gm = vec![0u32; 2 * n];
4599    let mut gt_v = vec![0u32; n];
4600    let mut ft_v = vec![0u32; n];
4601    let mut fv = vec![0u32; n];
4602    let mut gv = vec![0u32; n];
4603    let (gm_lo, gm_hi) = gm.split_at_mut(n);
4604    modp_mkgm2(gm_lo, gm_hi, logn, PRIMES[0].g, p, p0i);
4605
4606    for u in 0..n {
4607        gt_v[u] = modp_set(g_out[u] as i32, p);
4608    }
4609    for u in 0..n {
4610        fv[u] = modp_set(f[u] as i32, p);
4611        gv[u] = modp_set(g[u] as i32, p);
4612        ft_v[u] = modp_set(big_f[u] as i32, p);
4613    }
4614    modp_ntt2(&mut fv, &gm[..n], logn, p, p0i);
4615    modp_ntt2(&mut gv, &gm[..n], logn, p, p0i);
4616    modp_ntt2(&mut ft_v, &gm[..n], logn, p, p0i);
4617    modp_ntt2(&mut gt_v, &gm[..n], logn, p, p0i);
4618
4619    let r = modp_montymul(12289, 1, p, p0i);
4620    for u in 0..n {
4621        let z = modp_sub(
4622            modp_montymul(fv[u], gt_v[u], p, p0i),
4623            modp_montymul(gv[u], ft_v[u], p, p0i),
4624            p,
4625        );
4626        if z != r {
4627            return false;
4628        }
4629    }
4630
4631    true
4632}
4633
4634// ======================================================================
4635// Main key generation entry point
4636// ======================================================================
4637
4638/// Generate a Falcon key pair.
4639///
4640/// rng: SHAKE256 context (flipped/ready for extraction)
4641/// f, g: secret key polynomials (output)
4642/// big_f: NTRU equation solution F (output)
4643/// big_g: NTRU equation solution G (output, may be None)
4644/// h: public key (output, may be None)
4645/// logn: log2 of degree (1..10)
4646/// tmp: temporary buffer (must be large enough)
4647pub fn keygen(
4648    rng: &mut InnerShake256Context,
4649    f: &mut [i8],
4650    g: &mut [i8],
4651    big_f: &mut [i8],
4652    mut big_g: Option<&mut [i8]>,
4653    mut h: Option<&mut [u16]>,
4654    logn: u32,
4655    tmp: &mut [u8],
4656) {
4657    let n: usize = 1 << logn;
4658
4659    // Use raw pointer to allow reuse of tmp across loop iterations.
4660    let tmp_ptr = tmp.as_mut_ptr();
4661    let tmp_len = tmp.len();
4662
4663    loop {
4664        // Generate f and g with Gaussian distribution
4665        // Uses SHAKE256 directly (matching C reference FALCON_KG_CHACHA20=0)
4666        poly_small_mkgauss(rng, f, logn);
4667        poly_small_mkgauss(rng, g, logn);
4668
4669        // Check coefficient bounds
4670        let lim = 1i32 << (codec::MAX_FG_BITS[logn as usize] - 1);
4671        let mut bad = false;
4672        for u in 0..n {
4673            if f[u] as i32 >= lim
4674                || (f[u] as i32) <= -lim
4675                || g[u] as i32 >= lim
4676                || (g[u] as i32) <= -lim
4677            {
4678                bad = true;
4679                break;
4680            }
4681        }
4682        if bad {
4683            continue;
4684        }
4685
4686        // Check squared norm
4687        let normf = poly_small_sqnorm(f, logn);
4688        let normg = poly_small_sqnorm(g, logn);
4689        let norm = (normf.wrapping_add(normg)) | ((normf | normg) >> 31).wrapping_neg();
4690        if norm >= 16823 {
4691            continue;
4692        }
4693
4694        // Compute orthogonalized vector norm
4695        let fpr_tmp: &mut [Fpr] = unsafe {
4696            core::slice::from_raw_parts_mut(
4697                tmp_ptr as *mut Fpr,
4698                tmp_len / core::mem::size_of::<Fpr>(),
4699            )
4700        };
4701        let (rt1, rest) = fpr_tmp.split_at_mut(n);
4702        let (rt2, rest) = rest.split_at_mut(n);
4703        let (rt3, _) = rest.split_at_mut(n);
4704
4705        poly_small_to_fp(rt1, f, logn);
4706        poly_small_to_fp(rt2, g, logn);
4707        fft::fft(rt1, logn);
4708        fft::fft(rt2, logn);
4709        fft::poly_invnorm2_fft(rt3, rt1, rt2, logn);
4710        fft::poly_adj_fft(rt1, logn);
4711        fft::poly_adj_fft(rt2, logn);
4712        fft::poly_mulconst(rt1, FPR_Q, logn);
4713        fft::poly_mulconst(rt2, FPR_Q, logn);
4714        fft::poly_mul_autoadj_fft(rt1, rt3, logn);
4715        fft::poly_mul_autoadj_fft(rt2, rt3, logn);
4716        fft::ifft(rt1, logn);
4717        fft::ifft(rt2, logn);
4718        let mut bnorm = FPR_ZERO;
4719        for u in 0..n {
4720            bnorm = fpr_add(bnorm, fpr_sqr(rt1[u]));
4721            bnorm = fpr_add(bnorm, fpr_sqr(rt2[u]));
4722        }
4723        if fpr_lt(bnorm, FPR_BNORM_MAX) == 0 {
4724            continue;
4725        }
4726
4727        // Compute public key h = g/f mod phi mod q
4728        let mut h_buf = vec![0u16; n];
4729        let tmp_slice = unsafe { core::slice::from_raw_parts_mut(tmp_ptr, tmp_len) };
4730        if !compute_public(&mut h_buf, f, g, logn, tmp_slice) {
4731            continue;
4732        }
4733        if let Some(ref mut hh) = h {
4734            hh[..n].copy_from_slice(&h_buf[..n]);
4735        }
4736
4737        // Solve the NTRU equation
4738        let lim2 = (1i32 << (codec::MAX_FG_BITS_UPPER[logn as usize] - 1)) - 1;
4739        let tmp_u32: &mut [u32] =
4740            unsafe { core::slice::from_raw_parts_mut(tmp_ptr as *mut u32, tmp_len / 4) };
4741        if !solve_ntru(logn, big_f, big_g.as_deref_mut(), f, g, lim2, tmp_u32) {
4742            continue;
4743        }
4744
4745        break;
4746    }
4747}