Crate discrete_logarithm

Expand description

§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.

Enums§

Error: Discrete logarithm error

Functions§

discrete_log: Compute the discrete logarithm of a in base b modulo n (smallest non-negative integer x where b**x = a (mod n)).
discrete_log_index_calculus: Index Calculus algorithm for computing the discrete logarithm of a in base b modulo n.
discrete_log_pohlig_hellman: Pohlig-Hellman algorithm for computing the discrete logarithm of a in base b modulo n (smallest non-negative integer x where b**x = a (mod n)).
discrete_log_pollard_rho: Pollard’s Rho algorithm for computing the discrete logarithm of a in base b modulo n (smallest non-negative integer x where b**x = a (mod n)).
discrete_log_shanks_steps: Baby-step giant-step algorithm for computing the discrete logarithm of a in base b modulo n (smallest non-negative integer x where b**x = a (mod n)).
discrete_log_trial_mul: Trial multiplication algorithm for computing the discrete logarithm of a in base b modulo n (smallest non-negative integer x where b**x = a (mod n)).
discrete_log_with_factors: Compute the discrete logarithm of a in base b modulo n (smallest non-negative integer x where b**x = a (mod n)).
discrete_log_with_order: Compute the discrete logarithm of a in base b modulo n (smallest non-negative integer x where b**x = a (mod n)).
n_order: Returns the order of a modulo n.