For the #57 key instead:
#define GSTEP (1<<28)
typedef struct hashtable_entry {
uint64_t x;
uint32_t exponent;
} hashtable_entry;
#define HASH_SIZE (2*GSTEP)
hashtable_entry table[HASH_SIZE];
I use 32 bit for the exponent (32 > 28) and I store only the first 64 bit of the x coordinate (there is a low chance to have a partial collision in a list of 2^28 element, i.e. two different x with the same first 64 bit) -->
(64 + 32 bit) To avoid any collisions you should use always 256 bit for the x coordinate. And the size of the hash table should be at least two times the size of the list you want to store.
With the above in mind how does the other guy's program work for the first 51 with only uint32_t x; instead of 64?? Mostly curious.
Because I oversimplified my explanation to avoid technical details.
GSTEP 2^25
HASHSIZE 2^26
hash table is for one list of 2^25 public keys (baby steps)
the second list of 2^25 public keys (giant steps) is computed and compaired with the first one "on fly" (no memory)
Take the x coordinate of a public key: xst (256 bit)
and split it:
xst.n[0] 64 bit
xst.n[1] 64 bit
xst.n[2] 64 bit
xst.n[3] 64 bit
the index of the table (entry) is 26 bit of xst.n[0]
if that entry is already occupied, use xst.n[1] to modify the index (this way you avoid collisions between elements in the hash table)
instead of the entire x, x = 32 bit of xst.n[2]
exponent = i (which step it is, to retrieve the private key to that public key)
for (size_t i = 1; i < GSTEP; i++) {
secp256k1_fe x,zinv;
secp256k1_fe_storage xst;
secp256k1_fe_inv_var(&zinv, &pt.z);
secp256k1_fe_sqr(&zinv, &zinv);
secp256k1_fe_mul(&x, &pt.x, &zinv);
secp256k1_fe_to_storage(&xst, &x);
uint32_t entry = xst.n[0] & (HASH_SIZE-1);
while (table[entry].exponent != 0) {
entry = (entry + (xst.n[1] | 1)) & (HASH_SIZE - 1);
}
table[entry].exponent = i;
table[entry].x = xst.n[2];
secp256k1_gej_add_ge_var(&pt, &pt, &secp256k1_ge_const_g, NULL);
}
This program uses at least 26 + 32 bit = 58 bit of each public key that is in the hash table (but 26 bit are the position in the memory, so it stores effectively only 32 bit of the key in the table + 32 bit for the exponent, the private key) .
Then it generates the second list (giant steps). A wrong collision between an element of this list and a element in the table can occur only if 2 public keys share exactly 58 bit (let's say for semplicity the first 58 bit, but they are not adjacent). To find a 51 bit key then 32 bit for the x coordinate is enough.
If you need to retrieve a 60 bit private key or more, you should use more space.
