Pollard's kangaroo ECDLP solver

[ripemdhash]

It is the same person or group which solve 120 bit.

So it is not kangaroo and not bsgs.

They must know something which we do not know.
The questions is -> what kind of math they use.   And second questions : I'm afraid BTC is not secure any more.

[1715178177]

1715178177

[sssergy2705]

In the 30+ minutes that I wasted hammering (and subsequently trashing) a reply to this, I just updated the pkarith script to spit out the correct end points... took me just two minutes and 2 lines of code change. https://gist.github.com/ZenulAbidin/e8687d9e16189c99d192e97d37e71dbe

See how more effectively and faster I can implement stuff when I have all the info I need, clearly (emphasis on that), beforehand?

I can only work with information I have at hand (without guessing random stuff). Nowhere was it said that you had to divide max value by 32 and add that to start value to get the end value... take a look back at them yourself.

Otherwise you get stuff like a broken Kangaroo-256 with a borked hashtable lookup function.

There wouldn't have even been a flamewar if I had that info. Instead I got "0.01325 to 0.0625" which I understood to mean that the zones themselves are the start and end points. With this info, making an assumption about division at that stage would've been a guess.

And none of this was resolved until Counselor explained this important point a few posts up.

Hello.
  I read the topic from the end and saw this script and discussion.
I checked how it works, but no matches are found when searching for public keys with the ranges that go in the same block in the keyhunt.
Do the public keys in the output of this script match the ranges?

[brainless]

 Who can solve
 p = 115792089237316195423570985008687907852837564279074904382605163141518161494335
a = 1099511627776
b = 115792089237316195423570985008687907852837564279074904382605163141005436653346
c = (a-b) %p
result = 1612236468765

in pubkey

p =115792089237316195423570985008687907852837564279074904382605163141518161494335
a = 02feea6cae46d55b530ac2839f143bd7ec5cf8b266a41d6af52d5e688d9094696d
b = 02746bd76e07a0dbbcc610245439ee1db94f73b70df43bc543d4046ebe119ad6b3
c = (a-b) %p
result = 02b21dd66bfde832c2dae35688c0e15b91b274ec018e2c14e23f1ca7cb32fcca73

substract formula
p = int(2**256 - 2**32 - 977)
x1 =  # fill pubkey1-x
y1=  # fill pubkey1-y
x2=  # fill pubkey2-x
y2=  # fill pubkey2-y



dx = (x1 - x2) % p
dy = (y1 - (-y2)) % p
c = dy * gmpy2.invert(dx, p) % p
Rx = (c*c - x2 - x1) % p
Ry = (c*(x2 - Rx) - y2) % p
print (Rx , Ry)
print (hex(Rx) , hex(Ry))


if you have alternate formula for adjust with mod p, apply and check for get acurate result in pubkey

[unpluggedcoin]

Who can solve
 p = 115792089237316195423570985008687907852837564279074904382605163141518161494335
a = 1099511627776
b = 115792089237316195423570985008687907852837564279074904382605163141005436653346
c = (a-b) %p
result = 1612236468765

in pubkey

p =115792089237316195423570985008687907852837564279074904382605163141518161494335
a = 02feea6cae46d55b530ac2839f143bd7ec5cf8b266a41d6af52d5e688d9094696d
b = 02746bd76e07a0dbbcc610245439ee1db94f73b70df43bc543d4046ebe119ad6b3
c = (a-b) %p
result = 02b21dd66bfde832c2dae35688c0e15b91b274ec018e2c14e23f1ca7cb32fcca73

substract formula
p = int(2**256 - 2**32 - 977)
x1 =  # fill pubkey1-x
y1=  # fill pubkey1-y
x2=  # fill pubkey2-x
y2=  # fill pubkey2-y



dx = (x1 - x2) % p
dy = (y1 - (-y2)) % p
c = dy * gmpy2.invert(dx, p) % p
Rx = (c*c - x2 - x1) % p
Ry = (c*(x2 - Rx) - y2) % p
print (Rx , Ry)
print (hex(Rx) , hex(Ry))


if you have alternate formula for adjust with mod p, apply and check for get acurate result in pubkey

Would you plz be specific, like solve for what? What is expected result conditions? How result should look like, can explain how the successful result should be some how

[brainless]

Who can solve
 p = 115792089237316195423570985008687907852837564279074904382605163141518161494335
a = 1099511627776
b = 115792089237316195423570985008687907852837564279074904382605163141005436653346
c = (a-b) %p
result = 1612236468765

in pubkey

p =115792089237316195423570985008687907852837564279074904382605163141518161494335
a = 02feea6cae46d55b530ac2839f143bd7ec5cf8b266a41d6af52d5e688d9094696d
b = 02746bd76e07a0dbbcc610245439ee1db94f73b70df43bc543d4046ebe119ad6b3
c = (a-b) %p
result = 02b21dd66bfde832c2dae35688c0e15b91b274ec018e2c14e23f1ca7cb32fcca73

substract formula
p = int(2**256 - 2**32 - 977)
x1 =  # fill pubkey1-x
y1=  # fill pubkey1-y
x2=  # fill pubkey2-x
y2=  # fill pubkey2-y



dx = (x1 - x2) % p
dy = (y1 - (-y2)) % p
c = dy * gmpy2.invert(dx, p) % p
Rx = (c*c - x2 - x1) % p
Ry = (c*(x2 - Rx) - y2) % p
print (Rx , Ry)
print (hex(Rx) , hex(Ry))


if you have alternate formula for adjust with mod p, apply and check for get acurate result in pubkey

Would you plz be specific, like solve for what? What is expected result conditions? How result should look like, can explain how the successful result should be some how

Above Dec calculate with mod P 2 digit less, same all Dec figures taken to create pubkey
Substraction formula original ecc with original mod P
Adjust mod P to 2 digit less for get correct pubkey as mention in pubkey result

[testbug]

Hi there,

i am playing around with kangaroo and i am not sure if it's working correctly. Why is it saying "Kangaroos:  0 2^-inf"?
Also, whats the meaning of HT Max/Min/...? Would be great if someone could explain it to me. I am running kangaroo in client/server mode with server command: ./kangaroo -w save.work -wsplit -wi 600 -o result.txt -d 24 -s in.txt

Here is an example of one of the workfiles, as it's saved every 10minutes there are severall workfiles now.

Kangaroo v2.2
Loading: save.work_27Jul23_101320
Version   : 0
DP bits   : 24
Start     : 200000000000000000000000000000000
Stop      : 3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
Key       : 03633CBE3EC02B9401C5EFFA144C5B4D22F87940259634858FC7E59B1C09937852
Count     : 0 2^-inf
Time      : 00s
DP Size   : 2.3/5.7MB
DP Count  : 11186 2^13.449
HT Max    : 3 [@ 00B207]
HT Min    : 0 [@ 000000]
HT Avg    : 0.04
HT SDev   : 0.21
Kangaroos : 0 2^-inf

Do you merge them for example once a day and only keep the merged file or do we need the save.workTIMESTAMP too?

Thanks a lot

[nomachine]

two script python
http://bitchain.pl/100btc/pollard_kangaroo.txt
and
https://github.com/Telariust/pollard-kangaroo/blob/master/pollard-kangaroo-multi.py

That link no longer exists. I barely managed to find the original pollard_kangaroo.txt on some Russian site. But it is deprecated for Python 2.x. I updated to 3.x and it's still slow, but if you want to play, here you go.

Code:

import time
import random
import gmpy2
from functools import lru_cache

modulo = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
order = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

class Point:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

PG = Point(Gx, Gy)
Z = Point(0, 0)  # zero-point, infinite in real x,y-plane

