Let us walk on the 3-isogeny graph
Loading...
Searching...
No Matches
fp-gmp.c
Go to the documentation of this file.
1#include "fp-gmp.h"
2#include "../fp-counters.h"
3// #include "framework.h"
4#include "../../primes.h"
5
6#include <gmp.h>
7
8//#define USE_GMP_SEC_FUNCTIONS
9//#define MONTGOMERY
10
11#if defined P2047m1l226
12const fp p = {
130xFFFFFFFFFFFFFFFF,0xCB336E65DD9AB972,0x31DA9904076E6A70,0x9F825D7BEA428F54,
140x80B1D7895DEABE60,0xD3B3CDE44A99EBD8,0x2C433638FE69F531,0x46C02600030671E2,
150x3EB36EBF24EB264F,0x5872FD3292CF3725,0x25261B882C99A891,0x5AA0C7A8E51C618F,
160xDFE30228DC090A5E,0x1235FFF9C3496720,0x556D82DFB25A19E0,0xAF0D91A49AD1FCF6,
170x5CFE8BDDCAAF7214,0x67D90F84820F3740,0x85DD61C29F9EA3FA,0x1B493E97510173BA,
180x57963F8A2EF281C0,0x215B3CA607652A95,0xBE13D52039838268,0xC1B8B0AC479FC5EB,
190xAACDDF254A1CEFF1,0x5D89B511362EE752,0x5C935F8B2C251C39,0x3336CCFC4DD81041,
200xFE4AEA834B8F332,0x8AA77CDCE5CCA52,0x2DD1AFC034E7A378,0x4B5882EA64EA57E7 };
21
22const fp r_squared_mod_p = {
230x7F4DD8E5DF23BB8,0x5C776D52280157ED,0x649F1DDABA652A4C,0x5F82754E976E1C51,
240x216A66554955B423,0x837F16EBDA6112EC,0x449BE2BE3F1308CA,0xD417CF96FBD398E,
250xF40CA379B3CFDD87,0xE572142C0A18BEF2,0x174A98FEF7CBBD6D,0x92147FED3A21520A,
260xC2FEF4524FB5A582,0x7EA04A000CF05B29,0xEE7604D0586AEE7,0x360C6B9E4402ACBE,
270x2412C3AB8629CC28,0x11843E0F489CD4DA,0x965E567F2D69ADA1,0xC35FDB6E0A1CE3AC,
280xDFCE999B5BE1D15D,0xADFC765457B8334C,0x178A9115F96B28ED,0x7C25482F10317EEF,
290x87B1090C7F92BA82,0xF6E929FCF67F4BB3,0xDAB73BE93D26BAA6,0xA520E31962981EFB,
300xD1EBB498F914FB73,0x71AAAC9068F25B31,0x18F8EE6ACA512273,0x2EA634B399D69CF7 };
31const fp p_minus_2 = {
320xFFFFFFFFFFFFFFFD,0xCB336E65DD9AB972,0x31DA9904076E6A70,0x9F825D7BEA428F54,
330x80B1D7895DEABE60,0xD3B3CDE44A99EBD8,0x2C433638FE69F531,0x46C02600030671E2,
340x3EB36EBF24EB264F,0x5872FD3292CF3725,0x25261B882C99A891,0x5AA0C7A8E51C618F,
350xDFE30228DC090A5E,0x1235FFF9C3496720,0x556D82DFB25A19E0,0xAF0D91A49AD1FCF6,
360x5CFE8BDDCAAF7214,0x67D90F84820F3740,0x85DD61C29F9EA3FA,0x1B493E97510173BA,
370x57963F8A2EF281C0,0x215B3CA607652A95,0xBE13D52039838268,0xC1B8B0AC479FC5EB,
380xAACDDF254A1CEFF1,0x5D89B511362EE752,0x5C935F8B2C251C39,0x3336CCFC4DD81041,
390xFE4AEA834B8F332,0x8AA77CDCE5CCA52,0x2DD1AFC034E7A378,0x4B5882EA64EA57E7 };
40const fp inv_min_p_mod_r = {
410x1,0xCB336E65DD9AB973,0xAF643763A21D419,0x9F2BDE02384F089B,
420xEEEE4E67E761E071,0xE14F6E448846FC16,0x7C33F1CB8995D537,0x9C5E5A0E41FBBB2B,
430x4018415AA62AB0F7,0x570A5C7C482D3FA4,0x290CBC45D2ED6704,0x6935DDB9DA0BF373,
440xA9C3A7DCE054C2E7,0x1A92280608691985,0x786A946F6A893A4E,0x817444232C2B50DA,
450x51BC998B9190158,0xED0A80A509441339,0x70CCCC137B5E8F1D,0x425869F7AD1DEB2C,
460xE27606BD4F848CE,0xF78A71E7CFC37870,0x347E7689108AA61E,0xD89DFF0D518DFEFF,
470x7223F57C599BD0D8,0xA84199D7B55177A2,0xBADC4BDDEB193D87,0x3C4583C1A5C1CD7,
480x8ACB116EB508F9DF,0x23F88493636893F,0x47A93C3A24EFEA29,0x5420403EEAB4C43E };
49
50#ifdef MONTGOMERY
51const fp fp_1 = {
520x3,0x9E65B4CE672FD3A7,0x6A7034F3E9B4C0AD,0x2178E78C41385203,
530x7DEA7963E63FC4DE,0x84E4965320323C76,0x7B365D5504C2206A,0x2BBF8DFFF6ECAA59,
540x43E5B3C2913E8D12,0xF6A7086847925A90,0x908DAD677A33064B,0xF01DA90550AADB52,
550x6056F9856BE4E0E4,0xC95E0012B623CA9D,0xFFB77760E8F1B25F,0xF2D74B122F8A091C,
560xE9045C669FF1A9C1,0xC874D17279D25A3E,0x6E67DAB821241410,0xAE24443A0CFBA4D0,
570xF93D416173287ABF,0x9BEE4A0DE9D0803F,0xC5C4809F537578C7,0xBAD5EDFB2920AE3C,
580xFF96629021A9302A,0xE762E0CC5D734A07,0xEA45E15E7B90AB53,0x665B990B1677CF3B,
590xD051F40761D52669,0xE600989694E9A109,0x768AF0BF61491597,0x1DF67740D140F84A };
60
61#else
62const fp fp_1 = {0x1};
63#endif
64
65#define pbits 2047
66#define itch_size 128
67
68#elif defined P4095m27l262
69const fp p = {
700xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
710xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
720xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
730xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
740xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
750xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
760xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xBABB857F53B45F38,
770xA0FA17C9F017AAA4,0xCA367EE9DCA136B3,0x9825FE450B3306F0,0x7598BC71B003BE60,
780x75D9C93D2F88118F,0x25FAB108318489EF,0xB853C0B81A59A320,0xA68AC2FAA6576BD0,
790x6FE6DE6B60B8DD73,0xBE1BA97A296DF474,0x90F3D594E0BB1B1A,0x50845534C663819,
800x5DA43F39BA465F9D,0x67A79C055011CD6C,0x10AABAC0E83F00E0,0x55B21EF174813BB,
810xB32A5B550F65F8E8,0x6C8A637162557E06,0x184398D9CE7B8ED0,0xF6389D60A659DBF9,
820x4898DDCC4C6451B1,0xD34D57E179DBAA87,0xB300098DDDD2A53D,0x4D83B4D248CD8DC8,
830xA999042BBABBA293,0x8E37AAC3FD7145B5,0x896199C58C6CDEE2,0x5D499CA3173C69A1,
840x324B4917CB3C3BFA,0xF83956A2F7A46669,0xE0CA5CB997EAFB95,0x16C0EB2AAF99D121,
850xAF95A6D3DA6A40FF,0x8EDE5A2EF574F91F,0xF17F15465794272,0x411889A889DBBAF2};
86const fp r_squared_mod_p = {
870xCA9664131ABC0203,0xBBACA9841048F533,0x8EABAAFDB1A5302C,0x8717BB74DAE9C8CC,
880xDB09FDAD266C9FE3,0x87FE292E7623BBAC,0xC4608F8CDD193747,0x29756590B837429E,
890x25E069B05DF9158B,0x81B88A6E00EB97D7,0xFEB41576DF0529FE,0x75DCB5D79F31D7BD,
900x4ECF835F54A00B39,0x12BDF9E28ADE3FA0,0xBE1FC6DF5625BA99,0x387429A496E48929,
910x26C1594875AAEC54,0xF55991263DCDBF72,0x824598E7E40BF31C,0xCF0D0408B41080C8,
920x6E8ED3548F1C53E3,0xE89C93835E6CB9A7,0xB8F73FC08D85EEAA,0x16813517F4D53663,
930xBDABAD4E8AD094D7,0xC8F4E4BC812987AB,0xF2B12B6984FB1324,0xDCF1220EFBBDF5BF,
940xD4ADE1120C73CECE,0xFF966A2C8A47A0CC,0x90B723888F342AB4,0xBBFFE44E9B103534,
950x7A6882E784FAFFFD,0x2032BA8B44CD3D68,0xE59012732A0507CE,0x41030A597B14046D,
960x70338B98F4FD3DF5,0xF9DBB4D3531E71A0,0xE09D4FD229D810B6,0x1F73C8F1FBBCF3F4,
970xBDA5F434EDB6FD3B,0x138E4F816D09F0BE,0x4D29DC6B345CC58F,0x48365C1D1C10AD63,
980x8799389318D2A8C2,0xDC983E5063104657,0x1BCDA74009C0B95A,0x46AC0180E7080A18,
990x1ECE665A556B2D85,0xBE187F58C05BF423,0x137C3D745FCF8564,0xE94225E253BCC1FF,
1000xE18A90228B1C625E,0xED4C0E96616F842B,0x79EFB7D08707F5AF,0xB0FC6FF8828CCFD0,
1010x5459C35AFF8A0F53,0x55F5A04678F556B0,0xD8CBCC2A34884A9C,0xB64BC960DEA1137F,
1020x276AA6537115111B,0xE8F7B5C15A55D484,0x8CB566E62B90747C,0x2B202E35F35F4C36};
103const fp p_minus_2 = {
1040xFFFFFFFFFFFFFFFD,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
1050xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
1060xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
1070xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
1080xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
1090xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
1100xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xBABB857F53B45F38,
1110xA0FA17C9F017AAA4,0xCA367EE9DCA136B3,0x9825FE450B3306F0,0x7598BC71B003BE60,
1120x75D9C93D2F88118F,0x25FAB108318489EF,0xB853C0B81A59A320,0xA68AC2FAA6576BD0,
1130x6FE6DE6B60B8DD73,0xBE1BA97A296DF474,0x90F3D594E0BB1B1A,0x50845534C663819,
1140x5DA43F39BA465F9D,0x67A79C055011CD6C,0x10AABAC0E83F00E0,0x55B21EF174813BB,
1150xB32A5B550F65F8E8,0x6C8A637162557E06,0x184398D9CE7B8ED0,0xF6389D60A659DBF9,
1160x4898DDCC4C6451B1,0xD34D57E179DBAA87,0xB300098DDDD2A53D,0x4D83B4D248CD8DC8,
1170xA999042BBABBA293,0x8E37AAC3FD7145B5,0x896199C58C6CDEE2,0x5D499CA3173C69A1,
1180x324B4917CB3C3BFA,0xF83956A2F7A46669,0xE0CA5CB997EAFB95,0x16C0EB2AAF99D121,
1190xAF95A6D3DA6A40FF,0x8EDE5A2EF574F91F,0xF17F15465794272,0x411889A889DBBAF2};
120const fp inv_min_p_mod_r = {
1210x1,0x0,0x0,0x0,
1220x0,0x0,0x0,0x0,
1230x0,0x0,0x0,0x0,
1240x0,0x0,0x0,0x0,
1250x0,0x0,0x0,0x0,
1260x0,0x0,0x0,0x0,
1270x0,0x0,0x0,0xBABB857F53B45F39,
1280xA0FA17C9F017AAA4,0xCA367EE9DCA136B3,0x9825FE450B3306F0,0x7598BC71B003BE60,
1290x75D9C93D2F88118F,0x25FAB108318489EF,0xB853C0B81A59A320,0xA68AC2FAA6576BD0,
1300x6FE6DE6B60B8DD73,0xBE1BA97A296DF474,0x90F3D594E0BB1B1A,0x50845534C663819,
1310x5DA43F39BA465F9D,0x67A79C055011CD6C,0x10AABAC0E83F00E0,0x55B21EF174813BB,
1320xB32A5B550F65F8E8,0x6C8A637162557E06,0x184398D9CE7B8ED0,0xF6389D60A659DBF9,
1330x4898DDCC4C6451B1,0xD34D57E179DBAA87,0xB300098DDDD2A53D,0x4D83B4D248CD8DC8,
1340xA999042BBABBA293,0x8E37AAC3FD7145B5,0xDEDC3288E003993,0x28FCCC134500ED9,
1350x99237E427A9541FF,0x979318575D8DA63E,0xCD99020B3B318AB8,0xF038B83232D3D40A,
1360x8B6DB111DCEFF4B8,0x9204380C67BBB04,0x4DC7D4B3C7C3F798,0x76E2C34D5BDB8598};
137
138#ifdef MONTGOMERY
139const fp fp_1 = {
1400x3,0x0,0x0,0x0,
1410x0,0x0,0x0,0x0,
1420x0,0x0,0x0,0x0,
1430x0,0x0,0x0,0x0,
1440x0,0x0,0x0,0x0,
1450x0,0x0,0x0,0x0,
1460x0,0x0,0x0,0xCFCD6F8204E2E255,
1470x1D11B8A22FB90011,0xA15C83426A1C5BE5,0x378E0530DE66EB2D,0x9F35CAAAEFF4C4DE,
1480x9E72A4487167CB51,0x8E0FECE76B726231,0xD704BDD7B0F3169F,0xC5FB7100CF9BC8D,
1490xB04B64BDDDD567A5,0xC5AD039183B622A2,0x4D247F415DCEAEAF,0xF0E730061ACD57B3,
1500xE7134252D12CE128,0xC9092BF00FCA97BA,0xCDFFCFBD4742FD5E,0xEFEE9A32BA27C4CE,
1510xE680EE00D1CE1547,0xBA60D5ABD8FF85EB,0xB7353572948D538E,0x1D5627DE0CF26C14,
1520x2635669B1AD30AEA,0x8617F85B926D006A,0xE6FFE35666881046,0x1774E189259756A5,
1530x334F37CCFCD1846,0x5558FFB407AC2EDF,0x63DB32AF5AB96358,0xE8232A16BA4AC31B,
1540x691E24B89E4B4C10,0x1753FC171912CCC4,0x5DA0E9D3383F0D3E,0xBBBD3E7FF1328C9A,
1550xF13F0B8470C13D02,0x5364F1731FA114A0,0xD2B82C02CF9438A8,0x3CB66306626CCF29};
156#else
157const fp fp_1 = {0x1};
158#endif
159
160#define pbits 4095
161#define itch_size 256
162
163#elif defined P5119m46l244
164const fp p = {
1650xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
1660xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
1670xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
1680xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
1690xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
1700xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
1710xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
1720xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
1730xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
1740xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
1750xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
1760xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xB5309D1E99A64A6A,0xD4F20F3D310BE993,
1770xD92726C717015CFD,0xF06D7BAB9FBC61BA,0xC2EE5257F3F53C0A,0x3AF92D2E448901D2,
1780x3A0C8A8186EE6D0D,0x53C4B1599AEEC0E1,0xE4EACE2722BC33D6,0x238DC49B3B1C9CC,
1790xB8D14D0F82E0AFB5,0x3B1B2AB37CD1DF46,0x7B9D7D5D4927ED03,0xADC309FAFEB712E0,
1800x1E9A86229953557A,0x1F15A379F4EF9329,0xA65C5A1161E1D325,0xB8711C1B97A356D8,
1810x6AD52806F4121BE7,0x951B321B6C3C584C,0xD4EDED55AFC190E5,0x56CF35332848D386,
1820xF6322D985F4F8905,0x37E31D4DDBC39AD6,0xBCFFB1DE739D78F0,0xBFBF3DA580661DCC,
1830x5CFB6A9766C03723,0x1BAA906DE71522B6,0xD76E42C1E401FF20,0xA69EFCEFEF88BD2E,
1840xA0A2737A7E193839,0x68C24DC989220343,0x524C926C9F96C9CF,0x6B5ECF5EB8DE6C90};
185const fp r_squared_mod_p = {
1860x3B6858C6EA09FF39,0xC0C1A01FC66553BF,0xBF1C26B03D13448D,0xCEE65529DB4276C6,
1870x263216DC529FA0E,0x1064C4347BDEEE65,0xE0A9109823C9039A,0xADA812BBB0D2D2CE,
1880x58633B8D4B5C35BA,0xDA399891C3CA96B0,0xCB943DC5AD81966C,0xE157868A016EAF8F,
1890x6993ABD64C6304CF,0xE01D2BB15467A629,0xFF811CCFF0BC9F26,0x9EDC510CD20C3FEA,
1900xCF05F2DD5DF5214F,0x7105AFC7967757B,0x1E9AA04F82608BE6,0x8CC448337DD40BB3,
1910x1E91E2EE0BA2628A,0xE944B17DAA7E75A3,0xD16BA714A0148CB1,0x80B88C8429F6700E,
1920x83A8759BF83CF558,0x7AFCC7F87611BDB8,0x7254245CB9DD9DE7,0xF1288B81E6B10E99,
1930xD18C267CEBA3F6D4,0xF8D367B197112BF,0xE7EEC1B008858F7D,0x59BAB08FF24DFCE2,
1940xCB7750FAB0A9DBAC,0x4C38E3A5BB5D6793,0xCA09905B939E13A,0x79099E2C2B7B8D5E,
1950x8D917855EF331AE4,0xFBEE792CF496564D,0x63B46BB42339F99E,0x164D487ABD553DA9,
1960x1FE539A1C0233F64,0xD54A9A356B55B86E,0x461FAABE484D85BF,0x5BC0E4B7B2996C6D,
1970x16B704B7EE90E039,0x90C046EAF2EE369B,0x5A3F5E29E205FB7B,0x941D41A97F9A2E31,
1980xB30C70F20F70CB36,0xA766CBA7A81DA5ED,0xC6CBFA0579541D21,0x8158A5A6310D5592,
1990x5D331ACA8A018A36,0xC58988AEA16BA091,0xC1B95F08B0A1CD3E,0x1FEE3B3C136B3C25,
2000xF604C3F7DCFB1769,0x8F0981ABF7CCEC30,0xADC387AF7A71D8F2,0xBA0397BD54E38EBD,
2010x12706EDAB696BE65,0x6E272E35D79CE370,0xEFDCE9C846E22985,0x271B00F78817CDF7,
2020x62A7CD3B88536B4A,0xEBF82C1F791DB225,0x701BF73194E21823,0x9A7D7C09E114C256,
2030xF791706806F0F525,0x8EF51F6403121129,0x48BA0645DF412D6B,0xCF3A4C68615D4A05,
2040x59D9DC740C1D2A03,0xE7DA10BCF7AA2,0xBA8B94C9E733AAB2,0xAFB849D79563DFE9,
2050x8482B243768BD44F,0x9A7716C39F4ADA39,0x38E0B51760EEBE36,0x2F644368EA43512};
206const fp p_minus_2 = {
2070xFFFFFFFFFFFFFFFD,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
2080xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
2090xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
2100xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
2110xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
2120xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
2130xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
2140xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
2150xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
2160xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
2170xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
2180xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xB5309D1E99A64A6A,0xD4F20F3D310BE993,
2190xD92726C717015CFD,0xF06D7BAB9FBC61BA,0xC2EE5257F3F53C0A,0x3AF92D2E448901D2,
2200x3A0C8A8186EE6D0D,0x53C4B1599AEEC0E1,0xE4EACE2722BC33D6,0x238DC49B3B1C9CC,
2210xB8D14D0F82E0AFB5,0x3B1B2AB37CD1DF46,0x7B9D7D5D4927ED03,0xADC309FAFEB712E0,
2220x1E9A86229953557A,0x1F15A379F4EF9329,0xA65C5A1161E1D325,0xB8711C1B97A356D8,
2230x6AD52806F4121BE7,0x951B321B6C3C584C,0xD4EDED55AFC190E5,0x56CF35332848D386,
2240xF6322D985F4F8905,0x37E31D4DDBC39AD6,0xBCFFB1DE739D78F0,0xBFBF3DA580661DCC,
2250x5CFB6A9766C03723,0x1BAA906DE71522B6,0xD76E42C1E401FF20,0xA69EFCEFEF88BD2E,
2260xA0A2737A7E193839,0x68C24DC989220343,0x524C926C9F96C9CF,0x6B5ECF5EB8DE6C90};
227const fp inv_min_p_mod_r = {
2280x1,0x0,0x0,0x0,
2290x0,0x0,0x0,0x0,
2300x0,0x0,0x0,0x0,
2310x0,0x0,0x0,0x0,
2320x0,0x0,0x0,0x0,
2330x0,0x0,0x0,0x0,
2340x0,0x0,0x0,0x0,
2350x0,0x0,0x0,0x0,
2360x0,0x0,0x0,0x0,
2370x0,0x0,0x0,0x0,
2380x0,0x0,0x0,0x0,
2390x0,0x0,0xB5309D1E99A64A6B,0xD4F20F3D310BE993,
2400xD92726C717015CFD,0xF06D7BAB9FBC61BA,0xC2EE5257F3F53C0A,0x3AF92D2E448901D2,
2410x3A0C8A8186EE6D0D,0x53C4B1599AEEC0E1,0xE4EACE2722BC33D6,0x238DC49B3B1C9CC,
2420xB8D14D0F82E0AFB5,0x3B1B2AB37CD1DF46,0x7B9D7D5D4927ED03,0xADC309FAFEB712E0,
2430x1E9A86229953557A,0x1F15A379F4EF9329,0xA65C5A1161E1D325,0xB8711C1B97A356D8,
2440x6AD52806F4121BE7,0x951B321B6C3C584C,0xD4EDED55AFC190E5,0x56CF35332848D386,
2450xF6322D985F4F8905,0x37E31D4DDBC39AD6,0xBCFFB1DE739D78F0,0xBFBF3DA580661DCC,
2460x5CFB6A9766C03723,0x1BAA906DE71522B6,0xD76E42C1E401FF20,0xA69EFCEFEF88BD2E,
2470xA0A2737A7E193839,0x68C24DC989220343,0x524C926C9F96C9CF,0x6B5ECF5EB8DE6C90};
248
249#ifdef MONTGOMERY
250const fp fp_1 = {
2510x2,0x0,0x0,0x0,
2520x0,0x0,0x0,0x0,
2530x0,0x0,0x0,0x0,
2540x0,0x0,0x0,0x0,
2550x0,0x0,0x0,0x0,
2560x0,0x0,0x0,0x0,
2570x0,0x0,0x0,0x0,
2580x0,0x0,0x0,0x0,
2590x0,0x0,0x0,0x0,
2600x0,0x0,0x0,0x0,
2610x0,0x0,0x0,0x0,
2620x0,0x0,0x959EC5C2CCB36B2A,0x561BE1859DE82CD8,
2630x4DB1B271D1FD4604,0x1F2508A8C0873C8A,0x7A235B50181587EA,0x8A0DA5A376EDFC5A,
2640x8BE6EAFCF22325E5,0x58769D4CCA227E3D,0x362A63B1BA879853,0xFB8E476C989C6C66,
2650x8E5D65E0FA3EA095,0x89C9AA99065C4172,0x8C505456DB025F9,0xA479EC0A0291DA3F,
2660xC2CAF3BACD59550A,0xC1D4B90C1620D9AD,0xB3474BDD3C3C59B5,0x8F1DC7C8D0B9524E,
2670x2A55AFF217DBC830,0xD5C99BC927874F67,0x56242554A07CDE34,0x52619599AF6E58F2,
2680x139BA4CF4160EDF5,0x9039C5644878CA52,0x86009C4318C50E1F,0x808184B4FF33C466,
2690x46092AD1327F91B8,0xC8AADF2431D5BA93,0x51237A7C37FC01BF,0xB2C2062020EE85A2,
2700xBEBB190B03CD8F8C,0x2E7B646CEDBBF978,0x5B66DB26C0D26C61,0x294261428E4326DF};
271#else
272const fp fp_1 = {0x1};
273#endif
274
275#define pbits 5119
276#define itch_size 322
277
278#elif defined P6143m59l262
279const fp p = {
2800xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
2810xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
2820xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
2830xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
2840xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
2850xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
2860xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
2870xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
2880xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
2890xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
2900xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
2910xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
2920xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
2930xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
2940xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0x35985E4C03BD1014,
2950x74C88B0E3733AB9E,0xCC5EBC3CA4FAA947,0x821D23FC31769999,0x7DD81C7ECF287336,
2960x397B3BC1E4878A95,0x4668669E24F5CD05,0x45C68D7E8D5BA6E8,0x63DAA86AB6F4AA9E,
2970x4FEADF6BA95A3814,0xC14DC5EE6A02B1CD,0xCCAAB92DABD0F3E2,0x5C5DE133E486EA2A,
2980x149B3990755103CF,0x7E37E927A1F549AC,0xB41FA73F044C2191,0x1558E943308D9356,
2990xCC51A5F650F1DDE6,0x9CB2FD4B418C0807,0xFDAC42332803B31B,0x3FE7C77E1BD479FC,
3000x77B20071167346DE,0x63DA3A20500E6BE1,0xEBBB7C777054734A,0xA71872C190AEABFF,
3010xA13B14217BC25602,0x3BF5A900D843EEF1,0x2D83E22FC80D9EC1,0x3FAC5F1728799D3D,
3020x289BCF6DC62ADBCE,0x65606A37CBFD6BBA,0x4025C0EB0BD9BC24,0x316E981BB3081481,
3030xFFAE9D83F13FD711,0x3A4C4B7B7647853E,0x1D234B4CEA41F44B,0x5475A30084FF51D6};
304const fp r_squared_mod_p = {
3050xEA1076E527DE13D2,0xC52E0483E2754A2E,0x5436E0A0C9B4B9B0,0x36B05C5BE329B851,
3060x841BEB22660A7F99,0xA41D5874CB9BB130,0x14F7C9564D190F6D,0x3D016994D56DC0D5,
3070x6FBC560206DCFC,0x287A31B541B41B73,0xD475ED64F68C23EF,0x3AF40FB5B2217366,
3080x61B2DB68718CA1D8,0xDE27B57ACF3EA0E9,0x19539863C951FC69,0x29B914EF38EFECB6,
3090xBF824A1A7F094517,0x9A227DA653BE3451,0x2BE700C9E0A5CF88,0x714DCADC04986290,
3100x8D1B250772E3FC6F,0x6E1979C64A6950FC,0x3DE9DB2EC7CFE4D7,0x41DFB16712835AD3,
3110xC8A4DA1ADCE1EA57,0xE79127BAFF6E4CE4,0x58DBB651E1FD5E83,0x1233EC7FC7A76EAD,
3120x10BEE487E2D20C5D,0xFC3D4345B89B0D88,0x4BFCA0D6C91C2E89,0x852F09D77DFE7B8D,
3130xC6F6FCDE180A8C7B,0x679EA8E6F3C66D2F,0xC3686AD1DFD71DA2,0x6F974B5AC8499469,
3140x6CE93E51EFDA6C77,0xAABDE4102AEAB7CB,0xE07ABF93F88447E,0x6FD8F23A45AB18F7,
3150x82BA3DE4FC056F7E,0x6B9CED500E61076E,0xC76158874C44F077,0x8019FB6AD3CEECAA,
3160x124EECB38098B680,0x2831C66750810633,0x1CFCD7437BD43E43,0x79F3B8EBDBFA28B5,
3170x18CDBBCD1671D212,0xD8FBBD1C9DB803F5,0x544FDB9742C04755,0x3C10AD2C03ED7F66,
3180xE26C19B6728EF975,0xB2DE0DCBFE031E63,0xF3FC921114247ECC,0x5441123FA874BA68,
3190xE3E034B43BF6EAE1,0xF5B4D8750F96C276,0x43741756C7A8EB9F,0x3BE507C2CDD316D2,
3200xF222366AAC72246E,0xDAFD3EEAB249E29D,0xAF3F026F58864E82,0x3CB6D1762D698008,
3210x334F8CFDE69BC30D,0x68CA56C4D05338E3,0xAE6F07AE1529BFCF,0xBDC400071E5A9DE7,
3220xFF7F6A1C8FE9750F,0x304E721C9FCC7884,0x796662377CE1F0AB,0x814B06A81F56D886,
3230x860CA75B9B6174F0,0x22A7776F8EC1B8CD,0x9B4BA313C44FE88D,0x4E3B5B720B6B0A1E,
3240x86C141F3C572195C,0x54C050368D8A3E02,0xCCE3FF5FDFE6A3AC,0xCDE2F0AE3E357604,
3250x6E2C8832740443,0xE61AECA7076C0558,0xC230DB509FB70D94,0x40C2E5EB595779AE,
3260x5B42311CD71CD2DC,0x1D33D362D2D3F25C,0x31C87F44C917374B,0x158AC965518F7419,
3270x7909DAA97DBCA21E,0x1AABE4853A468E60,0xF67CDEECBC59C895,0x1B1C1C8377584087,
3280x248E6A6B6C149308,0x5BD0155136187521,0x69B1017EADBBA771,0x3EA89DA336AAFB31};
329const fp p_minus_2 = {
3300xFFFFFFFFFFFFFFFD,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
3310xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
3320xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
3330xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
3340xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
3350xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
3360xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
3370xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
3380xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
3390xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
3400xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
3410xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
3420xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
3430xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
3440xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0x35985E4C03BD1014,
3450x74C88B0E3733AB9E,0xCC5EBC3CA4FAA947,0x821D23FC31769999,0x7DD81C7ECF287336,
3460x397B3BC1E4878A95,0x4668669E24F5CD05,0x45C68D7E8D5BA6E8,0x63DAA86AB6F4AA9E,
3470x4FEADF6BA95A3814,0xC14DC5EE6A02B1CD,0xCCAAB92DABD0F3E2,0x5C5DE133E486EA2A,
3480x149B3990755103CF,0x7E37E927A1F549AC,0xB41FA73F044C2191,0x1558E943308D9356,
3490xCC51A5F650F1DDE6,0x9CB2FD4B418C0807,0xFDAC42332803B31B,0x3FE7C77E1BD479FC,
3500x77B20071167346DE,0x63DA3A20500E6BE1,0xEBBB7C777054734A,0xA71872C190AEABFF,
3510xA13B14217BC25602,0x3BF5A900D843EEF1,0x2D83E22FC80D9EC1,0x3FAC5F1728799D3D,
3520x289BCF6DC62ADBCE,0x65606A37CBFD6BBA,0x4025C0EB0BD9BC24,0x316E981BB3081481,
3530xFFAE9D83F13FD711,0x3A4C4B7B7647853E,0x1D234B4CEA41F44B,0x5475A30084FF51D6};
354const fp inv_min_p_mod_r = {
3550x1,0x0,0x0,0x0,
3560x0,0x0,0x0,0x0,
3570x0,0x0,0x0,0x0,
3580x0,0x0,0x0,0x0,
3590x0,0x0,0x0,0x0,
3600x0,0x0,0x0,0x0,
3610x0,0x0,0x0,0x0,
3620x0,0x0,0x0,0x0,
3630x0,0x0,0x0,0x0,
3640x0,0x0,0x0,0x0,
3650x0,0x0,0x0,0x0,
3660x0,0x0,0x0,0x0,
3670x0,0x0,0x0,0x0,
3680x0,0x0,0x0,0x0,
3690x0,0x0,0x0,0x35985E4C03BD1015,
3700x74C88B0E3733AB9E,0xCC5EBC3CA4FAA947,0x821D23FC31769999,0x7DD81C7ECF287336,
3710x397B3BC1E4878A95,0x4668669E24F5CD05,0x45C68D7E8D5BA6E8,0x63DAA86AB6F4AA9E,
3720x4FEADF6BA95A3814,0xC14DC5EE6A02B1CD,0xCCAAB92DABD0F3E2,0x5C5DE133E486EA2A,
3730x149B3990755103CF,0x7E37E927A1F549AC,0xB41FA73F044C2191,0x1558E943308D9356,
3740xCC51A5F650F1DDE6,0x9CB2FD4B418C0807,0xFDAC42332803B31B,0x3FE7C77E1BD479FC,
3750x77B20071167346DE,0x63DA3A20500E6BE1,0xEBBB7C777054734A,0xA71872C190AEABFF,
3760xA13B14217BC25602,0x3BF5A900D843EEF1,0x2D83E22FC80D9EC1,0x3FAC5F1728799D3D,
3770x289BCF6DC62ADBCE,0x65606A37CBFD6BBA,0x4025C0EB0BD9BC24,0x316E981BB3081481,
3780xFFAE9D83F13FD711,0x3A4C4B7B7647853E,0x1D234B4CEA41F44B,0x5475A30084FF51D6};
379
380#ifdef MONTGOMERY
381const fp fp_1 = {
3820x3,0x0,0x0,0x0,
3830x0,0x0,0x0,0x0,
3840x0,0x0,0x0,0x0,
3850x0,0x0,0x0,0x0,
3860x0,0x0,0x0,0x0,
3870x0,0x0,0x0,0x0,
3880x0,0x0,0x0,0x0,
3890x0,0x0,0x0,0x0,
3900x0,0x0,0x0,0x0,
3910x0,0x0,0x0,0x0,
3920x0,0x0,0x0,0x0,
3930x0,0x0,0x0,0x0,
3940x0,0x0,0x0,0x0,
3950x0,0x0,0x0,0x0,
3960x0,0x0,0x0,0x5F36E51BF4C8CFC1,
3970xA1A65ED55A64FD25,0x9AE3CB4A11100429,0x79A8940B6B9C3332,0x8677AA839286A65C,
3980x538E4CBA5269603F,0x2CC6CC25911E98F0,0x2EAC578457ED0B47,0xD47006BFDB220025,
3990x103F61BD03F157C2,0xBC16AE34C1F7EA98,0x99FFD476FC8D2457,0xEAE65C64526B417F,
4000xC22E534EA00CF491,0x855844891A2022FB,0xE3A10A42F31B9B4B,0xBFF544366E5745FB,
4010x9B0B0E1D0D2A664D,0x29E7081E3B5BE7E8,0x6FB396687F4E6AD,0x4048A985AC829209,
4020x98E9FEACBCA62B65,0xD471519F0FD4BC5B,0x3CCD8A99AF02A620,0xAB6A7BB4DF3FC00,
4030x1C4EC39B8CB8FDF8,0x4C1F04FD7734332B,0x77745970A7D723BC,0x40FAE2BA86932848,
4040x862C91B6AD7F6C95,0xCFDEC1589C07BCD1,0x3F8EBD3EDC72CB92,0x6BB437ACE6E7C27C,
4050xF427742C407ACC,0x511B1D8D9D297043,0xA8961E19413A231E,0x29F16FE71020A7D};
406#else
407const fp fp_1 = {0x1};
408#endif
409
410#define pbits 6143
411#define itch_size 386
412
413#elif defined P8191m78l338
414const fp p = {
4150xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4160xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4170xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4180xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4190xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4200xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4210xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4220xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4230xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4240xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4250xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4260xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4270xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4280xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4290xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4300xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4310xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4320xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4330xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4340xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0x3EAF65A95F0041EC,0x372B7D9154133882,
4350x5A58A580E1CA9829,0x8FC4156DDCAD437,0x4CE6AE3C63765131,0x4F3865F90F46D0D3,
4360xB6AA2C454C34E51B,0xD434D3F80A147B77,0x6B926F74A2AA5C76,0x43BCB530BDFEAFF9,
4370x671D6CE9572B43C1,0xD5B30D80ECB73020,0xF823265621739F49,0xC1754744306061CA,
4380x6171E42D89E177BB,0x8994F48EF23A7F2A,0xA2057C82B399C3AF,0xC60CD8BEC9D528B1,
4390xB9B5FAB739469676,0x601A2E4779AEC853,0xE00D857E16B58377,0xE65DEF66D0C08A1D,
4400x26692BC11E11E82B,0x3A2B8F6CD365560D,0x39E653855729C7FB,0xC10B3B5E0D9DE1C4,
4410x7D13530314EEC59E,0xD0A1B556BFEAF779,0xE63C16F48D4938B9,0x3839DF74876C52B0,
4420x5AD0EACB1BD7283,0xC1709D8F85717F0F,0x185BC2F57DE71EB1,0x2F9EC8170F78D4E0,
4430xF519D562D85DB142,0x9CCB77F2238053C5,0x6BB5CF773506E8B0,0x2770E39BEED00FEB,
4440x3A51E0099D663BC,0x5E93F3908FA8986E,0x4AE63438608085B,0x5290F3FDF0F9F666,
4450xA5E5B7F7D86B7F44,0xAB4BD70919AC3458,0x60473AD832847641,0xC35589BD7E5B6D68,
4460x60340C810D6E6475,0xDA4E9331BBBE84E,0x8726969D65FA39A0,0x558064826AE53F6C};
447const fp r_squared_mod_p = {
4480x48FF50537902DF76,0xC2BEB8EDB7A746B,0xB191B393624EDDC9,0x5FDA25C18B693E94,
4490x8EC0B349149054A6,0xFEB68765452E6B6A,0x997E5330C0C214A4,0x3A15A96F06078DA8,
4500x114440E55C5C16E3,0x657C50D8C556322A,0x8D824EF35CC9B18D,0x62FAFDB9455B9877,
4510xBE7240C977BCF4C,0x428F91F09E626C35,0xB3AD14DCFEA6FE33,0x71D3C4CA016B49C9,
4520x7A6507B9299BDEAC,0x7B173AD40A91FC44,0x62BB05E87C5FD442,0x246BFD096A84F103,
4530x52426D6B9D8D47A0,0xE4BB917FB1C2191A,0xDC302C94A13C92CB,0xCEC02FCE33EB1809,
4540x144A90E21B0FD055,0xB130558FD3E7EC12,0x50EDC3B6EC344C9C,0x78AF9F52007E33B3,
4550x3FAA15C53BCC5183,0x2628B54F4D59AC4C,0xCC359C24C3C7C82A,0xB662FBE71ABD79A2,
4560x296BECB123B6B471,0xF13E060D6052DE41,0x97D247DC121FFAB1,0xEA937D00ACCB3BE4,
4570xF2C874424CF7EB45,0xE8A67AD0845E9875,0xFAE9B4C2E5283A3E,0xDEFC7887D66FB83B,
4580xC55961942EF56D88,0x1AE6877A81698BC1,0x5E4CCB8CAE5707B5,0x9E3C703DAE834CE9,
4590x21BD61882F660152,0xEA67C38767B0EA6A,0x7F17A3A0C007B8B,0xE5EFD3AFA361609F,
4600x42A48A60C15039E5,0x1BEFB92014D5A27F,0xBAB513F5A85B6C97,0x48497BC3DAFDFD67,
4610xF6AEFD7454DA6CA3,0x8653F0E4E90C5C1C,0xC66FD5575688B975,0x1CDF192DD0C47003,
4620x73651F8CAF8A560F,0x44BB58AD2A71CEA7,0xAFC1E3C7015AB065,0xAB3EE8FF78E441A9,
4630xD6C7D1DA506E9FAB,0x82209BED877C18BC,0xBC031C142567844A,0xC5C44F43AE219313,
4640xE80DF29EF7AEB3A7,0x855E6B20D289958C,0xA220CE015E72C732,0x3DE8A8719186E78,
4650xE11BCFB54DA98548,0xAF1C327CAE6C1827,0xF65F9E16613B1391,0x2774565DBC69AC86,
4660x69697E5E51691FDE,0x608818EEF0DFFD96,0x55CA4061CC449193,0x29C1A1E8A35AC7CB,
4670x145F101B409B52B4,0xB4EA6C8481F57E5C,0xF09202C4AAD55D3B,0xE2644022177A7FA3,
4680x9CC07785AA9B9F38,0x24B17A53135A229D,0xE1FB1336D31DC070,0x50EB148BCC994A27,
4690x67CBECB045BB084,0x1B0BD0A9C615171A,0xCA4A91EFA19E077A,0x42833091585C4ED7,
4700x8FC8248CFECAF72,0xEFA12B7288486DF7,0xF365FBFE0EA83E,0x6C1B1B5AAEB30EC8,
4710x386FCBE212B6F633,0x1C65928B7A29950D,0x93724C20857408F8,0x733DA9C0AD2C19D4,
4720xF5F4C19CDF63C776,0x9474B3E83AE8DA02,0x7C0416C6FCC8F539,0xA88F54B7B22668CE,
4730x92723D98C0E86A7A,0xF594A7E3EA441D17,0x5F7F84030289FF60,0x72F9FE14C36C5315,
4740xD374A0AB55064EC1,0x822E5D285D11603C,0xE604BBE0F25F32CE,0x20D8C78F74BD9BAB,
4750x7E07F1D70E7FDD4D,0x5E85DA008ABDD2DA,0xDA2C31523BFA23C4,0x6AA4E64DA533D8F4,
4760x3F3B77AB6ACAE50A,0x71400272D9A719BA,0x8AC44AFF353CDBE6,0xE9ADFEB168F160DE,
4770xDB47CE8BC7ED6316,0xEB4F4E96A9EA264C,0xE00D4B721E7214C5,0xDC76C130E053F1A0,
4780xB7D491D182E1AA8E,0xB45BFE9C337633FF,0xBEA6012EBD1DA3B2,0x5FAA8D00E3A6AAE4,
4790xD2658839BF7F1B99,0xE44E63752C7AE340,0x416A67E82F55E73B,0x3B636BC92F968203};
480const fp p_minus_2 = {
4810xFFFFFFFFFFFFFFFD,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4820xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4830xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4840xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4850xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4860xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4870xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4880xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4890xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4900xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4910xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4920xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4930xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4940xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4950xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4960xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4970xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4980xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
4990xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
5000xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0x3EAF65A95F0041EC,0x372B7D9154133882,
5010x5A58A580E1CA9829,0x8FC4156DDCAD437,0x4CE6AE3C63765131,0x4F3865F90F46D0D3,
5020xB6AA2C454C34E51B,0xD434D3F80A147B77,0x6B926F74A2AA5C76,0x43BCB530BDFEAFF9,
5030x671D6CE9572B43C1,0xD5B30D80ECB73020,0xF823265621739F49,0xC1754744306061CA,
5040x6171E42D89E177BB,0x8994F48EF23A7F2A,0xA2057C82B399C3AF,0xC60CD8BEC9D528B1,
5050xB9B5FAB739469676,0x601A2E4779AEC853,0xE00D857E16B58377,0xE65DEF66D0C08A1D,
5060x26692BC11E11E82B,0x3A2B8F6CD365560D,0x39E653855729C7FB,0xC10B3B5E0D9DE1C4,
5070x7D13530314EEC59E,0xD0A1B556BFEAF779,0xE63C16F48D4938B9,0x3839DF74876C52B0,
5080x5AD0EACB1BD7283,0xC1709D8F85717F0F,0x185BC2F57DE71EB1,0x2F9EC8170F78D4E0,
5090xF519D562D85DB142,0x9CCB77F2238053C5,0x6BB5CF773506E8B0,0x2770E39BEED00FEB,
5100x3A51E0099D663BC,0x5E93F3908FA8986E,0x4AE63438608085B,0x5290F3FDF0F9F666,
5110xA5E5B7F7D86B7F44,0xAB4BD70919AC3458,0x60473AD832847641,0xC35589BD7E5B6D68,
5120x60340C810D6E6475,0xDA4E9331BBBE84E,0x8726969D65FA39A0,0x558064826AE53F6C};
513const fp inv_min_p_mod_r = {
5140x1,0x0,0x0,0x0,
5150x0,0x0,0x0,0x0,
5160x0,0x0,0x0,0x0,
5170x0,0x0,0x0,0x0,
5180x0,0x0,0x0,0x0,
5190x0,0x0,0x0,0x0,
5200x0,0x0,0x0,0x0,
5210x0,0x0,0x0,0x0,
5220x0,0x0,0x0,0x0,
5230x0,0x0,0x0,0x0,
5240x0,0x0,0x0,0x0,
5250x0,0x0,0x0,0x0,
5260x0,0x0,0x0,0x0,
5270x0,0x0,0x0,0x0,
5280x0,0x0,0x0,0x0,
5290x0,0x0,0x0,0x0,
5300x0,0x0,0x0,0x0,
5310x0,0x0,0x0,0x0,
5320x0,0x0,0x0,0x0,
5330x0,0x0,0x3EAF65A95F0041ED,0x372B7D9154133882,
5340x5A58A580E1CA9829,0x8FC4156DDCAD437,0x4CE6AE3C63765131,0x4F3865F90F46D0D3,
5350xB6AA2C454C34E51B,0xD434D3F80A147B77,0x6B926F74A2AA5C76,0x43BCB530BDFEAFF9,
5360x671D6CE9572B43C1,0xD5B30D80ECB73020,0xF823265621739F49,0xC1754744306061CA,
5370x6171E42D89E177BB,0x8994F48EF23A7F2A,0xA2057C82B399C3AF,0xC60CD8BEC9D528B1,
5380xB9B5FAB739469676,0x601A2E4779AEC853,0xE00D857E16B58377,0xE65DEF66D0C08A1D,
5390x26692BC11E11E82B,0x3A2B8F6CD365560D,0x39E653855729C7FB,0xC10B3B5E0D9DE1C4,
5400x7D13530314EEC59E,0xD0A1B556BFEAF779,0xE63C16F48D4938B9,0x3839DF74876C52B0,
5410x5AD0EACB1BD7283,0xC1709D8F85717F0F,0x185BC2F57DE71EB1,0x2F9EC8170F78D4E0,
5420xF519D562D85DB142,0x9CCB77F2238053C5,0x6BB5CF773506E8B0,0x2770E39BEED00FEB,
5430x3A51E0099D663BC,0x5E93F3908FA8986E,0x4AE63438608085B,0x5290F3FDF0F9F666,
5440xA5E5B7F7D86B7F44,0xAB4BD70919AC3458,0x60473AD832847641,0xC35589BD7E5B6D68,
5450x60340C810D6E6475,0xDA4E9331BBBE84E,0x8726969D65FA39A0,0x558064826AE53F6C};
546
547#ifdef MONTGOMERY
548const fp fp_1 = {
5490x2,0x0,0x0,0x0,
5500x0,0x0,0x0,0x0,
5510x0,0x0,0x0,0x0,
5520x0,0x0,0x0,0x0,
5530x0,0x0,0x0,0x0,
5540x0,0x0,0x0,0x0,
5550x0,0x0,0x0,0x0,
5560x0,0x0,0x0,0x0,
5570x0,0x0,0x0,0x0,
5580x0,0x0,0x0,0x0,
5590x0,0x0,0x0,0x0,
5600x0,0x0,0x0,0x0,
5610x0,0x0,0x0,0x0,
5620x0,0x0,0x0,0x0,
5630x0,0x0,0x0,0x0,
5640x0,0x0,0x0,0x0,
5650x0,0x0,0x0,0x0,
5660x0,0x0,0x0,0x0,
5670x0,0x0,0x0,0x0,
5680x0,0x0,0x82A134AD41FF7C26,0x91A904DD57D98EFB,
5690x4B4EB4FE3C6ACFAD,0xEE077D52446A5791,0x6632A38739135D9D,0x618F340DE1725E59,
5700x92ABA775679635C9,0x5796580FEBD70910,0x28DB2116BAAB4712,0x7886959E8402A00D,
5710x31C5262D51A9787D,0x5499E4FE26919FBF,0xFB9B353BD18C16C,0x7D1571779F3F3C6A,
5720x3D1C37A4EC3D1088,0xECD616E21B8B01AB,0xBBF506FA98CC78A0,0x73E64E826C55AE9C,
5730x8C940A918D72D312,0x3FCBA3710CA26F58,0x3FE4F503D294F911,0x334421325E7EEBC4,
5740xB32DA87DC3DC2FA8,0x8BA8E126593553E5,0x8C3358F551AC7009,0x7DE98943E4C43C77,
5750x5D959F9D62274C2,0x5EBC9552802A110D,0x3387D216E56D8E8C,0x8F8C4116F1275A9E,
5760xF4A5E2A69C851AF9,0x7D1EC4E0F51D01E1,0xCF487A150431C29C,0xA0C26FD1E10E563F,
5770x15CC553A4F449D7B,0xC669101BB8FF5874,0x2894611195F22E9E,0xB11E38C8225FE029,
5780xF8B5C3FECC533887,0x42D818DEE0AECF23,0xF6A33978F3EFEF49,0x5ADE18041E0C1333,
5790xB43490104F290177,0xA96851EDCCA7974E,0x3F718A4F9AF7137C,0x7954EC850349252F,
5800x3F97E6FDE5233714,0xE4B62D99C8882F63,0xF1B2D2C5340B8CBF,0x54FF36FB2A358126};
581#else
582const fp fp_1 = {0x1};
583#endif
584
585#define pbits 8191
586#define itch_size 516
587
588#elif defined P9215m85l389
589const fp p = {
5900xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
5910xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
5920xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
5930xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
5940xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
5950xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
5960xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
5970xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
5980xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
5990xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6000xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6010xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6020xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6030xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6040xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6050xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6060xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6070xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6080xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6090xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6100xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6110xFFFFFFFFFFFFFFFF,0xD4EB2E32201FF538,0x9731F6B12064E278,0x68F5236C9A6E8EEB,
6120x6FF70217C7682DD9,0xD996C5CAFCAB6BA6,0xEE5EF78FD74361DB,0x3BA7F52C9AA6F698,
6130xC9BEDE007C259BF0,0xD9A864CC7D33B52C,0x440F7936394BF5B6,0xCF4B1FD62F49C859,
6140x92D044003F20EADC,0xCD842B3809D80C8E,0x2FBDB1D89B9D569F,0x613F115278C53010,
6150xB95DE73343F27240,0xC92888276CA27909,0x28839A94D3CA2D5F,0x93147941B2E308,
6160x745BCF59034C79D5,0x73C37E1E3AE8FC67,0x2E9DE986D4FC8646,0x33859631C10023B1,
6170x15A2A2E2188C4BEC,0xBF8F6740D0BAE643,0x42FEB9CCCF7D3200,0x792C49D34520B80E,
6180x83959EC2A5E959BB,0xF6BB457B67E4747,0xCC1CA65F453F0CE5,0xCD0FC61342EC7176,
6190x45FA3489D307DC18,0xDA7FA26690C6E0F6,0x144DB37F4D0B736D,0x2F53EAEDABBEB338,
6200xA7015C360AFA08C0,0x282F93BFA396C390,0x701BE8C44F787FAD,0x5530DBBAB892409E,
6210x36E5E81E4162EAEE,0xBB332AD4236A07AD,0x3276B28E0577E3F1,0xA973F305069CC11E,
6220xDDD71DAAC305A437,0x21B47A8072B86EAE,0x799455FDCD01F2FF,0xFF4E3D96380C1004,
6230x3AF56DDA678BFF86,0xA882C926E07337F9,0xEB2143236B97EBF1,0x3A70A1E85E02F35A,
6240x49BDF004F95AC7F6,0x380D448104A8EB09,0x704E29C40AB77B69,0x199F2E3A6D2E23AC,
6250xA5252A0EFC013C8C,0x38CABDE8DD5935A4,0x57DEA1BECC1C7D9A,0x71A72AD537EA0C9E};
626
627const fp r_squared_mod_p = {
6280xA9AF7454F03D753C,0xFEE65A88EB10B5EA,0x4980B568F42EF7C1,0xB9D6862C549712E1,
6290xF4239DA640C945A8,0x84EE9556F038099A,0x9CCA409764812D51,0xB8EDDA69575EE654,
6300x150EBAF6B58EABD7,0x392BB3D9715CA58,0x202D9EEF0B9F5FC2,0x38847E9AAD3A47B5,
6310x51284A9012387F18,0xCDDEC9C363F777FE,0x1FBB90D81871E7A7,0x1688191F2B2EC4F8,
6320xFFEB61B2BEA7F4A3,0x73E922B23B71CDEC,0xDE544F4141AAE2FC,0xF90F8873A82100DA,
6330x613C7FF306B3AF8D,0x29D174286C1B2CDA,0x35E90A4395B92C78,0x2B2D6281513FC944,
6340xADF9F91549E9746C,0x3E0465589E71470,0x8B7B897823DC3A6A,0x74A3C4C0D12846FB,
6350xAD92B4AB385A3DB3,0xA3930061C92CFA0E,0x5F781937AE64D117,0x82C6215777B68905,
6360xDEF3C3145BC7B2F1,0x87F24F8F4F1E112F,0x314DFF2126BA61E5,0x31C281579EAE9897,
6370x9648810196467FCE,0xFE980E1121BD36DE,0xB2B9C6C30845A92C,0xE5F4ACE5ED6AF632,
6380xEE18832C0DA0CC25,0xE374111EAB629CE8,0xBEAD1E410C62E6B7,0x1823EA9CBA06F7F,
6390xE1288FED154D1D22,0xD107995A95B70C16,0x8DF03BB2F388753,0x68C6923955CC523F,
6400xF307589064657325,0x7588193C98BDF823,0x875B9F315976F842,0x5060CA00E83DE80F,
6410xAD35983FC3A5F915,0xAC3DD0C5A65E37E9,0xE2BAF636BB430A5A,0x4212254854B97C6,
6420x42A6CE9DFCDCC4B3,0x5F2E08142AA3DB17,0x86101CD89367F9ED,0x1305FE03894E87E2,
6430xB575E9183EF5F2C2,0xB4686F6F1310DFF5,0xC56385D2AD3A78D4,0xD90EE4E134A285E4,
6440x9C2292CD4327FBD6,0x3E7B5C5DBFECAD70,0x3CB62CB331D2741,0x684680AA15395048,
6450xEA7F5161C25758D4,0xBF0D628A9C4CED0B,0xCED6DFD589316357,0xB7F4226B82DF594C,
6460xFD04CFFAFA47D58E,0x5D12E0ACB3D5DB0A,0x5FA0DFEEA4BE8A68,0xDAC197A19D8022F2,
6470x792FCEFB77B0CD73,0x6EF6298AFF9E0071,0x57930BFE77528F10,0xD37C35612EAC87CA,
6480x4C2BFA87F55BB970,0xEE692F062C30EFFA,0x7B15F501C0FF5340,0x7DDC1A91500115A,
6490x66220BB592C92FC9,0xE9BB736255581E82,0x5ECD046373EE709E,0x8CC9480B502C54A2,
6500x1F4F6DE652111980,0xE584B1CE9FE0B22D,0x2CF974040027E2C1,0x41DD0CB68A42D0A2,
6510x9DB76995C1619789,0xB45231FDADA9B1F,0x999061E20793A24,0xA75426534E82053C,
6520x73BD53096A4F0736,0x67AC91E7E98175C5,0xFEF33A48823FE320,0x58A6437B0DC9EE51,
6530xF198D26093E681F4,0x8D561A87BF7A27F5,0xBDBB97CE527941D0,0x9BA8A2D827F45100,
6540x5B51CD62CC9FB4E8,0xDD3487FDBE61CA7C,0x7C45926ABF89F157,0x4D59C72ED024DF9D,
6550x608E0004D1F23117,0xCE15EF66F36DC092,0x22C35E250F3B49CE,0x396E1BCB93EC9421,
6560x447E34615B83E547,0x9854FB6A4F71FDA7,0xA8E9C4A2C61E8144,0x2578212CC18F2F50,
6570x3B47BF383A202BEC,0xDCB1B43AFE8635D4,0x8FADD43B539E2970,0xA3EFAFAB7CEA261F,
6580xAAAD864D0F60BE2D,0xCD56237772DB347B,0xEEEB874A946746A7,0x2DC373A87E502A2C,
6590xF7F73FEF213B1459,0xB377C5AF338F5BC0,0x7EC5C0C013C8AE60,0xFC85631CD8E9C939,
6600x7BBDA6593FEC2B29,0x43B0CD93CC2FE31E,0xE66717D87EEEAB5E,0xD85DA70EB28567A3,
6610xDB1999D954EEDE09,0xA98EE87A72267CB4,0xDFCCB4FAA2C1C0F3,0x36DFEA217B6EEC6E,
6620x14C0C6824F2108CD,0xF8184FC9A5EF1F26,0x10417975DEC645D8,0xFF1B45F96B8243F5,
6630x60904FE88DADDE7E,0xAD3FF045EBA9C25A,0x41C148DF8BD37786,0x292D4073D89AAF2B};
664
665const fp p_minus_2 = {
6660xFFFFFFFFFFFFFFFD,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6670xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6680xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6690xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6700xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6710xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6720xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6730xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6740xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6750xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6760xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6770xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6780xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6790xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6800xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6810xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6820xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6830xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6840xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6850xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6860xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,0xFFFFFFFFFFFFFFFF,
6870xFFFFFFFFFFFFFFFF,0xD4EB2E32201FF538,0x9731F6B12064E278,0x68F5236C9A6E8EEB,
6880x6FF70217C7682DD9,0xD996C5CAFCAB6BA6,0xEE5EF78FD74361DB,0x3BA7F52C9AA6F698,
6890xC9BEDE007C259BF0,0xD9A864CC7D33B52C,0x440F7936394BF5B6,0xCF4B1FD62F49C859,
6900x92D044003F20EADC,0xCD842B3809D80C8E,0x2FBDB1D89B9D569F,0x613F115278C53010,
6910xB95DE73343F27240,0xC92888276CA27909,0x28839A94D3CA2D5F,0x93147941B2E308,
6920x745BCF59034C79D5,0x73C37E1E3AE8FC67,0x2E9DE986D4FC8646,0x33859631C10023B1,
6930x15A2A2E2188C4BEC,0xBF8F6740D0BAE643,0x42FEB9CCCF7D3200,0x792C49D34520B80E,
6940x83959EC2A5E959BB,0xF6BB457B67E4747,0xCC1CA65F453F0CE5,0xCD0FC61342EC7176,
6950x45FA3489D307DC18,0xDA7FA26690C6E0F6,0x144DB37F4D0B736D,0x2F53EAEDABBEB338,
6960xA7015C360AFA08C0,0x282F93BFA396C390,0x701BE8C44F787FAD,0x5530DBBAB892409E,
6970x36E5E81E4162EAEE,0xBB332AD4236A07AD,0x3276B28E0577E3F1,0xA973F305069CC11E,
6980xDDD71DAAC305A437,0x21B47A8072B86EAE,0x799455FDCD01F2FF,0xFF4E3D96380C1004,
6990x3AF56DDA678BFF86,0xA882C926E07337F9,0xEB2143236B97EBF1,0x3A70A1E85E02F35A,
7000x49BDF004F95AC7F6,0x380D448104A8EB09,0x704E29C40AB77B69,0x199F2E3A6D2E23AC,
7010xA5252A0EFC013C8C,0x38CABDE8DD5935A4,0x57DEA1BECC1C7D9A,0x71A72AD537EA0C9E};
702
703const fp inv_min_p_mod_r = {
7040x1,0x0,0x0,0x0,
7050x0,0x0,0x0,0x0,
7060x0,0x0,0x0,0x0,
7070x0,0x0,0x0,0x0,
7080x0,0x0,0x0,0x0,
7090x0,0x0,0x0,0x0,
7100x0,0x0,0x0,0x0,
7110x0,0x0,0x0,0x0,
7120x0,0x0,0x0,0x0,
7130x0,0x0,0x0,0x0,
7140x0,0x0,0x0,0x0,
7150x0,0x0,0x0,0x0,
7160x0,0x0,0x0,0x0,
7170x0,0x0,0x0,0x0,
7180x0,0x0,0x0,0x0,
7190x0,0x0,0x0,0x0,
7200x0,0x0,0x0,0x0,
7210x0,0x0,0x0,0x0,
7220x0,0x0,0x0,0x0,
7230x0,0x0,0x0,0x0,
7240x0,0x0,0x0,0x0,
7250x0,0xD4EB2E32201FF539,0x9731F6B12064E278,0x68F5236C9A6E8EEB,
7260x6FF70217C7682DD9,0xD996C5CAFCAB6BA6,0xEE5EF78FD74361DB,0x3BA7F52C9AA6F698,
7270xC9BEDE007C259BF0,0xD9A864CC7D33B52C,0x440F7936394BF5B6,0xCF4B1FD62F49C859,
7280x92D044003F20EADC,0xCD842B3809D80C8E,0x2FBDB1D89B9D569F,0x613F115278C53010,
7290xB95DE73343F27240,0xC92888276CA27909,0x28839A94D3CA2D5F,0x93147941B2E308,
7300x745BCF59034C79D5,0x73C37E1E3AE8FC67,0x2E9DE986D4FC8646,0x33859631C10023B1,
7310x15A2A2E2188C4BEC,0xBF8F6740D0BAE643,0x42FEB9CCCF7D3200,0x792C49D34520B80E,
7320x83959EC2A5E959BB,0xF6BB457B67E4747,0xCC1CA65F453F0CE5,0xCD0FC61342EC7176,
7330x45FA3489D307DC18,0xDA7FA26690C6E0F6,0x144DB37F4D0B736D,0x2F53EAEDABBEB338,
7340xA7015C360AFA08C0,0x282F93BFA396C390,0x701BE8C44F787FAD,0x5530DBBAB892409E,
7350x36E5E81E4162EAEE,0xBB332AD4236A07AD,0x3276B28E0577E3F1,0xA973F305069CC11E,
7360xDDD71DAAC305A437,0x21B47A8072B86EAE,0x799455FDCD01F2FF,0xFF4E3D96380C1004,
7370x3AF56DDA678BFF86,0xA882C926E07337F9,0xEB2143236B97EBF1,0x3A70A1E85E02F35A,
7380x49BDF004F95AC7F6,0x380D448104A8EB09,0x704E29C40AB77B69,0x199F2E3A6D2E23AC,
7390xA5252A0EFC013C8C,0x38CABDE8DD5935A4,0x57DEA1BECC1C7D9A,0x71A72AD537EA0C9E};
740
741#ifdef MONTGOMERY
742const fp fp_1 = {
7430x2,0x0,0x0,0x0,
7440x0,0x0,0x0,0x0,
7450x0,0x0,0x0,0x0,
7460x0,0x0,0x0,0x0,
7470x0,0x0,0x0,0x0,
7480x0,0x0,0x0,0x0,
7490x0,0x0,0x0,0x0,
7500x0,0x0,0x0,0x0,
7510x0,0x0,0x0,0x0,
7520x0,0x0,0x0,0x0,
7530x0,0x0,0x0,0x0,
7540x0,0x0,0x0,0x0,
7550x0,0x0,0x0,0x0,
7560x0,0x0,0x0,0x0,
7570x0,0x0,0x0,0x0,
7580x0,0x0,0x0,0x0,
7590x0,0x0,0x0,0x0,
7600x0,0x0,0x0,0x0,
7610x0,0x0,0x0,0x0,
7620x0,0x0,0x0,0x0,
7630x0,0x0,0x0,0x0,
7640x0,0x5629A39BBFC0158E,0xD19C129DBF363B0E,0x2E15B926CB22E228,
7650x2011FBD0712FA44D,0x4CD2746A06A928B3,0x234210E051793C48,0x88B015A6CAB212CE,
7660x6C8243FF07B4C81F,0x4CAF3667059895A6,0x77E10D938D681492,0x6169C053A16C6F4D,
7670xDA5F77FF81BE2A46,0x64F7A98FEC4FE6E2,0xA0849C4EC8C552C0,0x3D81DD5B0E759FDF,
7680x8D443199781B1B7F,0x6DAEEFB126BB0DEC,0xAEF8CAD6586BA540,0xFED9D70D7C9A39EF,
7690x1748614DF9670C55,0x187903C38A2E0731,0xA2C42CF25606F373,0x98F4D39C7DFFB89D,
7700xD4BABA3BCEE76827,0x80E1317E5E8A3379,0x7A028C6661059BFE,0xDA76C5975BE8FE3,
7710xF8D4C27AB42D4C89,0xE128975093037170,0x67C6B3417581E635,0x65E073D97A271D12,
7720x740B96EC59F047CE,0x4B00BB32DE723E13,0xD764990165E91924,0xA1582A24A882998F,
7730xB1FD4793EA0BEE7F,0xAFA0D880B8D278DE,0x1FC82E77610F00A5,0x559E488A8EDB7EC3,
7740x92342FC37D3A2A23,0x8999AA57B92BF0A5,0x9B129AE3F510381C,0xAD1819F5F2C67DC3,
7750x4451C4AA79F4B790,0xBC970AFF1A8F22A2,0xCD7540465FC1A01,0x16384D38FE7DFF7,
7760x8A15244B30E800F2,0xAEFA6DB23F19900D,0x29BD79B928D0281C,0x8B1EBC2F43FA194A,
7770x6C841FF60D4A7013,0x8FE576FDF6AE29ED,0x1F63AC77EA91092D,0xCCC1A38B25A3B8A7,
7780xB5B5ABE207FD86E7,0x8E6A842E454D94B6,0x5042BC8267C704CB,0x1CB1AA55902BE6C3};
779#else
780const fp fp_1 = {0x1};
781#endif
782#define pbits 9215
783#define itch_size 578
784
785#endif
786
787const fp fp_0 = {0x0};
788
789void fp_enc(fp a, fp const b)
790{
791#ifdef MONTGOMERY
792 fp_mul(a, b, r_squared_mod_p);
793 CNT_FP_MUL_DEC();
794#else
795 //(void) a;
796 //(void) b;
797 fp_copy(a, b);
798#endif
799}
800void fp_dec(fp a, fp const b)
801{
802#ifdef MONTGOMERY
803 fp_mul(a, b, uintbig_1);
804 CNT_FP_MUL_DEC();
805#else
806 //(void) a;
807 //(void) b;
808 fp_copy(a, b);
809#endif
810}
811
812void fp_pow(fp b, const fp e, const fp a)
813{
814 // It is required that e > 0.
815 if (fp_iszero(e))
816 {
817 fp_set1(b);
818 }
819 else
820 {
821 fp tmp;
822 fp_copy(tmp, a);
823 fp_dec(tmp, tmp);
824 mp_size_t pow_size = mpn_sec_powm_itch(NUMBER_OF_WORDS, NUMBER_OF_WORDS, NUMBER_OF_WORDS);
825 uint64_t tp_pow[pow_size];
826 mpn_sec_powm(b, tmp, NUMBER_OF_WORDS, e, NUMBER_OF_WORDS, p, NUMBER_OF_WORDS, tp_pow);
827 fp_enc(b, b);
828 }
829}
830
831// static void reduce_once(fp x)
832// {
833// fp tmp;
834// if (!mpn_sub_n(tmp, x, p, NUMBER_OF_WORDS))
835// {
836// fp_copy(x, tmp);
837// }
838// }
839
840void fp_cswap(fp x, fp y, uint8_t c)
841{
842
843 // uint64_t tmp, c64;
844
845 // c64 = (uint64_t)-c;
846 // for (int i = 0; i < NUMBER_OF_WORDS; i++)
847 // {
848 // tmp = (y[i] ^ x[i]) & c64;
849 // x[i] ^= tmp;
850 // y[i] ^= tmp;
851 // }
852
853 mpn_cnd_swap(c, x, y, NUMBER_OF_WORDS);
854}
855
856void fp_copy(fp b, const fp a)
857{
858 for (uint8_t i = 0; i < NUMBER_OF_WORDS; i++)
859 {
860 b[i] = a[i];
861 }
862}
863
864void fp_add(fp c, const fp a, const fp b)
865{
866 // (void)mpn_add_n(c, a, b, NUMBER_OF_WORDS);
867 // CNT_FP_ADD_INC();
868 // reduce_once(c);
869 (void)mpn_add_n(c, a, b, NUMBER_OF_WORDS);
870 mpn_cnd_sub_n(mpn_cmp(c, p, NUMBER_OF_WORDS) > 0, c, c, p, NUMBER_OF_WORDS);
871 CNT_FP_ADD_INC();
872}
873
874void fp_sub(fp c, const fp a, const fp b)
875{
876 // mp_limb_t borrow = mpn_sub_n(c, a, b, NUMBER_OF_WORDS);
877 // CNT_FP_ADD_INC();
878 // if (borrow)
879 // {
880 // mpn_add_n(c, c, p, NUMBER_OF_WORDS);
881 // }
882
883 mpn_cnd_add_n(mpn_sub_n(c, a, b, NUMBER_OF_WORDS), c, c, p, NUMBER_OF_WORDS);
884 CNT_FP_ADD_INC();
885}
886
887/*
888 see Algorithm 14.36 "Montgomery multiplication"
889 https://cacr.uwaterloo.ca/hac/about/chap14.pdf
890*/
891void fp_mul(fp c, const fp a, const fp b)
892{
893#ifdef MONTGOMERY
894 static __thread uint64_t tp[itch_size];
895
896 // mp_size_t size = mpn_sec_mul_itch(NUMBER_OF_WORDS, 1) ;
897 uint64_t A[NUMBER_OF_WORDS + 1] = {0x0};
898 uint64_t tmp_1[NUMBER_OF_WORDS + 1] = {0x0};
899 uint64_t tmp_2[NUMBER_OF_WORDS + 2] = {0x0};
900 uint64_t a_i[1] = {0x0};
901 for (int i = 0; i < NUMBER_OF_WORDS; i++)
902 {
903 // tmp_1 = x_i * y
904 a_i[0] = a[i];
905 mpn_sec_mul(tmp_1, b, NUMBER_OF_WORDS, a_i, 1, tp);
906
907 // tmp_2 = A + x_i * y
908 mpn_add(tmp_2, A, NUMBER_OF_WORDS + 1, tmp_1, NUMBER_OF_WORDS + 1);
909
910 // tmp_1 = u_i * m
911 mpn_sec_mul(tmp_1, p, NUMBER_OF_WORDS, tmp_2, 1, tp);
912
913 // tmp_1 = A + x_i * y + u_i * m
914 mpn_add(tmp_1, tmp_1, NUMBER_OF_WORDS + 1, tmp_2, NUMBER_OF_WORDS + 2);
915
916 // A = (A + x_i * y + u_i * m) / r
917 mpn_copyd(A, tmp_1 + 1, NUMBER_OF_WORDS);
918
919 A[NUMBER_OF_WORDS] = 0;
920 }
921
922 mpn_cnd_sub_n(mpn_cmp(A, p, NUMBER_OF_WORDS) > 0, c, A, p, NUMBER_OF_WORDS);
923
924#else
925#ifndef USE_GMP_SEC_FUNCTIONS
926 uint64_t tmp[NUMBER_OF_WORDS * 2];
927 uint64_t thrash[NUMBER_OF_WORDS + 1];
928 mpn_mul_n(tmp, a, b, NUMBER_OF_WORDS);
929 mpn_tdiv_qr(thrash, c, 0, tmp, 2 * NUMBER_OF_WORDS, p, NUMBER_OF_WORDS);
930#else
931 static __thread uint64_t tp[itch_size];
932 uint64_t tmp[NUMBER_OF_WORDS * 2];
933 mpn_sec_mul(tmp, a, NUMBER_OF_WORDS, b, NUMBER_OF_WORDS, tp);
934 mpn_sec_div_r(tmp, 2 * NUMBER_OF_WORDS, p, NUMBER_OF_WORDS, tp);
935 fp_copy(c, tmp);
936#endif
937#endif
938
939 CNT_FP_MUL_INC();
940}
941
942void fp_sqr(fp b, const fp a)
943{
944#ifdef MONTGOMERY
945 // fp_mul(b, a, a);
946 // CNT_FP_MUL_DEC();
947
948 uint64_t tmp[NUMBER_OF_WORDS * 2];
949 mpn_sqr(tmp, a, NUMBER_OF_WORDS);
950 fp_mont_redc(b, tmp);
951
952#else
953#ifndef USE_GMP_SEC_FUNCTIONS
954 uint64_t tmp[NUMBER_OF_WORDS * 2];
955 uint64_t thrash[NUMBER_OF_WORDS + 1];
956 mpn_sqr(tmp, a, NUMBER_OF_WORDS);
957 mpn_tdiv_qr(thrash, b, 0, tmp, 2 * NUMBER_OF_WORDS, p, NUMBER_OF_WORDS);
958#else
959 fp_mul(b, a, a);
960 CNT_FP_MUL_DEC();
961// mpn_sec_sqr(tmp, a, NUMBER_OF_WORDS, tp);
962// mpn_sec_div_r(tmp, 2 * NUMBER_OF_WORDS, p, NUMBER_OF_WORDS, tp);
963#endif
964#endif
965 CNT_FP_SQR_INC();
966}
967
968bool fp_issquare(fp const a)
969{
970 mpz_t mpzx, mpzp;
971 int s = mpz_legendre(mpz_roinit_n(mpzx, a, NUMBER_OF_WORDS), mpz_roinit_n(mpzp, p, NUMBER_OF_WORDS));
972 return s + 1;
973}
974
975void fp_inv(fp x)
976{
977#if defined(USE_GMP_SEC_FUNCTIONS) || defined(MONTGOMERY)
978 static __thread uint64_t tp[itch_size];
979#endif
980#ifdef MONTGOMERY
981 fp_dec(x, x);
982 fp tmp;
983 fp_copy(tmp, x);
984 mpn_sec_invert(x, tmp, p, NUMBER_OF_WORDS, (unsigned int)(2 * NUMBER_OF_WORDS * mp_bits_per_limb), tp);
985 fp_enc(x, x);
986#else
987#ifndef USE_GMP_SEC_FUNCTIONS
988 mpz_t res, mpzx, mpzp;
989 mpz_init(res);
990 mpz_roinit_n(mpzx, x, NUMBER_OF_WORDS);
991 mpz_roinit_n(mpzp, p, NUMBER_OF_WORDS);
992 mpz_invert(res, mpzx, mpzp);
993 int i = 0;
994 for (; i < res->_mp_size; ++i)
995 {
996 x[i] = ((uint64_t *)res->_mp_d)[i];
997 }
998 for (; i < NUMBER_OF_WORDS; ++i)
999 {
1000 x[i] = 0;
1001 }
1002 mpz_clear(res);
1003#else
1004 fp tmp;
1005 fp_copy(tmp, x);
1006 mpn_sec_invert(x, tmp, p, NUMBER_OF_WORDS, (unsigned int)(2 * NUMBER_OF_WORDS * mp_bits_per_limb), tp);
1007#endif
1008#endif
1009}
1010
1011#ifdef MONTGOMERY
1012/*
1013 see Algorithm 14.32 "Montgomery reduction"
1014 https://cacr.uwaterloo.ca/hac/about/chap14.pdf
1015*/
1016void fp_mont_redc(fp a, const uint64_t b[2 * NUMBER_OF_WORDS])
1017{
1018 static __thread uint64_t tp[itch_size];
1019 uint64_t A[2 * NUMBER_OF_WORDS + 1] = {0x0};
1020 // uint64_t a_i[1] = {0x0};
1021 uint64_t tmp_1[NUMBER_OF_WORDS + 1] = {0x0};
1022
1023 // 1. A = T
1024 mpn_copyd(A, b, 2 * NUMBER_OF_WORDS);
1025
1026 for (int i = 0; i < NUMBER_OF_WORDS; i++)
1027 {
1028 // 2.1 u_i = a_i * m' mod b
1029 // since montgomery friendly m' = 1
1030 // a_i[0] = A[i];
1031
1032 // 2.2 tmp_1 = u_i * m
1033 mpn_sec_mul(tmp_1, p, NUMBER_OF_WORDS, &A[i], 1, tp);
1034
1035 // 2.2 A = A + u_i * m * b^i
1036 mpn_add(A + i, A + i, 2 * NUMBER_OF_WORDS + 1, tmp_1, NUMBER_OF_WORDS + 1);
1037 }
1038
1039 // 3. A = A/b^n
1040 mpn_copyd(a, A + NUMBER_OF_WORDS, NUMBER_OF_WORDS);
1041
1042 // 4. If A > m then A = A - m
1043 mpn_cnd_sub_n(mpn_cmp(a, p, NUMBER_OF_WORDS) > 0, a, a, p, NUMBER_OF_WORDS);
1044}
1045#endif
1046
1047void fp_random(fp x)
1048{
1049 while (1)
1050 {
1051 randombytes(x, sizeof(fp));
1052 uint64_t m = ((uint64_t)1 << pbits % 64) - 1;
1053 x[NUMBER_OF_WORDS - 1] &= m;
1054
1055 for (size_t i = NUMBER_OF_WORDS - 1; i < NUMBER_OF_WORDS; --i)
1056 if (x[i] < p[i])
1057 return;
1058 else if (x[i] > p[i])
1059 break;
1060 }
1061}
randombytes
void randombytes(void *x, size_t l)
Definition rng.c:8
CNT_FP_ADD_INC
#define CNT_FP_ADD_INC()
Definition fp-counters.h:29
CNT_FP_MUL_INC
#define CNT_FP_MUL_INC()
Definition fp-counters.h:30
CNT_FP_MUL_DEC
#define CNT_FP_MUL_DEC()
Definition fp-counters.h:31
CNT_FP_SQR_INC
#define CNT_FP_SQR_INC()
Definition fp-counters.h:32
p
#define p
Definition fp-gmp.h:44
fp_sqr
#define fp_sqr
Definition fp-gmp.h:73
fp
uint64_t fp[NUMBER_OF_WORDS]
Definition fp-gmp.h:22
r_squared_mod_p
#define r_squared_mod_p
Definition fp-gmp.h:29
fp_pow
#define fp_pow
Definition fp-gmp.h:61
fp_sub
#define fp_sub
Definition fp-gmp.h:67
fp_mul
#define fp_mul
Definition fp-gmp.h:70
fp_1
#define fp_1
Definition fp-gmp.h:48
fp_inv
#define fp_inv
Definition fp-gmp.h:88
inv_min_p_mod_r
#define inv_min_p_mod_r
Definition fp-gmp.h:33
fp_issquare
#define fp_issquare
Definition fp-gmp.h:76
fp_0
#define fp_0
Definition fp-gmp.h:50
fp_add
#define fp_add
Definition fp-gmp.h:64
fp_enc
#define fp_enc
Definition fp-gmp.h:55
fp_copy
#define fp_copy
Definition fp-gmp.h:79
fp_cswap
#define fp_cswap
Definition fp-gmp.h:82
p_minus_2
#define p_minus_2
Definition fp-gmp.h:31
fp_random
#define fp_random
Definition fp-gmp.h:85
fp_dec
#define fp_dec
Definition fp-gmp.h:58
uintbig_1
#define uintbig_1
Definition fp-gmp.h:26
itch_size
#define itch_size
Definition fp-karatsuba.c:14
pbits
#define pbits
Definition fp-karatsuba.c:13
fp_mont_redc
void fp_mont_redc(fp a, const uint64_t b[2 *NUMBER_OF_WORDS])
Definition fp-karatsuba.c:100
tests.A
A
Definition tests.py:29
i
for i
Definition prime_search.m:10
a
f a
Definition to_model.m:12