discrete_logarithm/
lib.rs

1#![doc = include_str!("../README.md")]
2#![deny(rust_2018_idioms)]
3#![warn(missing_docs)]
4
5use std::collections::HashMap;
6
7use n_order::n_order_with_factors;
8use rug::{integer::IsPrime, Integer};
9mod n_order;
10mod pohlig_hellman;
11mod pollard_rho;
12mod shanks_steps;
13mod trial_mul;
14mod utils;
15
16pub use n_order::n_order;
17pub use pohlig_hellman::discrete_log_pohlig_hellman;
18pub use pollard_rho::discrete_log_pollard_rho;
19pub use shanks_steps::discrete_log_shanks_steps;
20pub use trial_mul::discrete_log_trial_mul;
21
22/// Discrete logarithm error
23#[derive(thiserror::Error, Debug, Clone, PartialEq, Eq)]
24pub enum Error {
25    /// Log does not exist
26    #[error("Log does not exist")]
27    LogDoesNotExist,
28    /// A and n are not relatively prime
29    #[error("A and n are not relatively prime")]
30    NotRelativelyPrime,
31}
32
33/// Compute the discrete logarithm of `a` in base `b` modulo `n` (smallest non-negative integer `x` where `b**x = a (mod n)`).
34pub fn discrete_log(n: &Integer, a: &Integer, b: &Integer) -> Result<Integer, Error> {
35    discrete_log_with_order(n, a, b, &n_order(b, n)?)
36}
37
38/// Compute the discrete logarithm of `a` in base `b` modulo `n` (smallest non-negative integer `x` where `b**x = a (mod n)`).
39///
40/// If the prime factorization of `n` is known, it can be passed as `n_factors` to speed up the computation.
41pub fn discrete_log_with_factors(
42    n: &Integer,
43    a: &Integer,
44    b: &Integer,
45    n_factors: &HashMap<Integer, usize>,
46) -> Result<Integer, Error> {
47    discrete_log_with_order(n, a, b, &n_order_with_factors(b, n, n_factors)?)
48}
49
50/// Compute the discrete logarithm of `a` in base `b` modulo `n` (smallest non-negative integer `x` where `b**x = a (mod n)`).
51///
52/// If the order of the group is known, it can be passed as `order` to speed up the computation.
53pub fn discrete_log_with_order(
54    n: &Integer,
55    a: &Integer,
56    b: &Integer,
57    order: &Integer,
58) -> Result<Integer, Error> {
59    if *order < 1000 {
60        discrete_log_trial_mul(n, a, b, Some(order))
61    } else if order.is_probably_prime(100) != IsPrime::No {
62        if *order < shanks_steps::MAX_ORDER {
63            discrete_log_shanks_steps(n, a, b, Some(order))
64        } else {
65            discrete_log_pollard_rho(n, a, b, Some(order))
66        }
67    } else {
68        discrete_log_pohlig_hellman(n, a, b, Some(order))
69    }
70}
71
72#[cfg(test)]
73mod tests {
74    use std::str::FromStr;
75
76    use super::*;
77
78    #[test]
79    fn big_discrete_log() {
80        let n = Integer::from_str("83408372012221120677052349409462320990177094246143674474872152829440524098582262384066400107950985845255268335597502228206679771838750219696329523257176739436871327238322817403970284015587320158034304282786944710043150568360761457471641695390427267786485448748458445872307883254297662715749746270343116946519").unwrap();
81        let a = Integer::from_str("109770827223661560471527567179288748906402603483328748683689436879660543465776899146036833470531024202351087008847594392666852763100570391337823820240726499421306887565697452868723849092658743267256316770223643723095601213088336064635680075206929620159782416078143076506249031972043819429093074684182845530529249907297736582589125917235222921623698038868900282049587768700860009877737045693722732170123306528145661683416808514556360429554775212088169626620488741903267154641722293484797745665402402381445609873333905772582972140944493849645600529147490903067975300304532955461710562911203871840101407995813072692212").unwrap();
82        let b = Integer::from_str("65537").unwrap();
83
84        assert_eq!(
85            discrete_log(&n, &a, &b).unwrap(),
86            Integer::from_str("495604594360692646132957963901411709").unwrap(),
87        );
88    }
89}
discrete_logarithm/lib.rs

discrete_logarithm/
lib.rs
