Hi All,
I've been reading this and other related topics for a few weeks and I'm trying to understand the complexity of the different algorithms and approaches.
For Pollard's Kangaroo algorithm, someone gave an estimate of 2^66.05 operations needed for solving #130 (
https://bitcointalk.org/index.php?topic=5244940.2740 not sure how they reached this conclusion, but from reading about the algorithm it has a similar complexity to BSGS). This equals
~7.6x1019 operations needed.
For BSGS, from reading about it, is has a complexity of O(n
1/2). Taking the square root of the range (2
130 - 2
129 - 1) equals ~
2.6x1019 operations needed.
Is this correct? Is BSGS more efficient, or is it just a wrong way of calculating the efficiency?
I think I'm missing something in estimating the total "operations needed" for these algorithms. Is there a better/correct way of doing this?
Considering HW limitations, I am still not familiar with how different Kangaroo implementations work, I see that the JeanLucPons' based on VanitySearch requires GPU power (I assume more cores means better, but not sure what is the requirement for VRAM, CPU, RAM).
For BSGS, seems like keyhunt is the best, and works better with more RAM and more CPU cores.
Am I missing anything? Are there any other/better tools available for searching the ranges with known public keys?
In fact, for block 66, a private key must be generated with the 81129638414569788207641586040831 number, and this process is slow with a CPU, but using a graphics processor speeds it up.
I have written a simple Python program below that randomly generates private key within the range of block 66, and compares its public key at every moment with the public key of block number 66. If found, it displays a message and saves it in the data.txt file in the root of the program.
import bitcoin
import ecdsa
import secrets
from timeit import default_timer as timer
start = timer()
t=""
for _ in range(47):# generate 47 character ( 0 )
t = t + "0"
def generate_private_key():
p=str(secrets.choice(range(2, 4)))# generate random( 2 or 3) for fist number
return (t+p+secrets.token_hex(

)#return { 47 character ( 0 ) + random (2 or 3 ) + generate random (16 character in hexadecimal) }
def private_key_to_public_key(private_key):
sk = ecdsa.SigningKey.from_string(bytes.fromhex(private_key), curve=ecdsa.SECP256k1)
vk = sk.get_verifying_key()
compressed_public_key = vk.to_string("compressed").hex()
return compressed_public_key
def main():
target_address = "13zb1hQbWVsc2S7ZTZnP2G4undNNpdh5so" # this is Target wallet address , just p2pkh compressed
while True:#
#for _ in range(100000):#while True:
private_key = generate_private_key()#secrets.randbelow(32)) # Generate a random private key
public_key = private_key_to_public_key(private_key) # Convert private key to compressed public key
# Generate Bitcoin address from public key
bitcoin_address = bitcoin.pubtoaddr(public_key)
print(private_key,' ',bitcoin_address)
if (bitcoin_address == target_address):
f = open("data.txt", "a")
f.write('\nprivate key int: '
+ private_key
+'\nBitcoin address: '
+ bitcoin_address+'\n_________\n')
f.close()
print(f"Found matching Bitcoin address for private key: {private_key}")
break
print("--- %s seconds ---" ,timer()-start)
if __name__ == "__main__":
main()