isogeny_walks.h

Go to the documentation of this file.

//
// Isogeny walks via radical computations
//
 
#ifndef SSEC_ISOGENY_WALKS_H
#define SSEC_ISOGENY_WALKS_H
 
#if defined AVX2
#include "../common/fp/avx2/fp-avx2.h"
#elif defined GMP
#include "../common/fp/gmp/fp-gmp.h"
#elif defined KARATSUBA
#include "../common/fp/karatsuba/fp-karatsuba.h"
#else
    #include "../common/fp/mulx/fp.h"
#endif
#include "../common/mont.h"
#include "../common/primes.h"
 
 
#ifdef P2047m1l226
static const fp CUBE_ROOT_EXPONENT_213 = {
0xFFFFFFFFFFFFFFFF, 0x87779EEE93BC7BA1, 0x213C6602AF9EF1A0,
0x6A56E8FD46D70A38, 0xAB213A5B93F1D440, 0x37CD33ED871147E5, 0x1D822425FEF14E21,
0x2F2AC40002044BEC, 0x29CCF47F6DF2198A, 0xE5A1FE21B734CF6E, 0x18C4125AC8667060,
0x91C0851B4368410A, 0xEA9756C5E80606E9, 0x617955512CDB9A15, 0x38F3AC9521916695,
0x1F5E61186736A8A4, 0x93545D3E871FA163, 0x453B5FADAC0A24D5, 0xAE939681BFBF17FC,
0x678629BA3600F7D1, 0x8FB97FB174A1ABD5, 0xC0E77DC404EE1C63, 0x29628E157BAD019A,
0x8125CB1D85152E9D, 0x1C893F6E31689FF6, 0x3E5BCE0B79749A37, 0x3DB7950772C36826,
0xCCCF3352DE900AD6, 0xA9874702325F776, 0x5B1C4FDE8993318C, 0x1E8BCA80234517A5,
0x323B01F1989C3A9A
};
static const fp ONE_HALF = {
0x0000000000000001, 0x34CC919A2265468D, 0xCE2566FBF891958F, 0x607DA28415BD70AB,
0x7F4E2876A215419F, 0x2C4C321BB5661427, 0xD3BCC9C701960ACE, 0xB93FD9FFFCF98E1D,
0xC14C9140DB14D9B0, 0xA78D02CD6D30C8DA, 0xDAD9E477D366576E, 0xA55F38571AE39E70,
0x201CFDD723F6F5A1, 0xEDCA00063CB698DF, 0xAA927D204DA5E61F, 0x50F26E5B652E0309,
0xA301742235508DEB, 0x9826F07B7DF0C8BF, 0x7A229E3D60615C05, 0xE4B6C168AEFE8C45,
0xA869C075D10D7E3F, 0xDEA4C359F89AD56A, 0x41EC2ADFC67C7D97, 0x3E474F53B8603A14,
0x553220DAB5E3100E, 0xA2764AEEC9D118AD, 0xA36CA074D3DAE3C6, 0xCCC93303B227EFBE,
0xF01B5157CB470CCD, 0xF755883231A335AD, 0xD22E503FCB185C87, 0x34A77D159B15A818
};
 
static const fp ONE_THIRD = {
0x5555555555555556, 0xCDDDB666C198D9B3, 0x3418EF52A5B663B4, 0xEAFE6C580E7E4B1D,
0xAA341AF9C1638114, 0x1D882167CE440D6F, 0x37D3312F56640734, 0x262A915553510969,
0x2B8860D5E7633BCB, 0x6FB357339E2085E7, 0x3C9142FA8CEEE4F4, 0xC394D03A11ED144B,
0x6ABDFE8F6D4F4E6B, 0xF3DC00042879BB3F, 0x1C61A8C033C3EEBF, 0x35F6F43CEE1EACB1,
0xC200F816CE35B3F2, 0x1019F5A7A94B307F, 0xA6C1BED395963D59, 0xEDCF2B9B1F545D83,
0xC59BD5A3E0B3A97F, 0x946DD791506738F1, 0x2BF2C73FD9A853BA, 0xD42F8A37D04026B8,
0x38CC15E723ECB55E, 0x16F98749DBE0BB1E, 0x179DC04DE291ED2F, 0x8886220276C54A7F,
0x4ABCE0E5322F5DDE, 0xFA390576CBC223C9, 0x36C98AD532103DAF, 0x231A5363BCB91ABB
};
 