def mul2(P, p=modulo):
    c = (3 * P.x * P.x * pow(2 * P.y, -1, p)) % p
    R = Point()
    R.x = (c * c - 2 * P.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

def add(P, Q, p=modulo):
    dx = Q.x - P.x
    dy = Q.y - P.y
    #c = (dy * pow(dx, -1, p)) % p
    c = dy * gmpy2.invert(dx, p) % p
    R = Point()
    R.x = (c * c - P.x - Q.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

@lru_cache(maxsize=None)
def X2Y(X, p=modulo):
    if p % 4 != 3:
        print('prime must be 3 modulo 4')
        return 0
    X = (X ** 3 + 7) % p
    pw = (p + 1) // 4
    Y = 1
    tmp = X
    for w in range(256):
        if (pw >> w) & 1 == 1:
            Y = (Y * tmp) % p
        tmp = pow(tmp, 2, p)
    return Y

def compute_P_table():
    P = [PG]
    for k in range(255):
        P.append(mul2(P[k]))
    return P

P = compute_P_table()

print('P-table prepared')

def comparator(A, Ak, B, Bk):
    result = set(A).intersection(set(B))
    if result:
        sol_kt = A.index(next(iter(result)))
        sol_kw = B.index(next(iter(result)))
        print('total time: %.2f sec' % (time.time() - starttime))
        d = Ak[sol_kt] - Bk[sol_kw]
        print('SOLVED:', d)
        with open("results.txt", 'a') as file:
            file.write(('%d' % (Ak[sol_kt] - Bk[sol_kw])) + "\n")
            file.write("---------------\n")
        return True
    else:
        return False

def check(P, Pindex, DP_rarity, file2save, A, Ak, B, Bk):
    if P.x % DP_rarity == 0:
        A.append(P.x)
        Ak.append(Pindex)
        with open(file2save, 'a') as file:
            file.write(('%064x %d' % (P.x, Pindex)) + "\n")
        return comparator(A, Ak, B, Bk)
    else:
        return False

def mulk(k, P=PG, p=modulo):
    if k == 0:
        return Z
    elif k == 1:
        return P
    elif k % 2 == 0:
        return mulk(k // 2, mul2(P, p), p)
    else:
        return add(P, mulk((k - 1) // 2, mul2(P, p), p), p)

def search(Nt, Nw, problem, kangoo_power, starttime):
    DP_rarity = 1 << ((problem - 2 * kangoo_power) // 2 - 2)
    hop_modulo = ((problem - 1) // 2) + kangoo_power
    T, t, dt = [], [], []
    W, w, dw = [], [], []
    for k in range(Nt):
        t.append((3 << (problem - 2)) + random.randint(1, (1 << (problem - 1))))
        T.append(mulk(t[k]))
        dt.append(0)
    for k in range(Nw):
        w.append(random.randint(1, (1 << (problem - 1))))
        W.append(add(W0, mulk(w[k])))
        dw.append(0)
    print('tame and wild herds are prepared')
    oldtime = time.time()
    Hops, Hops_old = 0, 0
    t0 = time.time()
    oldtime = time.time()
    starttime = oldtime
    while True:
        for k in range(Nt):
            Hops += 1
            pw = T[k].x % hop_modulo
            dt[k] = 1 << pw
            solved = check(T[k], t[k], DP_rarity, "tame.txt", T, t, W, w)
            if solved:
                return 'sol. time: %.2f sec' % (time.time() - starttime)
            t[k] += dt[k]
            T[k] = add(P[pw], T[k])
        for k in range(Nw):
            Hops += 1
            pw = W[k].x % hop_modulo
            dw[k] = 1 << pw
            solved = check(W[k], w[k], DP_rarity, "wild.txt", W, w, T, t)
            if solved:
                return 'sol. time: %.2f sec' % (time.time() - starttime)
            w[k] += dw[k]
            W[k] = add(P[pw], W[k])
        t1 = time.time()
        if (t1 - t0) > 5:
            print('%.3f h/s' % ((Hops - Hops_old) / (t1 - t0)))
            t0 = t1
            Hops_old = Hops

start = 2147483647
end = 4294967295
search_range = end - start + 1
problem = search_range.bit_length()

compreessed_public_key = "0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69" #Puzzle 32
kangoo_power = 3
Nt = Nw = 2 ** kangoo_power
X = int(compreessed_public_key, 16)
Y = X2Y(X % (2 ** 256))
if Y % 2 != (X >> 256) % 2:
    Y = modulo - Y
X = X % (2 ** 256)
W0 = Point(X, Y)
starttime = oldtime = time.time()

Hops = 0
random.seed()

hops_list = []
N_tests = 3

for k in range(N_tests):
    with open("tame.txt", 'w') as tame_file, open("wild.txt", 'w') as wild_file:
        tame_file.write('')
        wild_file.write('')
    search_result = search(Nt, Nw, problem, kangoo_power, starttime)
    print(search_result)
    M, D = 0, 0
    if len(hops_list) > 0:
        M = sum(hops_list) * 1.0 / len(hops_list)
        D = sum((xi - M) ** 2 for xi in hops_list) * 1.0 / len(hops_list)
    print(M, '+/-', (D / (len(hops_list) - 1)) ** 0.5)
    print('Average time to solve: %.2f sec' % ((time.time() - starttime) / N_tests))

It is about 142827.704 h/s here....

[dextronomous]

hi nomachine, doing a nice 250 300 but it is single core version is there a multicore version out
or can we edit this to do that , thanks mate for sharing.

[sssergy2705]

hi nomachine, doing a nice 250 300 but it is single core version is there a multicore version out
or can we edit this to do that , thanks mate for sharing.

https://github.com/Telariust/pollard-kangaroo/blob/master/pollard-kangaroo-multi.py

There is a link in his post.

[dextronomous]

i guess did not even clicked it or looked at it, cause i already have used that one,
wasn't what i was looking for actually i guess, the gpu already also working so,
the code of 57fe/Pollard-Rho-Kangaroo should be ai 'ed quickly..

[nomachine]

is there a multicore version out
or can we edit this to do that , thanks mate for sharing.

Sure, here's the full script with multiprocessing added:

Code:

import time
import random
import gmpy2
from functools import lru_cache
import multiprocessing

modulo = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
order = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

class Point:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

PG = Point(Gx, Gy)
Z = Point(0, 0)  # zero-point, infinite in real x,y-plane

def mul2(P, p=modulo):
    c = (3 * P.x * P.x * pow(2 * P.y, -1, p)) % p
    R = Point()
    R.x = (c * c - 2 * P.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

def add(P, Q, p=modulo):
    dx = Q.x - P.x
    dy = Q.y - P.y
    c = dy * gmpy2.invert(dx, p) % p
    R = Point()
    R.x = (c * c - P.x - Q.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

@lru_cache(maxsize=None)
def X2Y(X, p=modulo):
    if p % 4 != 3:
        print('prime must be 3 modulo 4')
        return 0
    X = (X ** 3 + 7) % p
    pw = (p + 1) // 4
    Y = 1
    tmp = X
    for w in range(256):
        if (pw >> w) & 1 == 1:
            Y = (Y * tmp) % p
        tmp = pow(tmp, 2, p)
    return Y

def compute_P_table():
    P = [PG]
    for k in range(255):
        P.append(mul2(P[k]))
    return P

P = compute_P_table()

print('P-table prepared')

def comparator(A, Ak, B, Bk):
    result = set(A).intersection(set(B))
    if result:
        sol_kt = A.index(next(iter(result)))
        sol_kw = B.index(next(iter(result)))
        print('total time: %.2f sec' % (time.time() - starttime))
        d = Ak[sol_kt] - Bk[sol_kw]
        print('SOLVED:', d)
        with open("results.txt", 'a') as file:
            file.write(('%d' % (Ak[sol_kt] - Bk[sol_kw])) + "\n")
            file.write("---------------\n")
        return True
    else:
        return False

def check(P, Pindex, DP_rarity, file2save, A, Ak, B, Bk):
    if P.x % DP_rarity == 0:
        A.append(P.x)
        Ak.append(Pindex)
        with open(file2save, 'a') as file:
            file.write(('%064x %d' % (P.x, Pindex)) + "\n")
        return comparator(A, Ak, B, Bk)
    else:
        return False

def mulk(k, P=PG, p=modulo):
    if k == 0:
        return Z
    elif k == 1:
        return P
    elif k % 2 == 0:
        return mulk(k // 2, mul2(P, p), p)
    else:
        return add(P, mulk((k - 1) // 2, mul2(P, p), p))

def search(process_id, Nt, Nw, problem, kangoo_power, starttime):
    DP_rarity = 1 << ((problem - 2 * kangoo_power) // 2 - 2)
    hop_modulo = ((problem - 1) // 2) + kangoo_power
    T, t, dt = [], [], []
    W, w, dw = [], [], []
    for k in range(Nt):
        t.append((3 << (problem - 2)) + random.randint(1, (1 << (problem - 1))))
        T.append(mulk(t[k]))
        dt.append(0)
    for k in range(Nw):
        w.append(random.randint(1, (1 << (problem - 1))))
        W.append(add(W0, mulk(w[k])))
        dw.append(0)
    print('tame and wild herds are prepared')
    oldtime = time.time()
    Hops, Hops_old = 0, 0
    t0 = time.time()
    oldtime = time.time()
    starttime = oldtime
    while True:
        for k in range(Nt):
            Hops += 1
            pw = T[k].x % hop_modulo
            dt[k] = 1 << pw
            solved = check(T[k], t[k], DP_rarity, "tame.txt", T, t, W, w)
            if solved:
                return 'sol. time: %.2f sec' % (time.time() - starttime)
            t[k] += dt[k]
            T[k] = add(P[pw], T[k])
        for k in range(Nw):
            Hops += 1
            pw = W[k].x % hop_modulo
            dw[k] = 1 << pw
            solved = check(W[k], w[k], DP_rarity, "wild.txt", W, w, T, t)
            if solved:
                return 'sol. time: %.2f sec' % (time.time() - starttime)
            w[k] += dw[k]
            W[k] = add(P[pw], W[k])
        t1 = time.time()
        if (t1 - t0) > 5:
            print('%.3f h/s' % ((Hops - Hops_old) / (t1 - t0)))
            t0 = t1
            Hops_old = Hops

start = 2147483647
end = 4294967295
search_range = end - start + 1
problem = search_range.bit_length()

compreessed_public_key = "0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69" #Puzzle 32
kangoo_power = 3
Nt = Nw = 2 ** kangoo_power

X = int(compreessed_public_key, 16)
Y = X2Y(X % (2 ** 256))
if Y % 2 != (X >> 256) % 2:
    Y = modulo - Y
X = X % (2 ** 256)
W0 = Point(X, Y)
starttime = oldtime = time.time()

Hops = 0
random.seed()

hops_list = []
N_tests = 3

def search_wrapper(process_id):
    return search(process_id, Nt, Nw, problem, kangoo_power, starttime)

if __name__ == "__main__":
    num_cpus = multiprocessing.cpu_count()
    N_tests = num_cpus  # Use the number of CPU cores as the number of tests

    with multiprocessing.Pool(processes=N_tests) as pool:
        results = pool.map(search_wrapper, range(N_tests))

    for result in results:
        print(result)
        M, D = 0, 0
        if len(hops_list) > 0:
            M = sum(hops_list) * 1.0 / len(hops_list)
            D = sum((xi - M) ** 2 for xi in hops_list) * 1.0 / len(hops_list)
        print(M, '+/-', (D / (len(hops_list) - 1)) ** 0.5)
        print('Average time to solve: %.2f sec' % ((time.time() - starttime) / N_tests))

In the __name__ == "__main__" block, the number of available CPU cores is determined using multiprocessing.cpu_count(), and N_tests is set to this number. This means that the script will create a separate process for each CPU core available for parallel processing.

[NotATether]

is there a multicore version out
or can we edit this to do that , thanks mate for sharing.

Sure, here's the full script with multiprocessing added:

Code:

import time
import random
import gmpy2
from functools import lru_cache
import multiprocessing

modulo = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
order = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

class Point:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

PG = Point(Gx, Gy)
Z = Point(0, 0)  # zero-point, infinite in real x,y-plane

def mul2(P, p=modulo):
    c = (3 * P.x * P.x * pow(2 * P.y, -1, p)) % p
    R = Point()
    R.x = (c * c - 2 * P.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

def add(P, Q, p=modulo):
    dx = Q.x - P.x
    dy = Q.y - P.y
    c = dy * gmpy2.invert(dx, p) % p
    R = Point()
    R.x = (c * c - P.x - Q.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

@lru_cache(maxsize=None)
def X2Y(X, p=modulo):
    if p % 4 != 3:
        print('prime must be 3 modulo 4')
        return 0
    X = (X ** 3 + 7) % p
    pw = (p + 1) // 4
    Y = 1
    tmp = X
    for w in range(256):
        if (pw >> w) & 1 == 1:
            Y = (Y * tmp) % p
        tmp = pow(tmp, 2, p)
    return Y

def compute_P_table():
    P = [PG]
    for k in range(255):
        P.append(mul2(P[k]))
    return P

P = compute_P_table()

print('P-table prepared')

def comparator(A, Ak, B, Bk):
    result = set(A).intersection(set(B))
    if result:
        sol_kt = A.index(next(iter(result)))
        sol_kw = B.index(next(iter(result)))
        print('total time: %.2f sec' % (time.time() - starttime))
        d = Ak[sol_kt] - Bk[sol_kw]
        print('SOLVED:', d)
        with open("results.txt", 'a') as file:
            file.write(('%d' % (Ak[sol_kt] - Bk[sol_kw])) + "\n")
            file.write("---------------\n")
        return True
    else:
        return False

def check(P, Pindex, DP_rarity, file2save, A, Ak, B, Bk):
    if P.x % DP_rarity == 0:
        A.append(P.x)
        Ak.append(Pindex)
        with open(file2save, 'a') as file:
            file.write(('%064x %d' % (P.x, Pindex)) + "\n")
        return comparator(A, Ak, B, Bk)
    else:
        return False

def mulk(k, P=PG, p=modulo):
    if k == 0:
        return Z
    elif k == 1:
        return P
    elif k % 2 == 0:
        return mulk(k // 2, mul2(P, p), p)
    else:
        return add(P, mulk((k - 1) // 2, mul2(P, p), p))

def search(process_id, Nt, Nw, problem, kangoo_power, starttime):
    DP_rarity = 1 << ((problem - 2 * kangoo_power) // 2 - 2)
    hop_modulo = ((problem - 1) // 2) + kangoo_power
    T, t, dt = [], [], []
    W, w, dw = [], [], []
    for k in range(Nt):
        t.append((3 << (problem - 2)) + random.randint(1, (1 << (problem - 1))))
        T.append(mulk(t[k]))
        dt.append(0)
    for k in range(Nw):
        w.append(random.randint(1, (1 << (problem - 1))))
        W.append(add(W0, mulk(w[k])))
        dw.append(0)
    print('tame and wild herds are prepared')
    oldtime = time.time()
    Hops, Hops_old = 0, 0
    t0 = time.time()
    oldtime = time.time()
    starttime = oldtime
    while True:
        for k in range(Nt):
            Hops += 1
            pw = T[k].x % hop_modulo
            dt[k] = 1 << pw
            solved = check(T[k], t[k], DP_rarity, "tame.txt", T, t, W, w)
            if solved:
                return 'sol. time: %.2f sec' % (time.time() - starttime)
            t[k] += dt[k]
            T[k] = add(P[pw], T[k])
        for k in range(Nw):
            Hops += 1
            pw = W[k].x % hop_modulo
            dw[k] = 1 << pw
            solved = check(W[k], w[k], DP_rarity, "wild.txt", W, w, T, t)
            if solved:
                return 'sol. time: %.2f sec' % (time.time() - starttime)
            w[k] += dw[k]
            W[k] = add(P[pw], W[k])
        t1 = time.time()
        if (t1 - t0) > 5:
            print('%.3f h/s' % ((Hops - Hops_old) / (t1 - t0)))
            t0 = t1
            Hops_old = Hops

start = 2147483647
end = 4294967295
search_range = end - start + 1
problem = search_range.bit_length()

compreessed_public_key = "0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69" #Puzzle 32
kangoo_power = 3
Nt = Nw = 2 ** kangoo_power

X = int(compreessed_public_key, 16)
Y = X2Y(X % (2 ** 256))
if Y % 2 != (X >> 256) % 2:
    Y = modulo - Y
X = X % (2 ** 256)
W0 = Point(X, Y)
starttime = oldtime = time.time()

Hops = 0
random.seed()

hops_list = []
N_tests = 3

def search_wrapper(process_id):
    return search(process_id, Nt, Nw, problem, kangoo_power, starttime)

if __name__ == "__main__":
    num_cpus = multiprocessing.cpu_count()
    N_tests = num_cpus  # Use the number of CPU cores as the number of tests

    with multiprocessing.Pool(processes=N_tests) as pool:
        results = pool.map(search_wrapper, range(N_tests))

    for result in results:
        print(result)
        M, D = 0, 0
        if len(hops_list) > 0:
            M = sum(hops_list) * 1.0 / len(hops_list)
            D = sum((xi - M) ** 2 for xi in hops_list) * 1.0 / len(hops_list)
        print(M, '+/-', (D / (len(hops_list) - 1)) ** 0.5)
        print('Average time to solve: %.2f sec' % ((time.time() - starttime) / N_tests))

In the __name__ == "__main__" block, the number of available CPU cores is determined using multiprocessing.cpu_count(), and N_tests is set to this number. This means that the script will create a separate process for each CPU core available for parallel processing.

If you're going to use multiprocessing, try not to print anything or do any I/O until the very end because the disk access bottleneck will slow the whole loop down (even on SSD - it can never possibly be as fast as a CPU's clock speed).

Actually you should even import tqdm and create a progress bar for that, and then customize the progress bar to show you the key being worked on, how many have already been done, etc. Much better than printing since there are not synchronized with a mutex (by default).

[nomachine]

is there a multicore version out
or can we edit this to do that , thanks mate for sharing.

Sure, here's the full script with multiprocessing added:

Code:

import time
import random
import gmpy2
from functools import lru_cache
import multiprocessing

modulo = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
order = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

class Point:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

PG = Point(Gx, Gy)
Z = Point(0, 0)  # zero-point, infinite in real x,y-plane

def mul2(P, p=modulo):
    c = (3 * P.x * P.x * pow(2 * P.y, -1, p)) % p
    R = Point()
    R.x = (c * c - 2 * P.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

def add(P, Q, p=modulo):
    dx = Q.x - P.x
    dy = Q.y - P.y
    c = dy * gmpy2.invert(dx, p) % p
    R = Point()
    R.x = (c * c - P.x - Q.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

@lru_cache(maxsize=None)
def X2Y(X, p=modulo):
    if p % 4 != 3:
        print('prime must be 3 modulo 4')
        return 0
    X = (X ** 3 + 7) % p
    pw = (p + 1) // 4
    Y = 1
    tmp = X
    for w in range(256):
        if (pw >> w) & 1 == 1:
            Y = (Y * tmp) % p
        tmp = pow(tmp, 2, p)
    return Y

def compute_P_table():
    P = [PG]
    for k in range(255):
        P.append(mul2(P[k]))
    return P

P = compute_P_table()

print('P-table prepared')

def comparator(A, Ak, B, Bk):
    result = set(A).intersection(set(B))
    if result:
        sol_kt = A.index(next(iter(result)))
        sol_kw = B.index(next(iter(result)))
        print('total time: %.2f sec' % (time.time() - starttime))
        d = Ak[sol_kt] - Bk[sol_kw]
        print('SOLVED:', d)
        with open("results.txt", 'a') as file:
            file.write(('%d' % (Ak[sol_kt] - Bk[sol_kw])) + "\n")
            file.write("---------------\n")
        return True
    else:
        return False

def check(P, Pindex, DP_rarity, file2save, A, Ak, B, Bk):
    if P.x % DP_rarity == 0:
        A.append(P.x)
        Ak.append(Pindex)
        with open(file2save, 'a') as file:
            file.write(('%064x %d' % (P.x, Pindex)) + "\n")
        return comparator(A, Ak, B, Bk)
    else:
        return False

def mulk(k, P=PG, p=modulo):
    if k == 0:
        return Z
    elif k == 1:
        return P
    elif k % 2 == 0:
        return mulk(k // 2, mul2(P, p), p)
    else:
        return add(P, mulk((k - 1) // 2, mul2(P, p), p))

def search(process_id, Nt, Nw, problem, kangoo_power, starttime):
    DP_rarity = 1 << ((problem - 2 * kangoo_power) // 2 - 2)
    hop_modulo = ((problem - 1) // 2) + kangoo_power
    T, t, dt = [], [], []
    W, w, dw = [], [], []
    for k in range(Nt):
        t.append((3 << (problem - 2)) + random.randint(1, (1 << (problem - 1))))
        T.append(mulk(t[k]))
        dt.append(0)
    for k in range(Nw):
        w.append(random.randint(1, (1 << (problem - 1))))
        W.append(add(W0, mulk(w[k])))
        dw.append(0)
    print('tame and wild herds are prepared')
    oldtime = time.time()
    Hops, Hops_old = 0, 0
    t0 = time.time()
    oldtime = time.time()
    starttime = oldtime
    while True:
        for k in range(Nt):
            Hops += 1
            pw = T[k].x % hop_modulo
            dt[k] = 1 << pw
            solved = check(T[k], t[k], DP_rarity, "tame.txt", T, t, W, w)
            if solved:
                return 'sol. time: %.2f sec' % (time.time() - starttime)
            t[k] += dt[k]
            T[k] = add(P[pw], T[k])
        for k in range(Nw):
            Hops += 1
            pw = W[k].x % hop_modulo
            dw[k] = 1 << pw
            solved = check(W[k], w[k], DP_rarity, "wild.txt", W, w, T, t)
            if solved:
                return 'sol. time: %.2f sec' % (time.time() - starttime)
            w[k] += dw[k]
            W[k] = add(P[pw], W[k])
        t1 = time.time()
        if (t1 - t0) > 5:
            print('%.3f h/s' % ((Hops - Hops_old) / (t1 - t0)))
            t0 = t1
            Hops_old = Hops

start = 2147483647
end = 4294967295
search_range = end - start + 1
problem = search_range.bit_length()

compreessed_public_key = "0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69" #Puzzle 32
kangoo_power = 3
Nt = Nw = 2 ** kangoo_power

X = int(compreessed_public_key, 16)
Y = X2Y(X % (2 ** 256))
if Y % 2 != (X >> 256) % 2:
    Y = modulo - Y
X = X % (2 ** 256)
W0 = Point(X, Y)
starttime = oldtime = time.time()

Hops = 0
random.seed()

hops_list = []
N_tests = 3

def search_wrapper(process_id):
    return search(process_id, Nt, Nw, problem, kangoo_power, starttime)

if __name__ == "__main__":
    num_cpus = multiprocessing.cpu_count()
    N_tests = num_cpus  # Use the number of CPU cores as the number of tests

    with multiprocessing.Pool(processes=N_tests) as pool:
        results = pool.map(search_wrapper, range(N_tests))

    for result in results:
        print(result)
        M, D = 0, 0
        if len(hops_list) > 0:
            M = sum(hops_list) * 1.0 / len(hops_list)
            D = sum((xi - M) ** 2 for xi in hops_list) * 1.0 / len(hops_list)
        print(M, '+/-', (D / (len(hops_list) - 1)) ** 0.5)
        print('Average time to solve: %.2f sec' % ((time.time() - starttime) / N_tests))

In the __name__ == "__main__" block, the number of available CPU cores is determined using multiprocessing.cpu_count(), and N_tests is set to this number. This means that the script will create a separate process for each CPU core available for parallel processing.

If you're going to use multiprocessing, try not to print anything or do any I/O until the very end because the disk access bottleneck will slow the whole loop down (even on SSD - it can never possibly be as fast as a CPU's clock speed).

Actually you should even import tqdm and create a progress bar for that, and then customize the progress bar to show you the key being worked on, how many have already been done, etc. Much better than printing since there are not synchronized with a mutex (by default).

You are  right. Using a progress bar is a much better approach than printing progress statements, especially when dealing with multiprocessing.
The tqdm library is an excellent choice for displaying progress bars in Python.

New script:

Code:

import time
import random
import gmpy2
from functools import lru_cache
import multiprocessing
from tqdm import tqdm

modulo = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
order = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

class Point:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

PG = Point(Gx, Gy)
Z = Point(0, 0)  # zero-point, infinite in real x,y-plane

def mul2(P, p=modulo):
    c = (3 * P.x * P.x * pow(2 * P.y, -1, p)) % p
    R = Point()
    R.x = (c * c - 2 * P.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

def add(P, Q, p=modulo):
    dx = Q.x - P.x
    dy = Q.y - P.y
    c = dy * gmpy2.invert(dx, p) % p
    R = Point()
    R.x = (c * c - P.x - Q.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

@lru_cache(maxsize=None)
def X2Y(X, p=modulo):
    if p % 4 != 3:
        print('prime must be 3 modulo 4')
        return 0
    X = (X ** 3 + 7) % p
    pw = (p + 1) // 4
    Y = 1
    tmp = X
    for w in range(256):
        if (pw >> w) & 1 == 1:
            Y = (Y * tmp) % p
        tmp = pow(tmp, 2, p)
    return Y

def compute_P_table():
    P = [PG]
    for k in range(255):
        P.append(mul2(P[k]))
    return P

P = compute_P_table()

print('P-table prepared')

def comparator(A, Ak, B, Bk):
    result = set(A).intersection(set(B))
    if result:
        sol_kt = A.index(next(iter(result)))
        sol_kw = B.index(next(iter(result)))
        d = Ak[sol_kt] - Bk[sol_kw]
        print('SOLVED:', d)
        with open("results.txt", 'a') as file:
            file.write(('%d' % (Ak[sol_kt] - Bk[sol_kw])) + "\n")
            file.write("---------------\n")
        return True
    else:
        return False

def check(P, Pindex, DP_rarity, file2save, A, Ak, B, Bk):
    if P.x % DP_rarity == 0:
        A.append(P.x)
        Ak.append(Pindex)
        with open(file2save, 'a') as file:
            file.write(('%064x %d' % (P.x, Pindex)) + "\n")
        return comparator(A, Ak, B, Bk)
    else:
        return False

def mulk(k, P=PG, p=modulo):
    if k == 0:
        return Z
    elif k == 1:
        return P
    elif k % 2 == 0:
        return mulk(k // 2, mul2(P, p), p)
    else:
        return add(P, mulk((k - 1) // 2, mul2(P, p), p))

def search(process_id, Nt, Nw, problem, kangoo_power, starttime):
    DP_rarity = 1 << ((problem - 2 * kangoo_power) // 2 - 2)
    hop_modulo = ((problem - 1) // 2) + kangoo_power
    T, t, dt = [], [], []
    W, w, dw = [], [], []
    for k in range(Nt):
        t.append((3 << (problem - 2)) + random.randint(1, (1 << (problem - 1))))
        T.append(mulk(t[k]))
        dt.append(0)
    for k in range(Nw):
        w.append(random.randint(1, (1 << (problem - 1))))
        W.append(add(W0, mulk(w[k])))
        dw.append(0)

    # Move the "tame and wild herds are prepared" line here
    print('tame and wild herds are prepared')

    oldtime = time.time()
    Hops, Hops_old = 0, 0
    t0 = time.time()
    starttime = oldtime
    pbar_t = tqdm(total=Nt, desc=f"Process {process_id}: tame", position=process_id, dynamic_ncols=True, leave=False, ncols=100)
    pbar_w = tqdm(total=Nw, desc=f"Process {process_id}: wild", position=process_id, dynamic_ncols=True, leave=False, ncols=100)

    while True:
        for k in range(Nt):
            Hops += 1
            pw = T[k].x % hop_modulo
            dt[k] = 1 << pw
            solved = check(T[k], t[k], DP_rarity, "tame.txt", T, t, W, w)
            if solved:
                pbar_t.close()
                pbar_w.close()
                elapsed_time_t = time.time() - starttime
                print(f'Process {process_id}: tame sol. time: %.2f sec' % elapsed_time_t)
                return f'Process {process_id}: tame sol. time: %.2f sec' % elapsed_time_t
            t[k] += dt[k]
            T[k] = add(P[pw], T[k])
            pbar_t.update(1)

        for k in range(Nw):
            Hops += 1
            pw = W[k].x % hop_modulo
            dw[k] = 1 << pw
            solved = check(W[k], w[k], DP_rarity, "wild.txt", W, w, T, t)
            if solved:
                pbar_t.close()
                pbar_w.close()
                elapsed_time_w = time.time() - starttime
                print(f'Process {process_id}: wild sol. time: %.2f sec' % elapsed_time_w)
                return f'Process {process_id}: wild sol. time: %.2f sec' % elapsed_time_w
            w[k] += dw[k]
            W[k] = add(P[pw], W[k])
            pbar_w.update(1)

def search_wrapper(args):
    return search(*args)

if __name__ == "__main__":
    start = 2147483647
    end = 4294967295
    search_range = end - start + 1
    problem = search_range.bit_length()

    compreessed_public_key = "0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69" #Puzzle 32
    kangoo_power = 3
    Nt = Nw = 2 ** kangoo_power

    X = int(compreessed_public_key, 16)
    Y = X2Y(X % (2 ** 256))
    if Y % 2 != (X >> 256) % 2:
        Y = modulo - Y
    X = X % (2 ** 256)
    W0 = Point(X, Y)
    starttime = oldtime = time.time()

    num_cpus = multiprocessing.cpu_count()
    N_tests = num_cpus  # Use the number of CPU cores as the number of tests

    args = [(i, Nt, Nw, problem, kangoo_power, starttime) for i in range(N_tests)]

    with multiprocessing.Pool(processes=N_tests) as pool:
        results = list(tqdm(pool.imap(search_wrapper, args), total=N_tests))

    # Output the average time to solve
    total_time = sum(float(result.split(': ')[-1][:-4]) for result in results if result is not None)
    print('Average time to solve: %.2f sec' % (total_time / N_tests))

It shows that the "P-table prepared" message is printed at the beginning, and then it displays progress bars for both "tame" and "wild" processes. After finishing the wild process, it shows "Process 0: wild" progress and the completion time.

Code:

P-table prepared
0%|      | 0/4 [00:00<?, ?it/s]tame and wild herds are prepared
tame and wild herds are prepared
tame and wild herds are prepared
Process 0: wild:   0%|      | 0/8 [00:00<?, ?it/stame and wild herds are prepared
Process 0: wild: 28464it [00:01, 13883.45it/s]SOLVED: -3093472814                                                                                 
Process 1: tame: 28652it [00:01, 13869.72it/s]Process 2: wild sol. time: 1.83 sec                                                                 
Process 2: tame: 28550it [00:01, 13659.12it/s]SOLVED: 3093472814
Process 0: tame sol. time: 1.86 sec                                                                                                               
 25%|███████████████████████████SOLVED: 3093472814                         | 1/4 [00:01<00:05,  1.89s/it]
Process 1: tame: 47801it [00:02, 36580.65it/s]Process 1: tame sol. time: 2.35 sec                                                                 
 50%|██████████████████████████████████████████SOLVED: 3093472814          | 2/4 [00:02<00:02,  1.08s/it]
Process 3: wild: 68509it [00:02, 29066.35it/s] Process 3: tame sol. time: 3.26 sec
100%|██████████████████████████████████████████████████████████████████████| 4/4 [00:03<00:00,  1.21it/s]
Average time to solve: 2.33 sec3, 51300.68it/s]

[sssergy2705]

is there a multicore version out
or can we edit this to do that , thanks mate for sharing.

Sure, here's the full script with multiprocessing added:

Code:

import time
import random
import gmpy2
from functools import lru_cache
import multiprocessing

modulo = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
order = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

class Point:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

PG = Point(Gx, Gy)
Z = Point(0, 0)  # zero-point, infinite in real x,y-plane

def mul2(P, p=modulo):
    c = (3 * P.x * P.x * pow(2 * P.y, -1, p)) % p
    R = Point()
    R.x = (c * c - 2 * P.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

def add(P, Q, p=modulo):
    dx = Q.x - P.x
    dy = Q.y - P.y
    c = dy * gmpy2.invert(dx, p) % p
    R = Point()
    R.x = (c * c - P.x - Q.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

@lru_cache(maxsize=None)
def X2Y(X, p=modulo):
    if p % 4 != 3:
        print('prime must be 3 modulo 4')
        return 0
    X = (X ** 3 + 7) % p
    pw = (p + 1) // 4
    Y = 1
    tmp = X
    for w in range(256):
        if (pw >> w) & 1 == 1:
            Y = (Y * tmp) % p
        tmp = pow(tmp, 2, p)
    return Y

def compute_P_table():
    P = [PG]
    for k in range(255):
        P.append(mul2(P[k]))
    return P

P = compute_P_table()

print('P-table prepared')

def comparator(A, Ak, B, Bk):
    result = set(A).intersection(set(B))
    if result:
        sol_kt = A.index(next(iter(result)))
        sol_kw = B.index(next(iter(result)))
        print('total time: %.2f sec' % (time.time() - starttime))
        d = Ak[sol_kt] - Bk[sol_kw]
        print('SOLVED:', d)
        with open("results.txt", 'a') as file:
            file.write(('%d' % (Ak[sol_kt] - Bk[sol_kw])) + "\n")
            file.write("---------------\n")
        return True
    else:
        return False

def check(P, Pindex, DP_rarity, file2save, A, Ak, B, Bk):
    if P.x % DP_rarity == 0:
        A.append(P.x)
        Ak.append(Pindex)
        with open(file2save, 'a') as file:
            file.write(('%064x %d' % (P.x, Pindex)) + "\n")
        return comparator(A, Ak, B, Bk)
    else:
        return False

def mulk(k, P=PG, p=modulo):
    if k == 0:
        return Z
    elif k == 1:
        return P
    elif k % 2 == 0:
        return mulk(k // 2, mul2(P, p), p)
    else:
        return add(P, mulk((k - 1) // 2, mul2(P, p), p))

def search(process_id, Nt, Nw, problem, kangoo_power, starttime):
    DP_rarity = 1 << ((problem - 2 * kangoo_power) // 2 - 2)
    hop_modulo = ((problem - 1) // 2) + kangoo_power
    T, t, dt = [], [], []
    W, w, dw = [], [], []
    for k in range(Nt):
        t.append((3 << (problem - 2)) + random.randint(1, (1 << (problem - 1))))
        T.append(mulk(t[k]))
        dt.append(0)
    for k in range(Nw):
        w.append(random.randint(1, (1 << (problem - 1))))
        W.append(add(W0, mulk(w[k])))
        dw.append(0)
    print('tame and wild herds are prepared')
    oldtime = time.time()
    Hops, Hops_old = 0, 0
    t0 = time.time()
    oldtime = time.time()
    starttime = oldtime
    while True:
        for k in range(Nt):
            Hops += 1
            pw = T[k].x % hop_modulo
            dt[k] = 1 << pw
            solved = check(T[k], t[k], DP_rarity, "tame.txt", T, t, W, w)
            if solved:
                return 'sol. time: %.2f sec' % (time.time() - starttime)
            t[k] += dt[k]
            T[k] = add(P[pw], T[k])
        for k in range(Nw):
            Hops += 1
            pw = W[k].x % hop_modulo
            dw[k] = 1 << pw
            solved = check(W[k], w[k], DP_rarity, "wild.txt", W, w, T, t)
            if solved:
                return 'sol. time: %.2f sec' % (time.time() - starttime)
            w[k] += dw[k]
            W[k] = add(P[pw], W[k])
        t1 = time.time()
        if (t1 - t0) > 5:
            print('%.3f h/s' % ((Hops - Hops_old) / (t1 - t0)))
            t0 = t1
            Hops_old = Hops

start = 2147483647
end = 4294967295
search_range = end - start + 1
problem = search_range.bit_length()

compreessed_public_key = "0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69" #Puzzle 32
kangoo_power = 3
Nt = Nw = 2 ** kangoo_power

X = int(compreessed_public_key, 16)
Y = X2Y(X % (2 ** 256))
if Y % 2 != (X >> 256) % 2:
    Y = modulo - Y
X = X % (2 ** 256)
W0 = Point(X, Y)
starttime = oldtime = time.time()

Hops = 0
random.seed()

hops_list = []
N_tests = 3

def search_wrapper(process_id):
    return search(process_id, Nt, Nw, problem, kangoo_power, starttime)

if __name__ == "__main__":
    num_cpus = multiprocessing.cpu_count()
    N_tests = num_cpus  # Use the number of CPU cores as the number of tests

    with multiprocessing.Pool(processes=N_tests) as pool:
        results = pool.map(search_wrapper, range(N_tests))

    for result in results:
        print(result)
        M, D = 0, 0
        if len(hops_list) > 0:
            M = sum(hops_list) * 1.0 / len(hops_list)
            D = sum((xi - M) ** 2 for xi in hops_list) * 1.0 / len(hops_list)
        print(M, '+/-', (D / (len(hops_list) - 1)) ** 0.5)
        print('Average time to solve: %.2f sec' % ((time.time() - starttime) / N_tests))

In the __name__ == "__main__" block, the number of available CPU cores is determined using multiprocessing.cpu_count(), and N_tests is set to this number. This means that the script will create a separate process for each CPU core available for parallel processing.

If you're going to use multiprocessing, try not to print anything or do any I/O until the very end because the disk access bottleneck will slow the whole loop down (even on SSD - it can never possibly be as fast as a CPU's clock speed).

Actually you should even import tqdm and create a progress bar for that, and then customize the progress bar to show you the key being worked on, how many have already been done, etc. Much better than printing since there are not synchronized with a mutex (by default).

You are  right. Using a progress bar is a much better approach than printing progress statements, especially when dealing with multiprocessing.
The tqdm library is an excellent choice for displaying progress bars in Python.

New script:

Code:

import time
import random
import gmpy2
from functools import lru_cache
import multiprocessing
from tqdm import tqdm

modulo = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
order = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

class Point:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

PG = Point(Gx, Gy)
Z = Point(0, 0)  # zero-point, infinite in real x,y-plane

def mul2(P, p=modulo):
    c = (3 * P.x * P.x * pow(2 * P.y, -1, p)) % p
    R = Point()
    R.x = (c * c - 2 * P.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

def add(P, Q, p=modulo):
    dx = Q.x - P.x
    dy = Q.y - P.y
    c = dy * gmpy2.invert(dx, p) % p
    R = Point()
    R.x = (c * c - P.x - Q.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

@lru_cache(maxsize=None)
def X2Y(X, p=modulo):
    if p % 4 != 3:
        print('prime must be 3 modulo 4')
        return 0
    X = (X ** 3 + 7) % p
    pw = (p + 1) // 4
    Y = 1
    tmp = X
    for w in range(256):
        if (pw >> w) & 1 == 1:
            Y = (Y * tmp) % p
        tmp = pow(tmp, 2, p)
    return Y

def compute_P_table():
    P = [PG]
    for k in range(255):
        P.append(mul2(P[k]))
    return P

P = compute_P_table()

print('P-table prepared')

def comparator(A, Ak, B, Bk):
    result = set(A).intersection(set(B))
    if result:
        sol_kt = A.index(next(iter(result)))
        sol_kw = B.index(next(iter(result)))
        d = Ak[sol_kt] - Bk[sol_kw]
        print('SOLVED:', d)
        with open("results.txt", 'a') as file:
            file.write(('%d' % (Ak[sol_kt] - Bk[sol_kw])) + "\n")
            file.write("---------------\n")
        return True
    else:
        return False

def check(P, Pindex, DP_rarity, file2save, A, Ak, B, Bk):
    if P.x % DP_rarity == 0:
        A.append(P.x)
        Ak.append(Pindex)
        with open(file2save, 'a') as file:
            file.write(('%064x %d' % (P.x, Pindex)) + "\n")
        return comparator(A, Ak, B, Bk)
    else:
        return False

def mulk(k, P=PG, p=modulo):
    if k == 0:
        return Z
    elif k == 1:
        return P
    elif k % 2 == 0:
        return mulk(k // 2, mul2(P, p), p)
    else:
        return add(P, mulk((k - 1) // 2, mul2(P, p), p))

def search(process_id, Nt, Nw, problem, kangoo_power, starttime):
    DP_rarity = 1 << ((problem - 2 * kangoo_power) // 2 - 2)
    hop_modulo = ((problem - 1) // 2) + kangoo_power
    T, t, dt = [], [], []
    W, w, dw = [], [], []
    for k in range(Nt):
        t.append((3 << (problem - 2)) + random.randint(1, (1 << (problem - 1))))
        T.append(mulk(t[k]))
        dt.append(0)
    for k in range(Nw):
        w.append(random.randint(1, (1 << (problem - 1))))
        W.append(add(W0, mulk(w[k])))
        dw.append(0)

    # Move the "tame and wild herds are prepared" line here
    print('tame and wild herds are prepared')

    oldtime = time.time()
    Hops, Hops_old = 0, 0
    t0 = time.time()
    starttime = oldtime
    pbar_t = tqdm(total=Nt, desc=f"Process {process_id}: tame", position=process_id, dynamic_ncols=True, leave=False, ncols=100)
    pbar_w = tqdm(total=Nw, desc=f"Process {process_id}: wild", position=process_id, dynamic_ncols=True, leave=False, ncols=100)

    while True:
        for k in range(Nt):
            Hops += 1
            pw = T[k].x % hop_modulo
            dt[k] = 1 << pw
            solved = check(T[k], t[k], DP_rarity, "tame.txt", T, t, W, w)
            if solved:
                pbar_t.close()
                pbar_w.close()
                elapsed_time_t = time.time() - starttime
                print(f'Process {process_id}: tame sol. time: %.2f sec' % elapsed_time_t)
                return f'Process {process_id}: tame sol. time: %.2f sec' % elapsed_time_t
            t[k] += dt[k]
            T[k] = add(P[pw], T[k])
            pbar_t.update(1)

        for k in range(Nw):
            Hops += 1
            pw = W[k].x % hop_modulo
            dw[k] = 1 << pw
            solved = check(W[k], w[k], DP_rarity, "wild.txt", W, w, T, t)
            if solved:
                pbar_t.close()
                pbar_w.close()
                elapsed_time_w = time.time() - starttime
                print(f'Process {process_id}: wild sol. time: %.2f sec' % elapsed_time_w)
                return f'Process {process_id}: wild sol. time: %.2f sec' % elapsed_time_w
            w[k] += dw[k]
            W[k] = add(P[pw], W[k])
            pbar_w.update(1)

def search_wrapper(args):
    return search(*args)

if __name__ == "__main__":
    start = 2147483647
    end = 4294967295
    search_range = end - start + 1
    problem = search_range.bit_length()

    compreessed_public_key = "0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69" #Puzzle 32
    kangoo_power = 3
    Nt = Nw = 2 ** kangoo_power

    X = int(compreessed_public_key, 16)
    Y = X2Y(X % (2 ** 256))
    if Y % 2 != (X >> 256) % 2:
        Y = modulo - Y
    X = X % (2 ** 256)
    W0 = Point(X, Y)
    starttime = oldtime = time.time()

    num_cpus = multiprocessing.cpu_count()
    N_tests = num_cpus  # Use the number of CPU cores as the number of tests

    args = [(i, Nt, Nw, problem, kangoo_power, starttime) for i in range(N_tests)]

    with multiprocessing.Pool(processes=N_tests) as pool:
        results = list(tqdm(pool.imap(search_wrapper, args), total=N_tests))

    # Output the average time to solve
    total_time = sum(float(result.split(': ')[-1][:-4]) for result in results if result is not None)
    print('Average time to solve: %.2f sec' % (total_time / N_tests))

It shows that the "P-table prepared" message is printed at the beginning, and then it displays progress bars for both "tame" and "wild" processes. After finishing the wild process, it shows "Process 0: wild" progress and the completion time.

Code:

P-table prepared
0%|      | 0/4 [00:00<?, ?it/s]tame and wild herds are prepared
tame and wild herds are prepared
tame and wild herds are prepared
Process 0: wild:   0%|      | 0/8 [00:00<?, ?it/stame and wild herds are prepared
Process 0: wild: 28464it [00:01, 13883.45it/s]SOLVED: -3093472814                                                                                 
Process 1: tame: 28652it [00:01, 13869.72it/s]Process 2: wild sol. time: 1.83 sec                                                                 
Process 2: tame: 28550it [00:01, 13659.12it/s]SOLVED: 3093472814
Process 0: tame sol. time: 1.86 sec                                                                                                               
 25%|███████████████████████████SOLVED: 3093472814                         | 1/4 [00:01<00:05,  1.89s/it]
Process 1: tame: 47801it [00:02, 36580.65it/s]Process 1: tame sol. time: 2.35 sec                                                                 
 50%|██████████████████████████████████████████SOLVED: 3093472814          | 2/4 [00:02<00:02,  1.08s/it]
Process 3: wild: 68509it [00:02, 29066.35it/s] Process 3: tame sol. time: 3.26 sec
100%|██████████████████████████████████████████████████████████████████████| 4/4 [00:03<00:00,  1.21it/s]
Average time to solve: 2.33 sec3, 51300.68it/s]

Code:

Process 0: wild: 76121it [00:03, 29910.37it/s]]SOLVED: -3093472814
Process 1: wild: 64721it [00:03, 30101.92it/s]Process 6: wild sol. time: 3.27 sec
Process 5: tame: 68144it [00:03, 25783.91it/s]]
Process 6: tame: 65643it [00:03, 25683.95it/s]SOLVED: -3093472814
Process 7: tame: 67557it [00:03, 29223.45it/s]]
 ... (more hidden) ...
Process 9: wild: 64425it [00:03, 20663.78it/s]]
Process 5: tame: 70777it [00:03, 24056.88it/s]]
Process 19: tame: 62187it [00:03, 27300.44it/s]
Process 7: wild: 69993it [00:03, 29536.12it/s]]
Process 21: wild: 49623it [00:03, 17401.26it/s]
Process 9: wild: 66541it [00:03, 19560.90it/s]
Process 20: wild: 55521it [00:03, 25278.08it/s]
Process 16: tame: 72577it [00:03, 29203.31it/s]
Process 12: tame: 65833it [00:03, 30571.12it/s]

Process 19: tame: 65118it [00:03, 27876.14it/s]
Process 17: wild: 57313it [00:03, 29236.38it/s]
Process 16: wild: 75633it [00:03, 29890.75it/s]

Process 20: wild: 58713it [00:03, 27127.54it/s]Process 21: wild sol. time: 3.29 sec
SOLVED: 30934728144309it [00:03, 20556.27it/s]
Process 40: tame sol. time: 3.24 sec
Process 0: wild: 82297it [00:03, 30400.36it/s]]SOLVED: -3093472814
Process 1: wild: 70905it [00:03, 30503.65it/s]

It gives me such nonsense)

[nomachine]

How about percentage ??

Code:

import time
import random
import gmpy2
from functools import lru_cache
import multiprocessing
from tqdm import tqdm

modulo = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
order = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

class Point:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

PG = Point(Gx, Gy)
Z = Point(0, 0)  # zero-point, infinite in real x,y-plane

def mul2(P, p=modulo):
    c = (3 * P.x * P.x * pow(2 * P.y, -1, p)) % p
    R = Point()
    R.x = (c * c - 2 * P.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

def add(P, Q, p=modulo):
    dx = Q.x - P.x
    dy = Q.y - P.y
    c = dy * gmpy2.invert(dx, p) % p
    R = Point()
    R.x = (c * c - P.x - Q.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

@lru_cache(maxsize=None)
def X2Y(X, p=modulo):
    if p % 4 != 3:
        print('prime must be 3 modulo 4')
        return 0
    X = (X ** 3 + 7) % p
    pw = (p + 1) // 4
    Y = 1
    tmp = X
    for w in range(256):
        if (pw >> w) & 1 == 1:
            Y = (Y * tmp) % p
        tmp = pow(tmp, 2, p)
    return Y

def compute_P_table():
    P = [PG]
    for k in range(255):
        P.append(mul2(P[k]))
    return P

P = compute_P_table()

print('P-table prepared')

def comparator(A, Ak, B, Bk):
    result = set(A).intersection(set(B))
    if result:
        sol_kt = A.index(next(iter(result)))
        sol_kw = B.index(next(iter(result)))
        d = Ak[sol_kt] - Bk[sol_kw]
        print('SOLVED:', d)
        with open("results.txt", 'a') as file:
            file.write(('%d' % (Ak[sol_kt] - Bk[sol_kw])) + "\n")
            file.write("---------------\n")
        return True
    else:
        return False

def check(P, Pindex, DP_rarity, file2save, A, Ak, B, Bk):
    if P.x % DP_rarity == 0:
        A.append(P.x)
        Ak.append(Pindex)
        with open(file2save, 'a') as file:
            file.write(('%064x %d' % (P.x, Pindex)) + "\n")
        return comparator(A, Ak, B, Bk)
    else:
        return False

def mulk(k, P=PG, p=modulo):
    if k == 0:
        return Z
    elif k == 1:
        return P
    elif k % 2 == 0:
        return mulk(k // 2, mul2(P, p), p)
    else:
        return add(P, mulk((k - 1) // 2, mul2(P, p), p))

def search(process_id, Nt, Nw, problem, kangoo_power, starttime):
    DP_rarity = 1 << ((problem - 2 * kangoo_power) // 2 - 2)
    hop_modulo = ((problem - 1) // 2) + kangoo_power
    T, t, dt = [], [], []
    W, w, dw = [], [], []
    for k in range(Nt):
        t.append((3 << (problem - 2)) + random.randint(1, (1 << (problem - 1))))
        T.append(mulk(t[k]))
        dt.append(0)
    for k in range(Nw):
        w.append(random.randint(1, (1 << (problem - 1))))
        W.append(add(W0, mulk(w[k])))
        dw.append(0)

    print('tame and wild herds are prepared')

    oldtime = time.time()
    Hops, Hops_old = 0, 0
    t0 = time.time()
    starttime = oldtime = time.time()

    total_tame_iterations = Nt * (problem - 2 * kangoo_power - 2)
    total_wild_iterations = Nw * (problem - 2 * kangoo_power - 2)
    total_iterations = total_tame_iterations + total_wild_iterations

    pbar_t = tqdm(total=total_tame_iterations, desc=f"Process {process_id}: tame", position=process_id, leave=False, ncols=50, bar_format="{desc:<0}|{bar} | {percentage:3.2f}% | ")
    pbar_w = tqdm(total=total_wild_iterations, desc=f"Process {process_id}: wild", position=process_id, leave=False, ncols=50, bar_format="{desc:<0}|{bar} | {percentage:3.2f}% | ")

    while True:
        for k in range(Nt):
            Hops += 1
            pw = T[k].x % hop_modulo
            dt[k] = 1 << pw
            solved = check(T[k], t[k], DP_rarity, "tame.txt", T, t, W, w)
            if solved:
                pbar_t.close()
                pbar_w.close()
                elapsed_time_t = time.time() - starttime
                percentage_completed = (Hops / total_iterations) * 100
                print(f'Process {process_id}: tame completed: %.2f%%' % (percentage_completed % 100))
                return f'Process {process_id}: tame sol. time: %.2f sec' % elapsed_time_t
            t[k] += dt[k]
            T[k] = add(P[pw], T[k])
            pbar_t.update(1)

        for k in range(Nw):
            Hops += 1
            pw = W[k].x % hop_modulo
            dw[k] = 1 << pw
            solved = check(W[k], w[k], DP_rarity, "wild.txt", W, w, T, t)
            if solved:
                pbar_t.close()
                pbar_w.close()
                elapsed_time_w = time.time() - starttime
                percentage_completed = (Hops / total_iterations) * 100
                print(f'Process {process_id}: wild completed: %.2f%%' % (percentage_completed % 100))
                return f'Process {process_id}: wild sol. time: %.2f sec' % elapsed_time_w
            w[k] += dw[k]
            W[k] = add(P[pw], W[k])
            pbar_w.update(1)

def search_wrapper(args):
    return search(*args)

if __name__ == "__main__":
    start = 2147483647
    end = 4294967295
    search_range = end - start + 1
    problem = search_range.bit_length()

    compressed_public_key = "0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69" #Puzzle 32
    kangoo_power = 3
    Nt = Nw = 2 ** kangoo_power

    X = int(compressed_public_key, 16)
    Y = X2Y(X % (2 ** 256))
    if Y % 2 != (X >> 256) % 2:
        Y = modulo - Y
    X = X % (2 ** 256)
    W0 = Point(X, Y)
    starttime = oldtime = time.time()

    num_cpus = multiprocessing.cpu_count()
    N_tests = num_cpus  # Use the number of CPU cores as the number of tests

    args = [(i, Nt, Nw, problem, kangoo_power, starttime) for i in range(N_tests)]

    with multiprocessing.Pool(processes=N_tests) as pool:
        results = list(tqdm(pool.imap(search_wrapper, args), total=N_tests, bar_format="{desc:<0}|{bar} | {percentage:3.2f}% | ", ncols=50))

    total_time = sum(float(result.split(': ')[-1][:-4]) for result in results if result is not None)
    print('Average time to solve: %.2f sec' % (total_time / N_tests))

Result:

Code:

P-table prepared
|                                       | 0.00% | tame and wild herds are prepared
Process 0: wild|                        | 0.00% | tame and wild herds are prepared
tame and wild herds are prepared
tame and wild herds are prepared
Process 0: wild|                        | 0.00% | SOLVED: -3093472814
Process 0: wild completed: 61.46%                 
|█████████▎                            | 25.00% | SOLVED: -3093472814
Process 1: wild|                        | 0.00% | Process 2: wild completed: 28.39%
Process 2: wild|                        | 0.00% | SOLVED: 3093472814
Process 1: tame|                        | 0.00% | Process 1: tame completed: 34.64%
|██████████████████▌                   | 50.00% | SOLVED: -3093472814
Process 3: wild|                        | 0.00% | Process 3: wild completed: 19.01%
|████████████████████████████████████ | 100.00% | 
Average time to solve: 1.53 sec         | 0.00% | 

 

[sssergy2705]

How about percentage ??

Code:

import time
import random
import gmpy2
from functools import lru_cache
import multiprocessing
from tqdm import tqdm

modulo = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEFFFFFC2F
order = 0xFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFEBAAEDCE6AF48A03BBFD25E8CD0364141
Gx = 0x79BE667EF9DCBBAC55A06295CE870B07029BFCDB2DCE28D959F2815B16F81798
Gy = 0x483ada7726a3c4655da4fbfc0e1108a8fd17b448a68554199c47d08ffb10d4b8

class Point:
    def __init__(self, x=0, y=0):
        self.x = x
        self.y = y

PG = Point(Gx, Gy)
Z = Point(0, 0)  # zero-point, infinite in real x,y-plane

def mul2(P, p=modulo):
    c = (3 * P.x * P.x * pow(2 * P.y, -1, p)) % p
    R = Point()
    R.x = (c * c - 2 * P.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

def add(P, Q, p=modulo):
    dx = Q.x - P.x
    dy = Q.y - P.y
    c = dy * gmpy2.invert(dx, p) % p
    R = Point()
    R.x = (c * c - P.x - Q.x) % p
    R.y = (c * (P.x - R.x) - P.y) % p
    return R

@lru_cache(maxsize=None)
def X2Y(X, p=modulo):
    if p % 4 != 3:
        print('prime must be 3 modulo 4')
        return 0
    X = (X ** 3 + 7) % p
    pw = (p + 1) // 4
    Y = 1
    tmp = X
    for w in range(256):
        if (pw >> w) & 1 == 1:
            Y = (Y * tmp) % p
        tmp = pow(tmp, 2, p)
    return Y

def compute_P_table():
    P = [PG]
    for k in range(255):
        P.append(mul2(P[k]))
    return P

P = compute_P_table()

print('P-table prepared')

def comparator(A, Ak, B, Bk):
    result = set(A).intersection(set(B))
    if result:
        sol_kt = A.index(next(iter(result)))
        sol_kw = B.index(next(iter(result)))
        d = Ak[sol_kt] - Bk[sol_kw]
        print('SOLVED:', d)
        with open("results.txt", 'a') as file:
            file.write(('%d' % (Ak[sol_kt] - Bk[sol_kw])) + "\n")
            file.write("---------------\n")
        return True
    else:
        return False

def check(P, Pindex, DP_rarity, file2save, A, Ak, B, Bk):
    if P.x % DP_rarity == 0:
        A.append(P.x)
        Ak.append(Pindex)
        with open(file2save, 'a') as file:
            file.write(('%064x %d' % (P.x, Pindex)) + "\n")
        return comparator(A, Ak, B, Bk)
    else:
        return False

def mulk(k, P=PG, p=modulo):
    if k == 0:
        return Z
    elif k == 1:
        return P
    elif k % 2 == 0:
        return mulk(k // 2, mul2(P, p), p)
    else:
        return add(P, mulk((k - 1) // 2, mul2(P, p), p))

def search(process_id, Nt, Nw, problem, kangoo_power, starttime):
    DP_rarity = 1 << ((problem - 2 * kangoo_power) // 2 - 2)
    hop_modulo = ((problem - 1) // 2) + kangoo_power
    T, t, dt = [], [], []
    W, w, dw = [], [], []
    for k in range(Nt):
        t.append((3 << (problem - 2)) + random.randint(1, (1 << (problem - 1))))
        T.append(mulk(t[k]))
        dt.append(0)
    for k in range(Nw):
        w.append(random.randint(1, (1 << (problem - 1))))
        W.append(add(W0, mulk(w[k])))
        dw.append(0)

    print('tame and wild herds are prepared')

    oldtime = time.time()
    Hops, Hops_old = 0, 0
    t0 = time.time()
    starttime = oldtime = time.time()

    total_tame_iterations = Nt * (problem - 2 * kangoo_power - 2)
    total_wild_iterations = Nw * (problem - 2 * kangoo_power - 2)
    total_iterations = total_tame_iterations + total_wild_iterations

    pbar_t = tqdm(total=total_tame_iterations, desc=f"Process {process_id}: tame", position=process_id, leave=False, ncols=50, bar_format="{desc:<0}|{bar} | {percentage:3.2f}% | ")
    pbar_w = tqdm(total=total_wild_iterations, desc=f"Process {process_id}: wild", position=process_id, leave=False, ncols=50, bar_format="{desc:<0}|{bar} | {percentage:3.2f}% | ")

    while True:
        for k in range(Nt):
            Hops += 1
            pw = T[k].x % hop_modulo
            dt[k] = 1 << pw
            solved = check(T[k], t[k], DP_rarity, "tame.txt", T, t, W, w)
            if solved:
                pbar_t.close()
                pbar_w.close()
                elapsed_time_t = time.time() - starttime
                percentage_completed = (Hops / total_iterations) * 100
                print(f'Process {process_id}: tame completed: %.2f%%' % (percentage_completed % 100))
                return f'Process {process_id}: tame sol. time: %.2f sec' % elapsed_time_t
            t[k] += dt[k]
            T[k] = add(P[pw], T[k])
            pbar_t.update(1)

        for k in range(Nw):
            Hops += 1
            pw = W[k].x % hop_modulo
            dw[k] = 1 << pw
            solved = check(W[k], w[k], DP_rarity, "wild.txt", W, w, T, t)
            if solved:
                pbar_t.close()
                pbar_w.close()
                elapsed_time_w = time.time() - starttime
                percentage_completed = (Hops / total_iterations) * 100
                print(f'Process {process_id}: wild completed: %.2f%%' % (percentage_completed % 100))
                return f'Process {process_id}: wild sol. time: %.2f sec' % elapsed_time_w
            w[k] += dw[k]
            W[k] = add(P[pw], W[k])
            pbar_w.update(1)

def search_wrapper(args):
    return search(*args)

if __name__ == "__main__":
    start = 2147483647
    end = 4294967295
    search_range = end - start + 1
    problem = search_range.bit_length()

    compressed_public_key = "0209c58240e50e3ba3f833c82655e8725c037a2294e14cf5d73a5df8d56159de69" #Puzzle 32
    kangoo_power = 3
    Nt = Nw = 2 ** kangoo_power

    X = int(compressed_public_key, 16)
    Y = X2Y(X % (2 ** 256))
    if Y % 2 != (X >> 256) % 2:
        Y = modulo - Y
    X = X % (2 ** 256)
    W0 = Point(X, Y)
    starttime = oldtime = time.time()

    num_cpus = multiprocessing.cpu_count()
    N_tests = num_cpus  # Use the number of CPU cores as the number of tests

    args = [(i, Nt, Nw, problem, kangoo_power, starttime) for i in range(N_tests)]

    with multiprocessing.Pool(processes=N_tests) as pool:
        results = list(tqdm(pool.imap(search_wrapper, args), total=N_tests, bar_format="{desc:<0}|{bar} | {percentage:3.2f}% | ", ncols=50))

    total_time = sum(float(result.split(': ')[-1][:-4]) for result in results if result is not None)
    print('Average time to solve: %.2f sec' % (total_time / N_tests))

Result:

Code:

P-table prepared
|                                       | 0.00% | tame and wild herds are prepared
Process 0: wild|                        | 0.00% | tame and wild herds are prepared
tame and wild herds are prepared
tame and wild herds are prepared
Process 0: wild|                        | 0.00% | SOLVED: -3093472814
Process 0: wild completed: 61.46%                 
|█████████▎                            | 25.00% | SOLVED: -3093472814
Process 1: wild|                        | 0.00% | Process 2: wild completed: 28.39%
Process 2: wild|                        | 0.00% | SOLVED: 3093472814
Process 1: tame|                        | 0.00% | Process 1: tame completed: 34.64%
|██████████████████▌                   | 50.00% | SOLVED: -3093472814
Process 3: wild|                        | 0.00% | Process 3: wild completed: 19.01%
|████████████████████████████████████ | 100.00% | 
Average time to solve: 1.53 sec         | 0.00% | 

 

Code:

Process 1: wild|                        | 0.00% | Process 15: tame completed: 5.73%
                                                  
Process 12: wild|                       | 0.00% | 
Process 12: wild|                       | 0.00% | SOLVED: -3093472814
Process 29: wild completed: 44.53%      | 0.00% | 
SOLVED: 3093472814    
                                                  
Process 0: wild|                        | 0.00% | SOLVED: -3093472814
Process 45: wild completed: 99.74%
Process 13: tame|                       | 0.00% | SOLVED: 3093472814
Process 38: tame completed: 67.45%      | 0.00% | 
                                                  SOLVED: -3093472814
Process 41: wild completed: 12.24%      | 0.00% | 
Process 0: wild|                        | 0.00% | SOLVED: 3093472814
Process 1: tame|                        | 0.00% | Process 19: tame completed: 13.28%
Process 0: wild|                        | 0.00% | SOLVED: -3093472814
Process 0: wild completed: 62.50%                 
|▊                                      | 2.08% | SOLVED: -3093472814
Process 25: wild completed: 11.20%      | 0.00% | Process 31: tame completed: 87.76%
                                                  SOLVED: 3093472814
Process 26: tame completed: 34.64%      | 0.00% | 
Process 42: tame completed: 64.06%                SOLVED: -3093472814
Process 27: wild completed: 19.01%      | 0.00% | 
Process 12: wild|                       | 0.00% | SOLVED: 3093472814
Process 1: wild|                        | 0.00% | Process 13: tame completed: 39.32%
                                                  SOLVED: 3093472814
Process 1: wild|                        | 0.00% | Process 12: tame completed: 58.85%
SOLVED: -3093472814                     | 0.00% | 
Process 5: wild|                        | 0.00% | Process 1: wild completed: 40.10%
|█▌                                     | 4.17% | SOLVED: 3093472814
Process 36: tame completed: 0.78%       | 0.00% | 
SOLVED: 3093472814                      | 0.00% | 
Process 13: wild|                       | 0.00% | Process 5: tame completed: 75.26%
SOLVED: -3093472814                               
Process 39: wild completed: 65.10%      | 0.00% | 
|████████████████████████████████████ | 100.00% | 
Average time to solve: 1.89 sec         | 0.00% | 

 

[marioantonini]

I recently started to approach the search for puzzle keys and I was wondering something.
how many chances are there that if i find for example the key of puzzle 66, which is between
0000000000000000000000000000000000000000000000020000000000000000
000000000000000000000000000000000000000000000003ffffffffffffffff

for example,  find the key of the 66 puzzle, i send the btc from the address to my address thus exposing the public key. How long does it take for a person using kangaroo to find the private account, thus "stealing" my bitcoins, before my tx is confirmed? Are there any solutions to avoid all this? Tnx

[digaran]

I recently started to approach the search for puzzle keys and I was wondering something.
how many chances are there that if i find for example the key of puzzle 66, which is between
0000000000000000000000000000000000000000000000020000000000000000
000000000000000000000000000000000000000000000003ffffffffffffffff

for example,  find the key of the 66 puzzle, i send the btc from the address to my address thus exposing the public key. How long does it take for a person using kangaroo to find the private account, thus "stealing" my bitcoins, before my tx is confirmed? Are there any solutions to avoid all this? Tnx

Yes there is, already taken care of, if you are the first one spending from that address, nobody else even you can not double spend it, RBF is turned off for all puzzle keys.

[7isce]

Yes there is, already taken care of, if you are the first one spending from that address, nobody else even you can not double spend it, RBF is turned off for all puzzle keys.

Where you get this info, If attacker send new transaction with 3BTC as fees then all pools will be so happy to replace the founder(who solve the puzzle) transaction that in best case have fraction of 1BTC as fees.

[digaran]

Yes there is, already taken care of, if you are the first one spending from that address, nobody else even you can not double spend it, RBF is turned off for all puzzle keys.

Where you get this info, If attacker send new transaction with 3BTC as fees then all pools will be so happy to replace the founder(who solve the puzzle) transaction that in best case have fraction of 1BTC as fees.

Well, I have no useful info about RBF other than what I said, but you are right we can never stop double spending unless miners respect RBF signals from txs.
But I'd say for puzzle 66 it would take at least 5 mins to find the key, but this should be automated where a script runs kangaroo after seeing the address has broadcasted the public key, and then after finding the key it needs to double spend it, so for our thief it takes around 5 mins.

66 solver is screwed.🤣