Quote from: kTimesG on Today at 09:21:58 AM

Quote from: farou9 on May 13, 2025, 08:08:13 PM

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 = N

x 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.png

So if we store sqrt2**30 , a space of 2**31 will need 2(sqrt2**30).
But if where are we storing them , ram or disk ?