static const fp ONE_NINTH = {
0x1C71C71C71C71C72, 0x99F4922240884891, 0x66B2FA70E1E77691, 0x4E54CEC804D4C3B4,
0x8E115E534076805C, 0x5F2D6077EF6C047A, 0x129BBB0FC776AD11, 0x0CB8DB1C711B0323,
0x0E82CAF1F7CBBE99, 0xCFE672668A0AD74D, 0xBEDB1653844FA1A6, 0x9686F0135B4F06C3,
0x78E9FF85246FC4CE, 0xFBF4000162D33E6A, 0x0975E2EABBEBFA3F, 0x67525169A4B4E43B,
0x40AAFD5CEF673BFB, 0x5AB351E28DC3BAD5, 0x8CEB3F9BDC8769C8, 0xA49A63DE5FC6C9D6,
0xEC894736A03BE32A, 0x3179F285C577BDA5, 0xB950ED15488D713E, 0x9C0FD8BD456AB792,
0xBD995CA2614EE71F, 0x07A8826DF3F593B4, 0x07DF4019F630A465, 0x2D820B56279718D5,
0x6E3EF5A1BB651F4A, 0x536857279940B698, 0x6798839C660569E5, 0x0BB371213EE85E3E
};
 
static const fp ONE_BY_27 = {
0x097B425ED097B426, 0xDDFC30B61582C2DB, 0x223BA8D04B4D2785, 0xC4C6EF98019C413C,
0xDA05CA1BC027801E, 0xCA64757D4FCEAC28, 0xB0DE93AFED278F05, 0xAEE849097B09010B,
0xAF80EE50A7EE94DD, 0x9AA226222E039D19, 0xEA4907712C1A8B37, 0x322CFAB11E6FACEB,
0x284DFFD70C25419A, 0xFEA6AAAB20F114CE, 0x587CA0F8E94EA8BF, 0x77C61B2336E6F6BE,
0x158E54744FCD13FE, 0x1E3BC5F62F413E47, 0x844E6A8949827898, 0x8C33769F75424347,
0xF98317BCE013F663, 0xBB28A62C9727E9E1, 0x3DC5A45C6D847B14, 0x3405483F17239286,
0xE9DDC98B75C4F7B5, 0x028D80CF5151DBE6, 0x57F5155DFCBAE177, 0x6480AE720D325D9C,
0xCF6A51E093CC5FC3, 0xC6781D0D33159232, 0x22882BDECCAC78A1, 0x03E67B0B14F81F6A
};
#endif
 
