-snip-
I use a precomputed table of multiples of G.
I did not use any precomputed multiples of G.
Do you use just 256 precomupted points for powers of two (2^0, 2^1, 2^2, 2^3, 2^4, ... 2^255) and later represent every private key number in binary and make
scalar additions of precomputed points? If no, how much is your precomupted table and what kind of points include?
If you precompute only the powers of two, you avoid only the doublings. It is like you split your binary key in 256 pieces, each piece in this case is a particular point and then you perform 255 additions between these points.
But if you split 256 in 128/64/32/16/8 parts and you precompute every key in these "parts" (in these cases each part has more than 1 point) you can lower the number of additions.
I use 32 groups of 255 points = 8160 precomputed points.
I represent every private key in binary, I split that number in 32 pieces (each piece has 256/32=8 bit -> 255 elements) and I compute only 32-1 = 31 group additions (instead of 256) for each key. No doubling.
Just for example, if you have a 32 bit key:
key = 10101010101000001111111101000010
split in 4 pieces of 32/4=8 bits:
(10101010)*2^24 + (10100000)*2^16 + (11111111)*2^8 + (01000010)
Then I need to do only 3 additions, if I have precomputed this table (a line for each piece):
00000001 00000010 00000011 … 11111111
2^0 2*2^0 3*2^0 … 255*2^0 --> one of these is (01000010)
2^8 2*2^8 3*2^8 … 255*2^8 --> one of these is (11111111)*2^8
2^(2*8) 2*2^(2*8) 3*2^(2*8) . 255*2^(2*8) --> one of these is (10100000)*2^16
2^(3*8) 2*2^(3*8) 3*2^(3*8) . 255*2^(3*8) --> one of these is (10101010)*2^24
Each line has 255 elements because you don't need the (00000000) element.
For a 256 bit key, this is the precomputed table (32 lines * 255 elements = 8160):
2^0 , 2*2^0, 3*2^0, … , 255*2^0
2^8, 2*2^8, 3*2^8, …, 255*2^8
2^(2*8), 2*2^(2*8), 3*2^(2*8) , .., 255*2^(2*8)
2^(3*8), 2*2^(3*8), 3*2^(3*8) , .., 255*2^(3*8)
2^(4*8), 2*2^(4*8), 3*2^(4*8) , .., 255*2^(4*8)
2^(5*8), 2*2^(5*8), 3*2^(5*8) , .., 255*2^(5*8)
…
2^(31*8), 2*2^(31*8), 3*2^(31*8) , .., 255*2^(31*8)
I split a 256 bit key in 32 pieces of 8 bit and I compute 31 additions.
