I know Modular Exponentiation ($r = b^e \bmod m$) is important for RSA, and I can find some algorithm that if e is expressed in binary form (for exp: )--in such way for a n-bit long e, one can expect ~1.5n rounds multiply modular operation.
I am working on making a public key recovery methodology for ECC like secp256k1/r1. There is a very efficient implementation in the secp256k1 lib, but that was coded in ASM code--hard to understand. But at least I know the 1st step--you need to recover the $ry$ from the $rx$ (i.e. r of the signature). It is very easy to get $ry^2$ from $rx$, but the next I will need to do square root modular--which can be converted to the exponentiation modular on the field, that is $e= (p+1)/4.$
OK, so now questions are:
- Is there a better algorithm other than the usual Modular Exponentiation to calculate the ($r = b^e \bmod m$)?
- Or alternatively, is there any short-cut algorithm specifically for secp256k1 that I don’t need run Modular Exponentiation at all and still be able to recover the $ry$ from $rx$?