search

herumi / mcl

a portable and fast pairing-based cryptography library
BSD 3-Clause "New" or "Revised" License
452 stars 152 forks source link

how to accelerate g*f by precompute? #42

Closed huyuguang closed 5 years ago

huyuguang commented 5 years ago

The speed of g*f(BN curve) in mclis very fast, much faster than normal wNAF algorithm.

In my scenario, the g is hardcoded, so I think I can accelerate the speed of g*fby precompute and cache some data, for example, 2g, 4g, 8g,16g ... , then I can convert theg*fto test_bit&add. But to my surprise, I found the test_bit&add version only slightly faster (20%~30%) than mclversion.

So, what should I do? How can I accelerate the speed for 100% or more by precompute/cache? Could you please give some suggestions (or some URLs)?

herumi commented 5 years ago

Use mcl/window_method.hpp as the followings:

#include <mcl/window_method.hpp>
mcl::fp::WindowMethod<G1> wm;
wm.init(P, Fr::getBitSize(), 4 /* winSize */); // precompute a table for a fixed P with 4-bit window size
Fr x;
wm.mul(P1, x); // instead of G1::mul(P1, P, x);

If increasing winSize then it requires more memory and computes more faster.

huyuguang commented 5 years ago

Very thanks, I will try it.

huyuguang commented 5 years ago

It works fine. I use init(g, bit_size, 8) and got 500% speed. Thanks again.