#ifdef P2047m4l205
static const fp CUBE_ROOT_EXPONENT_213 = {
        0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF,
        0xFFFFFFFFFFFFFFFF, 0xC638EB5843CFFFFF, 0x3597DCAD6317016E, 0x642741FEB670775F,
        0xC9F8CEADD4B2625A, 0x1ABF6F8F673935D2, 0x9D515209928E23CD, 0xA8305AE5D28241C3,
        0x721C932E426A5077, 0xC068596C696E0298, 0xE62279ADF94431FA, 0x8752C725EAD714A8,
        0x68D8BB85C46AA869, 0xD6AD08FED8E8FFED, 0x22C004CC0F7D6FB2, 0xF9C7670629F564CA,
        0x1F5395C34A664FF2, 0xC3A7E869AADDC0C2, 0x3F1A93EEF39867D8, 0xF0C2DA214B09FA03,
        0x367241D4CD7FCD60, 0xDBC00C2B71949FD9, 0x17AE7DCC4231E239, 0x3E78ADFBA5A3170B,
        0x2FBD32BC946988A0, 0x86337E3FC41663FA, 0x7F710347013BA61C, 0xAD27AB62A8E8ADFD,
        0x41DC5EDB807F2382
};
static const fp ONE_HALF = {
        0x0000000000000001, 0x0000000000000000, 0x0000000000000000, 0x0000000000000000,
        0xD6AA9EFB9A480000, 0x2F9C34FBEB5D7DD9, 0x69C51D01EE574CF1, 0xD10AC9FB40F46C78,
        0x57E0D8A8E52A2F43, 0x940604F1A42ACA4C, 0x83B777A7443C9D5A, 0x54D5233A9C60874C,
        0xDF6379DD61DAFC1B, 0xA6CC497B0A19B507, 0xB503D5471FBD6102, 0xE2BAE6B759600361,
        0xBDFC7281BAA2801B, 0xCBDFF8CDE8C3D873, 0x8954E576C10FE8D0, 0xD1029F5B10668813,
        0xDA8423617FB35EDC, 0x21582219929B643A, 0x96DBB8CE0F7108FB, 0x2E549D40CBC04BEE,
        0x365FEDBED5A1103A, 0x5C7A434D9CB52CA9, 0xA24AFB06878B5D6F, 0xB86433E52161B30F,
        0x36B2C2A059DE6A08, 0xC0D67B157E2686D5, 0xFC447EEC02A2FB03, 0x1D3571B6BF414ABB
};
 
static const fp ONE_THIRD = {
        0x5555555555555556, 0x5555555555555555, 0x5555555555555555, 0x5555555555555555,
        0x8F1C69FD11855555, 0x1FBD78A7F23E53E6, 0xF12E13569EE4DDF6, 0x8B5C86A780A2F2FA,
        0x3A95E5C5EE1C1F82, 0xB804034BC2C73188, 0xAD24FA6F82D31391, 0xE338C22712EB04DD,
        0x94ECFBE8EBE752BC, 0x6F32DBA75C11235A, 0xCE028E2F6A7E40AC, 0xEC7C99CF90EAACEB,
        0x7EA84C567C6C5567, 0x3295508945D7E5A2, 0x5B8DEE4F2B5FF08B, 0x3601BF920AEF0562,
        0x91AD6CEBAA779493, 0x163AC16661BCED7C, 0x64927B340A4B5B52, 0x1EE3138087D587F4,
        0x79954929E3C0B57C, 0x3DA6D7891323731B, 0x16DCA759AFB23E4A, 0x25982298C0EBCCB5,
        0xCF21D715913EF15B, 0xD5E4520E5419AF38, 0xA82DA9F2AC6CA757, 0x1378F679D4D631D2
};
 
static const fp ONE_NINTH = {
        0x71C71C71C71C71C7, 0xC71C71C71C71C71C, 0x1C71C71C71C71C71, 0x71C71C71C71C71C7,
        0xE825EE55D269C71C, 0x500B168EACF59CAE, 0x2D22FCC6E58485AC, 0x3E1B3EE4153A2CD6,
        0xF63C59B45850A56A, 0x0BFF54C8B4DECD13, 0xB879D642BF877CBD, 0xDA2134F97CD8D485,
        0x91D880AE83597235, 0x42CCDB641B527A1B, 0x5DAA3DA2C3959FE3, 0xADEB3BB2BD2E3883,
        0x4039489C40989C6E, 0x223C7293C9B159BA, 0x461302F2CE1AAD3E, 0xCC550ABCFE2D7F1A,
        0x3D0DC32E0E41673C, 0xFC4B8A6EEFB5D86B, 0x99E79621FE48C61C, 0xA584D2153EB1BEAC,
        0xC111C923AF5FE1C0, 0xF5B986BE7CCF6CD0, 0x7C308EC662B7A048, 0xCF114F91352E088C,
        0xDD7A5C2712758270, 0x07049CFD9CA662CB, 0x8EA30E578DEDE41C, 0x276BD6EBB1DC4D07
};
 
