Add wnaf#14
Conversation
|
hey @burdges can you take a quick second look on this? |
|
Thanks! |
|
Oops, this fell off my radar, sorry! I have not checked the conversion of all the test vectors or There is however one Rust issue though, As an aside, even if you wrote to the result, then for a short array like this you should return a |
Heya, thanks for the feedback on this, rust is a language I'm somewhat unfamiliar with. Given the branch is merged, is it too late to push a change to fix this? |
Yes. If you have the time it would be fantastic if you opened a second PR. Otherwise I can do it. :) |
Hello!
This is a small modification to the
miller_loopandprecomputemethods. Both methods iterate over the bits of parameterate_loop_count. If the bit is set totrue, a line function for theG2group element is precomputed inprecompute. Then later inmiller_loop, the line function is scaled by the pairedG1group element, with the result being multiplied into the accumulatedFp12elementf.We can take advantage of the fact that negations on an elliptic curve are essentially free, and use a Non-Adjacent-Form representation of
ate_loop_count. Instead of a binary representation, each 'bit' can be either0,1or-1. The hamming weight of the NAF is ~50% less than the binary form.The
precomputealgorithm is modified to iterate over NAF entries ofate_loop_count_naf. If an entry is-1, a line function relative to-G2is computed. This reduces the number of precomputed G2 entries, from 102 to 87.This provides a corresponding ~15% reduction in the run-time of the miller loop, as each precompute entry requires a line doubling computation in
Fp2and a scalar multiplication inFp12, both of which are expensive.