This project is still full CPU, migration to GPU is being analyzed.
This repository contains a high-performance implementation of Pollard’s Lambda algorithm for solving the Elliptic Curve Discrete Logarithm Problem (ECDLP) on the secp256k1 curve.
The algorithm uses parallel pseudo-random walks based on an R-adding walk construction.
Each walker maintains:
G is the generator point.
H is the target public key.
a and b are scalar coefficients used for recovery after collision.
The transition function uses a precomputed step table and MurmurHash3 avalanche mixing.
When two walkers reach the same point with different coefficients, a modular equation allows recovery through modular inversion.
5 bits ≈ 00:00:00
10 bits ≈ 00:00:00
15 bits ≈ 00:00:00
20 bits ≈ 00:00:00
25 bits ≈ 00:00:00
30 bits ≈ 00:00:00
35 bits ≈ 00:00:00
40 bits ≈ 00:00:00
45 bits ≈ 00:00:00
50 bits ≈ 00:00:00
55 bits ≈ 00:00:04
60 bits ≈ 00:00:07
65 bits ≈ 00:00:43
70 bits ≈ 00:01:09
The formal equation by van Oorschot and Wiener (1999) on paper: P. C. Van Oorschot & M. J. Wiener (1999) - Parallel Collision Search with Cryptanalytic Applications for the expected total time of the Lambda method operating on a restricted interval is:
The expected constant for the factor k is:
This value represents the theoretical efficiency boundary predicted for parallel collision search when elliptic curve symmetry reduction is applied through the Negation Map.
The implementation achieves an empirical average k-factor of approximately:
This value was obtained through thousands of independent benchmark samples, measuring the average number of operations required to solve interval-restricted searches.
The observed k-factor is the result of the combined effect of multiple engineering optimizations:
— Negation Map optimization.
— Parallel collision search architecture.
— Optimized random walk distribution.
— Distinguished Points collision detection.
— Cache-aware precomputed step windows.
— Efficient walker synchronization.
— Batch Jacobian-to-Affine conversion.
Shows that the implementation operates below the theoretical average bound expected for the generic optimized Pollard's Lambda model, approaching practical optimal performance under real execution conditions.
Lower-than-average k-factor values may still occur due to the statistical nature of random walks, where some searches benefit from favorable trajectory convergence and collision timing.
— Multi-threaded walkers.
— Cache-aware tables.
— Batch inversion.
— Snapshot recovery.
— Distinguished Point system.
— Negation Map optimization.
Inversions in finite fields are computationally expensive. Both versions utilize Batch Inversion, processing multiple walkers simultaneously. This allows the algorithm to perform only one modular inversion per batch, converting Jacobian coordinates to Affine at a fraction of the usual cost, only the x coordinate is calculated to maintain efficiency.
The entire search state: walker positions, scalar coefficients, and the
distinguished-point table, can be saved to disk and restored exactly where it left off. Saves are written atomically via a PID-namespaced temporary file promoted by a single rename(2), with fsync on both the file and its parent directory before commit, guaranteeing full recovery even after a hard power loss. Every snapshot carries an integrity checksum and is validated against the current run parameters before any state is touched, so neither corruption nor a configuration mismatch can produce a silent incorrect resume.
The step window is dynamically adjusted according to the processor's cache behavior. While small searches benefit from larger entropy tables, large searches prioritize lower latency cache access, making the ultimate objective to perfectly balance step entropy and memory locality.
The Distinguished Points strategy is a memory-saving filter. Instead of storing every step of the walk (which would crash your RAM), the algorithm only saves points that satisfy a specific condition: the first d bits of the x coordinate must be zero. When two walkers hit the same DP, a collision is found and the private key is recovered.
The Trade-off:
More DP bits:
— Lower RAM usage.
— Slower detection.
Fewer DP bits:
— Faster detection.
— Higher RAM usage.
When a walker begins traversing a path already explored by another walker, a collision will be delayed if the distinguished points filter condition is not met for both walkers. The delay will be overcome after the distinct points are recorded in the dp table. The higher the dp value, the greater the delay for a collision to be detected and recorded by the hashmap, this inherent delay directly affects the algorithm's empirical k-factor. While the actual path convergence is dictated by the birthday paradox, the delayed detection forces walkers to perform additional operations before the collision is logged. Since the k-factor measures the total steps taken against the theoretical expectation, this DP overhead naturally inflates the final result.. To mitigate this, it would be necessary to disable the dp filter, but this would cause excessive RAM usage and would not be worth the effort, and would ruin the performance. This delay is a necessary evil when using distinct points.
Theoretical Calculus:
unsigned long long RAM_BYTES = (unsigned long long)sysconf(_SC_PAGESIZE) * (unsigned long long)sysconf(_SC_AVPHYS_PAGES);
int dp = std::max(1, std::max((int)std::ceil((key_range / 2.0) - std::log2((double)RAM_BYTES / 128.0 /*128 bytes*/)), key_range >> 2));
Simple Abstraction:
int dp = std::max<int>(1, std::min<int>(key_range >> 2, static_cast<int>(sizeof(int32_t) * CHAR_BIT)));
The expected time complexity of Pollard's Lambda algorithm for elliptic curves is
Each walker stores its current elliptic curve position and scalar state. Multiple independent walkers explore different trajectories simultaneously. This design enables large-scale CPU parallelization.
The implementation applies elliptic curve negation symmetry (Equivalence Class Size 2).
Equivalent points can be treated as the same state during the search.
The expected improvement changes the effective complexity to approximately:
This implementation enforces strict geometric bounds (2S for type 0 walks and 3S for type 2 walks) to prevent long tails and wasted CPU cycles. By cutting off extreme statistical bad luck scenarios at the 3S mark, the engine consistently achieves the expected theoretical average of k ≈ 1.2533.
Due to the nature of the search, it may be possible to obtain solutions with a k-factor < 1.2533. These represent scenarios of extreme statistical luck solving the ECDLP within a distance of just 1S jump. This rare "sniper" event requires three specific conditions to align: the type 2 walker drops extremely close to the private key, immediately merges with a type 1 trail, and quickly triggers a Distinguished Point (DP). While rarer than standard 2S or 3S jumps convergences, the architecture fully capitalizes on these optimal drops when they occur.
J. M. Pollard - Monte Carlo methods for index computation (mod p) (1978)
Richard P. Brent - An improved Monte Carlo factorization algorithm (1980)
Peter L. Montgomery - Speeding the Pollard and Elliptic Curve Methods of Factorization (1987)
P. C. Van Oorschot & M. J. Wiener - Parallel Collision Search with Cryptanalytic Applications (1999)
Gaudry & Schost - A low-memory parallel version of Matsuo, Chao and Tsujii's algorithm (2004)
SECG - SEC 2: Recommended Elliptic Curve Domain Parameters (secp256k1 specification) (2010)
- g++
- boost/multiprecision/cpp_int.hpp
- libssl-dev
-
Clone this repository:
~/$ git clone https://github.com/lucaselblanc/pollardslambda.git -
Install the necessary libraries:
sudo apt update sudo apt install build-essential -y sudo apt install boost-headers -y sudo apt install libssl-dev -y
-
Compile the project:
~/$cd pollardslambda
~/pollardslambda$ make -
Run the program:
~/pollardslambda$ ./lambda <compressed public key(hex)> <key range(int)> <walkers(int)> <OPTIONAL DP(int)> <OPTIONAL Threads(int)> <OPTIONAL snaptime(int)>
Replace
<compressed public key>with the point (G) on the secp256k1 curve multiplied by your private key value, and<key range>with the size of the search interval for (k).Example usage:
~/pollardslambda$ ./lambda --pubkey 02145d2611c823a396ef6712ce0f712f09b9b4f3135e3e0aa3230fb9b6d08d1e16 --keyrange 135 --walkers 1000000 --dp 12 --t 8 --snaptime 15
The random walk begins using the public point of the compressed public key as the parameter H, the target private key range for initializing the initial probability space, and the optional distinguished points parameter, which will be calculated automatically if not defined:
~/pollardslambda$ ./lambda <compressed public key> <key range> <walkers> <dp bits> <threads> <snaptime>--pubkey: The public key derived from the private key (discrete logarithm k) G = Q.
--keyrange: The range covering the regions of the elliptic curve where the discrete logarithm k resides.
--walkers: The walkers have the mission of traversing the elliptic curve point by point, they carry information such as the current point R and the coefficients a and b used to recover k in the event of a collision.
--dp: The Distinguished Points strategy is a memory-saving filter. Instead of storing every step of the walk (which would crash your RAM).
--t: Number of CPU threads/cores used to run the program.
--snaptime: Interval between each progress save, --snaptime 0 don't save anything.
"secp256k1.h" Lucas Leblanc
"parallel_hashmap/phmap.h" Gregory Popovitch
Contributions are welcome! Feel free to open issues or submit pull requests.
This project is licensed under the MIT License. See the LICENSE file for details.
-
🔭 I’m currently working on Pollard's Lambda Algorithm
-
🚀 I’m looking to collaborate on: Cyber-Security
-
📝 I regularly read: Monte Carlo methods for index computation (mod p)
-
📄 Know about my experiences: https://www.linkedin.com/in/lucas-leblanc-215594208