static const fp ONE_BY_27 = {
        0x25ED097B425ED097, 0xED097B425ED097B4, 0x097B425ED097B425, 0x7B425ED097B425ED,
        0x68F03ACA349DED09, 0xA59B8EDCF2138AFE, 0x7332EB9658474E98, 0x3401E3A48670714C,
        0xC228E2CB84A96CF6, 0xF6A66E4C798312D3, 0x3B03A25167AF6B57, 0xBAD24F816C07ECA4,
        0xF105D9A695367DFF, 0xA7116D7A025FB003, 0xFBE0DBB1815E49F4, 0x4D7C7A16AE24BB3F,
        0x96C02132EE713412, 0xD8D42AFD52B88D9B, 0x112312AC6EA8F3DE, 0x636FEEACF4757A51,
        0x2D57297904F38DD6, 0x9333C213EE2A5AA7, 0x24100C2C9FCCE6B7, 0x184932868D106245,
        0x1C1B4F3756B495C4, 0x6997000BC121B12A, 0xBD33883DC68AF723, 0x1F6DA297A6238B79,
        0xD006F24CCA3D8F75, 0xD71D379B8AC871B5, 0x875E057FD837FA06, 0x4F00512A111DE7DA
};
#endif
 
#ifdef P2047m6l194
static const fp CUBE_ROOT_EXPONENT_213 = {
0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF,
0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xFFFFFFFFFFFFFFFF, 0xBD0B074CFE00024F,
0x4BAC2164C074ACA4, 0x3FBC0A160D91873, 0x5EAC49E6A24559BE, 0xBA25874CAB37A12,
0x3295173C709A30F9, 0x7F4D07FB4DDD8D29, 0x38982EB1A7817B27, 0x5CE0D94B20B1F6D,
0xEDFA5D782487A839, 0x60803CFB001E158B, 0xACA120F6343CDFCD, 0xF93EEFDF2694D458,
0x7BA144949664B562, 0x245E0C6921797563, 0xE86D13238ECE8A77, 0xD7767A664F04BEC8,
0xB947CE2D75033E4C, 0x9A19076B3B42C04E, 0xF7B08D4C3167E010, 0x7EED903D4D70BA72,
0x7A1C12DCAB677198, 0xD38252B330EB8530, 0x3E1B7F2B159AC4DE, 0xAB05F4E16A7BD263,
0x2DAEE4AF4B890CBA
};
static const fp ONE_HALF = {
0x0000000000000001, 0x0000000000000000, 0x0000000000000000, 0x0000000000000000,
0x0000000000000000, 0x0000000000000000, 0xE46F750C82FFFC88, 0x0E7DCDE8DF50FD08,
0xFA065F0DEEBA5B53, 0x71FD91260C97F962, 0x6E8C7B50CFF2C8E4, 0x34205D255718B68A,
0xC10C74070B33AC42, 0x2B1BB9F584BDC744, 0x774AEBA0F4EF50DC, 0x1B0873CBC93483AA,
0xEF3FA4877FD2DFAE, 0xFD0E4E8EB1A4B04B, 0x8A2198314620C17A, 0xC68E19211E68EFEB,
0x4972ED624DC9CFEA, 0xA35C634AA9CA304D, 0xBCCE48668978E1D2, 0xEA144ABBD07B228C,
0x18DA74DF271BDF89, 0x8C772C0DB5E42FE7, 0x419BA7A40BD6E853, 0x48D5E3B4FEE4D59B,
0xC2BC83F3369EB837, 0x22D6C13F5F97D8B1, 0xFF7710ADE046446B, 0x3B79A8F90EB26CE7
};
 
