Legendre Symbol Breakthrough in ECC

Your 256-step tree for secp256k1 is gonna have so many branches and magic numbers. Good luck with that.

In the toy example, the tree had only about 10-15 nodes, not 67 leaves. The depth was logarithmic, and the branching was binary. The magic numbers are based on the curve properties, not random.

I counted 21 branches, not the 6-7 you claimed. Where’s this logarithmic depth you talk about?

It’s logarithmic when you use a 256-bit lookup. ECDLP can be solved in 256 logical steps. But secp256k1 is generic, and the Legendre symbol won't leak scalar data.

Thanks for the critique! You're right, there are more branches in the toy example than I’d like. But in a group of 67, a decision tree with depth ~5-6 is typically enough.