I think I’ve approached all of this the wrong way.
I’m offering a 0.1 BTC bounty for the formal proof of any traversal method that provides a statistical edge over a linear scan for puzzle 69. By statistical edge I mean that this new traversal method running on a statistically significant number of executions requires significantly fewer checks (let’s put the threshold at 5%) to find the key.
Conditions :
- Has to be written using math semantics. Not “where does John lives” metaphors.
- Has to be empirically validated using a python / nodeJS script.
- First one posting it to this thread will be recipient of the bounty.
I think If we assume that the key is uniformly distributed within this range, then every key within the range has an equal probability of being the correct private key. Since the key has a uniform distribution, uniform distribution provides no bias in how the key is distributed, all traversal methods will, on average, require the same number of checks. This means that no method will significantly reduce the number of checks required to find the key.
The key is uniformly distributed, meaning every number within the range has an equal probability of being the correct key. In a linear search, we check keys one by one, starting from the beginning of the range and moving towards the end. The expected number of trials in a linear search for a uniformly distributed key is the average of the number of trials required to find the key. Since the key can be anywhere in the range, the expected number of trials is given by N/2, where N is the number of possible keys in the range.
Because any traversal method still needs to explore a random and uniformly distributed key space, and the expected number of trials is N/2 for any such strategy.
Well using middle search or jumping around may increase your luck but the probability of finding the key is still the same.