static const fp ONE_THIRD = {
0x5555555555555556, 0x5555555555555555, 0x5555555555555555, 0x5555555555555555,
0x5555555555555555, 0x5555555555555555, 0x984A4E0857555305, 0x09A933F094E0A8B0,
0x515994B3F47C3CE2, 0xF6A90B6EB30FFB97, 0x49B2FCE08AA1DB42, 0x22C03E18E4BB245C,
0xD6084D5A0777C82C, 0x1CBD26A3ADD3DA2D, 0x4F8747C0A34A35E8, 0x675AF7DD30CDAD1C,
0xF4D5185A55373FC9, 0xA8B4345F21187587, 0x5C1665762EC080FC, 0xD9B410C0BEF09FF2,
0x30F748EC33DBDFF1, 0x6CE84231C686CADE, 0x7DDEDAEF0650968C, 0x9C0D8727E0521708,
0xBB3C4DEA1A129506, 0x5DA4C80923ED7544, 0xD667C51807E49AE2, 0xDB394278A9EDE3BC,
0x81D302A22469D024, 0x1739D62A3FBA9076, 0xAA4F6073EAD982F2, 0x27A670A609CC489A
};
 
static const fp ONE_NINTH = {
0x71C71C71C71C71C7, 0xC71C71C71C71C71C, 0x1C71C71C71C71C71, 0x71C71C71C71C71C7,
0xC71C71C71C71C71C, 0x1C71C71C71C71C71, 0xE69E4853F171C77F, 0xFE63CCAD3C853937,
0xC7C667375740A084, 0xD6E3D36D8CD2AB66, 0xF3B780853E3A5B74, 0xFA354AFBD9E0CF45,
0x5C53F31BA96C094D, 0xFB35CEE4B85CB0F8, 0xF2BEC95FE4C8F703, 0xC41B815B22886325,
0xAC87269B9C76CAB3, 0x39374C9ACFD141BE, 0x45FC446C4D8A952B, 0x0661FD3535829002,
0xF7D6C92DF75B5AAD, 0x432E9FA25EE988DA, 0xEB05862D7EF29193, 0x3B5314240547A6D3,
0xE0CB4858FBA791D4, 0x45B9DEA924ADC1C9, 0xDC4409D1540490DA, 0x30CBCA41390304B5,
0xEA5CD4E4F9EE5D4F, 0xA6CBB1A3A00B9296, 0xE39D6FECAE3114D7, 0x240EED39A9089E90
};
 
static const fp ONE_BY_27 = {
0xD097B425ED097B42, 0x97B425ED097B425E, 0xB425ED097B425ED0, 0x25ED097B425ED097,
0xED097B425ED097B4, 0x097B425ED097B425, 0x00BA466D24D098FD, 0x4FF754EC1F116965,
0xEF4002B8782CC1BB, 0xCC4CC0C2801390AB, 0x2C63AC66CF6D30DA, 0xECB1A49CD642B2E9,
0x8917D506DF681F03, 0x455E06FA668A4DE6, 0x7E7BF494FA9DE20D, 0x385BAF2FC8714A7E,
0xE9C280B15EE14E57, 0xBEB854AEB4B985D0, 0x93F38EBE57CDF13A, 0xBFF14C06B25DE007,
0xE4CBF3EE8DDB2E40, 0xDFF0BEC7E70A72D9, 0x64BD1497A7288FEA, 0x1B14EDCD66EED6C2,
0x42A59BD346D93B6E, 0x3DC0E633CF9885F6, 0x88E2CB646D648D82, 0xF7FCA22EBE0A0FB3,
0x628AC5A5EBC53707, 0x8151A576C026934C, 0xF6B77514EF4E4579, 0x22DC6C1588C765E2
};
#endif
 
void isogeny_walks_get_points_3_fp(fp *output, const proj input_A);
void isogeny_walks_to_montgomery_model_3_fp(fp *output_A, const fp *input_t);
void isogeny_walks_3_fp(fp output_A, const proj input_A, size_t input_length, uint8_t direction);
 
#endif // SSEC_ISOGENY_WALKS_H