From the Readme of secp256k1 we can see the following:
Use a precomputed table of multiples of powers of 16 multiplied with the generator, so general multiplication becomes a series of additions.
I was wondering why in particular the table used precomputed table of multiples of
16? I would have expected a higher number or a more dynamic approach which includes dynamic caching.
Let me elaborate a little bit:
With multiples of
16 we always need
4 bit computed in the table. meaning we have
256 / 4 = 64 buckets with
16 entries for each bucket.
n be the number of bits in a window for which we compute powers of
g this would result in the general formula for the amount of precomputed values in our table for
n > 1:
256 / n * 2 ^ n
n = 4 we have
64 * 16 = 1024 entries.
n = 8 we would have 32 * 256 = 8192 entries. However when actually computing a multiplication we would only need 32 additions instead of 64. creating a speedup of a factor of 2 for 8 times us much memory usage of our lookup table.
n = 16 we would have
16 * 65536 = 1048576 or
1M * sizeof(point) of main memory to have only 16 point additions when computing a multiplication.
Obviously such a big lookup table requires some time when setting up the library. Even if the table was already precomputed and in binary shipped with the library.
Anyway I was wondering for the particular choice of
4 bits. I would assume that
8 bits was better and probably even taking
16 bit windows seems fairly reasonable.