Re: Pollard's kangaroo ECDLP solver

Quote from: Chail35 on Today at 12:30:04 AM

Here is a calculator to calculate the estimated time it would take to use the Kangaroo Algorithm on a given range and the Keys per second:

Code:

Kangaroo v2.2
Start:8000000000000000000000000
Stop :FFFFFFFFFFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 32
Range width: 2^99
Jump Avg distance: 2^48.95
Number of kangaroos: 2^20.55
Suggested DP: 26
Expected operations: 2^50.61
Expected RAM: 990.8MB
DP size: 26 [0xffffffc000000000]
GPU: GPU #0 NVIDIA GeForce RTX 4070 (46x0 cores) Grid(92x128) (122.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^20.52 kangaroos [21.0s]
[1342.45 MK/s][GPU 1264.50 MK/s][Count 2^38.15][Dead 0][04:18 (Avg 14.8d)][2.1/4.7MB]

And this is what the calculator estimated:

Now, I know this is a stretch and isn't possible in its current state but you'll get the point. Hypothetically, if you were to use Elon Musk's new supercomputer with 100,000 H100s to run the Kangaroo Algorithm on puzzle 130 (doesn't have to be JLP), it would take about 18.5 hours:

Enter start key (64 hex chars, or shorter hex number): 200000000000000000000000000000000
Enter stop key (64 hex chars, or shorter hex number): 3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
Enter keys per second (e.g., 29500000000 or 29,500,000,000): 781250000000000

Estimated time to complete Pollard's Kangaroo algorithm:
0.00 years, 0.00 days, 18.00 hours, 33.00 minutes, 4.35 seconds

Total operations (expected steps): 52,175,271,301,331,132,416
Total key range size: 680,564,733,841,876,926,926,749,214,863,536,422,912

Speedup compared to brute force: 13043817825332781056.00x

Just thought I would share FYI

Too slow...

Code:

./kangaroo -t 0 -gpu -g 284,256 130.txt
Kangaroo v2.2
Start:200000000000000000000000000000000
Stop :3FFFFFFFFFFFFFFFFFFFFFFFFFFFFFFFF
Keys :1
Number of CPU thread: 0
Range width: 2^129
Jump Avg distance: 2^64.01
Number of kangaroos: 2^25.15
Suggested DP: 36
Expected operations: 2^65.60
Expected RAM: 31036.2MB
DP size: 36 [0xfffffffff0000000]
GPU: GPU #0 NVIDIA RTX 6000 Ada Generation (142x0 cores) Grid(284x256) (-1249.0 MB used)
SolveKeyGPU Thread GPU#0: creating kangaroos...
SolveKeyGPU Thread GPU#0: 2^25.15 kangaroos [194.0s]
[2372.91 MK/s][GPU 2372.91 MK/s][Count 2^37.67][Dead 0][01:48 (Avg 746.849y)][2.0/4.0MB] ^C

And a highly optimized GPU jumper

Code:

Device 0: NVIDIA RTX 6000 Ada Generation
Clock rate: 2505 MHz
Memory bus width: 384
Memory peak clock rate: 10001000 kHz
L2 cache size: 100663296
Compute capability: 8.9
Total global memory: 48546 MB
Number of SM: 142
32-bit registers per SM: 65536
Max blocks per SM: 24
Max threads per SM: 1536
32-bit registers per block: 65536
Max threads per block: 1024
Shared memory per SM: 100 KB
Shared memory per block: 48 KB
Warp size: 32
Cores per SM: 0
Total CUDA cores: 0
Max local memory / thread: 233386
CUDA stack size limit: 1024 bytes
FE limb size: 64
gridDim: 142
blockDim: 256
Generating *** jump points
max dp len: 32
Group size / thread: ***
Jumps / thread: ***
Kernel registers: 255
Kernel max threads / block : 256
Kernel local memory: *** bytes
Kernel constant memory: 4096 bytes
[GPU] Computing *** batches of *** elements each over *** jumps (100 steps)
Total elements to jump: ******
Total group operations: 1905891737600.000000
Found DP: 5
[001] Ops: 19058917376 GPU: 5587.1 Mo/s 3411 ms/step CPU: 3439.2 ms/step
Found DP: 2
[002] Ops: 38117834752 GPU: 5589.4 Mo/s 3410 ms/step CPU: 3428.5 ms/step
Found DP: 7
[003] Ops: 57176752128 GPU: 5589.9 Mo/s 3409 ms/step CPU: 3425.1 ms/step

I think it costs a good few hundred thouands $ to solve 130 though. Or luck. Or patience.