Quote from: vjudeu on Today at 07:25:38 AM

When we have secp256k1, then gcd between "p-1" and "n-1" is equal to 6. It means, that using lambda and beta is all we can do, because other factors are different, so it is hard to map private and public keys. However, when it comes to secp160k1, it seems to be different:

Code:

p=0xfffffffffffffffffffffffffffffffeffffac73
n=0x0100000000000000000001b8fa16dfab9aca16b6b3
print(factor(p-1))
print(factor(n-1))
print(gcd(p-1,n-1))

This is the output:

Code:

2 * 3 * 5 * 7 * 113 * 61588775277324185343602394973294691093621473
2 * 3 * 5 * 8837 * 42918291593381467397 * 128449012680369359431471
30

Which means, that if the greatest common divisor is equal to 30, instead of 6, then it should be possible to get a better speedup, than by using lambda and beta alone. If so, then how this "efficiently computable endomorphism" looks like for secp160k1? Because using lambda and beta from secp256k1, and changing constants into secp160k1 will obviously give some results, but if the divisor is 30 instead, then I guess those equations are different, and it is possible to create a faster implementation. Am I right? Do you know, how to get those equations, where gcd is bigger than 6?

That's a great find. How does working with secp160k1 help secp256k1? Is there a way to map one to the other?

Below are the endomorphism values for P and N; I am trying to figure out how to get the equations.
p=0xfffffffffffffffffffffffffffffffeffffac73
[1, 116413238536967823204912062004448726737640720821, 1192671444047713143517039375510234845319976240753, 320568492332623811159581411922637138849485810267, 170033768725603827466154123598115574507330393474, 888563150828732192317477979643480826024658399499, 459808123412383666504375194171595673260619233000, 506013106973151716048837162345055484894245883380, 756739066376840291689464290814729327749587999038, 914082931336101346080276401800062193637040619652, 888563150828732192317477979643480826024658399498, 343394884875415843299463132167146946522978512179, 774843300256341490735482619551103659225907196918, 436170574044216480529882878892092188900102188771, 744049162610497518614122278201946619129710226178, 1461501637330902918203684832716283019651637554290, 1345088398793935094998772770711834292913996833470, 268830193283189774686645457206048174331661313538, 1140933144998279107044103420793645880802151744024, 1291467868605299090737530709118167445144307160817, 572938486502170725886206853072802193626979154792, 1001693513918519251699309638544687346391018321291, 955488530357751202154847670371227534757391670911, 704762570954062626514220541901553691902049555253, 547418705994801572123408430916220826014596934639, 572938486502170725886206853072802193626979154793, 1118106752455487074904221700549136073128659042112, 686658337074561427468202213165179360425730357373, 1025331063286686437673801953824190830751535365520, 717452474720405399589562554514336400521927328113]

0x0100000000000000000001b8fa16dfab9aca16b6b3
[1, 1408470634914903571732066888580417336645162873119, 708713767398721337809629107989760271137717787930, 1151796019543683584915212041505571206301361534252, 41278637720562416563498774273562198366106105008, 69796346552658733766475001267285041190029755381, 459366475837133574597979692431231491490457423387, 719990520318696333937754171078776164365241746857, 595911485914207747779051672558094670244251938235, 780348846544327904014579629185545903813779011634, 69796346552658733766475001267285041190029755380, 512397478253132921069599719021683880242453713839, 11276752919974996128125063089015893227523958927, 905617103701427081067526546223393189340049567554, 739070208823765487451080854911983705447672906626, 1461501637330902918203686915170869725397159163570, 53031002415999346471620026590452388751996290452, 752787869932181580394057807181109454259441375641, 309705617787219333288474873665298519095797629319, 1420222999610340501640188140897307527031053058563, 1391705290778244184437211913903584684207129408190, 1002135161493769343605707222739638233906701740184, 741511117012206584265932744092093561031917416714, 865590151416695170424635242612775055152907225336, 681152790786575014189107285985323821583380151937, 1391705290778244184437211913903584684207129408191, 949104159077769997134087196149185845154705449732, 1450224884410927922075561852081853832169635204644, 555884533629475837136160368947476536057109596017, 722431428507137430752606060258886019949486256945]