Ok fast lookup is a lost cause then ,
So how does bsgs work ,doesn't it need to store sqrt of the space to make sqrt of space speed ,right?
It works just as you said.
If you have to find a key in a space of size N, BSGS allows to express the problem as
x * y = Nx is the precomputed table size, y is the number of subtractions and lookups.
x + y is minimal when x = sqrt(N)
When x is any other value (a table that is smaller or larger than sqrt(N)) then x + y is no longer minimal. You end up with either using less memory (and more subs and lookups), or more memory (and less subs and lookups).
Here's a graph for N = 100.
https://talkimg.com/images/2025/05/14/UU961c.pngSo if we store sqrt2**30 , a space of 2**31 will need 2(sqrt2**30).
