discrete-logarithm
| Crates.io | discrete-logarithm |
| lib.rs | discrete-logarithm |
| version | 1.1.0 |
| created_at | 2023-07-28 15:44:42.75936+00 |
| updated_at | 2025-10-21 09:27:22.728956+00 |
| description | Fast discrete logarithm solver |
| homepage | |
| repository | https://github.com/skyf0l/discrete-logarithm |
| max_upload_size | |
| id | 928598 |
| size | 58,027 |
Skyf0l (skyf0l)
documentation
README
Discrete Logarithm Solver
Fast discrete logarithm solver in Rust.
The code is based on the sympy implementation and translated to Rust.
Based on rug, it can use arbitrary-precision numbers (aka BigNum).
Algorithm
This library solves the discrete logarithm problem: given b, a, and n, find the smallest non-negative integer x such that b^x ≡ a (mod n).
The main discrete_log function intelligently selects the most efficient algorithm based on the characteristics of the input, specifically the order of the group. The following algorithms are implemented:
| Algorithm | Complexity | Memory | Use Case |
|---|---|---|---|
| Trial Multiplication Exhaustive search testing each exponent sequentially |
O(order) | O(1) | Very small orders (< 1,000) |
| Baby-Step Giant-Step Time-memory tradeoff algorithm that precomputes a table of values |
O(√order) | O(√order) | Prime orders when memory usage is acceptable |
| Pollard's Rho Randomized algorithm with minimal memory requirements, same expected time as Shanks |
O(√order) | O(1) | Large prime orders where memory is constrained |
| Pohlig-Hellman Reduces the problem to smaller subproblems using the factorization of the group order |
O(∑ e_i(log(n) + √p_i)) | O(log(order)) | Composite orders (non-prime) |
| Index Calculus Most efficient for very large primes, uses smooth numbers and linear algebra |
O(exp(2√(log(n)log(log(n))))) | O(B) | Very large prime orders where exp(2√(log(n)log(log(n)))) < √order |
Algorithm Selection Logic
The library automatically selects the optimal algorithm:
- If order < 1,000: use Trial Multiplication
- If order is prime (or probably prime):
- If 4√(log(n)log(log(n))) < log(order) - 10: use Index Calculus
- Else if order < 10^12: use Baby-Step Giant-Step
- Else: use Pollard's Rho
- If order is composite: use Pohlig-Hellman
This automatic selection ensures optimal performance across different problem sizes and characteristics.
License
Licensed under either of
- Apache License, Version 2.0 (LICENSE-APACHE or http://www.apache.org/licenses/LICENSE-2.0)
- MIT license (LICENSE-MIT or http://opensource.org/licenses/MIT)
at your option.
Contribution
Unless you explicitly state otherwise, any contribution intentionally submitted for inclusion in the work by you, as defined in the Apache-2.0 license, shall be dual licensed as above, without any additional terms or conditions.