sssergy2705
Copper Member
Jr. Member
 Offline
Activity: 205
Merit: 1
|
 |
August 03, 2023, 12:56:53 PM |
|
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: 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:
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. 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]
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) |
