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 index_calculus;
10mod n_order;
11mod pohlig_hellman;
12mod pollard_rho;
13mod shanks_steps;
14mod trial_mul;
15mod utils;
16
17pub use index_calculus::discrete_log_index_calculus;
18pub use n_order::n_order;
19pub use pohlig_hellman::discrete_log_pohlig_hellman;
20pub use pollard_rho::discrete_log_pollard_rho;
21pub use shanks_steps::discrete_log_shanks_steps;
22pub use trial_mul::discrete_log_trial_mul;
23
24/// Discrete logarithm error
25#[derive(thiserror::Error, Debug, Clone, PartialEq, Eq)]
26pub enum Error {
27    /// Log does not exist
28    #[error("Log does not exist")]
29    LogDoesNotExist,
30    /// A and n are not relatively prime
31    #[error("A and n are not relatively prime")]
32    NotRelativelyPrime,
33}
34
35/// Compute the discrete logarithm of `a` in base `b` modulo `n` (smallest non-negative integer `x` where `b**x = a (mod n)`).
36pub fn discrete_log(n: &Integer, a: &Integer, b: &Integer) -> Result<Integer, Error> {
37    discrete_log_with_order(n, a, b, &n_order(b, n)?)
38}
39
40/// Compute the discrete logarithm of `a` in base `b` modulo `n` (smallest non-negative integer `x` where `b**x = a (mod n)`).
41///
42/// If the prime factorization of `n` is known, it can be passed as `n_factors` to speed up the computation.
43pub fn discrete_log_with_factors(
44    n: &Integer,
45    a: &Integer,
46    b: &Integer,
47    n_factors: &HashMap<Integer, usize>,
48) -> Result<Integer, Error> {
49    discrete_log_with_order(n, a, b, &n_order_with_factors(b, n, n_factors)?)
50}
51
52/// Compute the discrete logarithm of `a` in base `b` modulo `n` (smallest non-negative integer `x` where `b**x = a (mod n)`).
53///
54/// If the order of the group is known, it can be passed as `order` to speed up the computation.
55pub fn discrete_log_with_order(
56    n: &Integer,
57    a: &Integer,
58    b: &Integer,
59    order: &Integer,
60) -> Result<Integer, Error> {
61    // Validate input: n should be positive
62    if *n < 1 {
63        return Err(Error::LogDoesNotExist);
64    }
65    // Special case: n == 1
66    if *n == 1 {
67        return Ok(Integer::from(0));
68    }
69
70    if *order < 1000 {
71        discrete_log_trial_mul(n, a, b, Some(order))
72    } else if order.is_probably_prime(100) != IsPrime::No {
73        // Shanks and Pollard rho are O(sqrt(order)) while index calculus is O(exp(2*sqrt(log(n)log(log(n)))))
74        // we compare the expected running times to determine the algorithm which is expected to be faster
75        let n_f64 = n.to_f64();
76        let order_f64 = order.to_f64();
77        let log_n = n_f64.ln();
78        let log_log_n = log_n.ln();
79        let log_order = order_f64.ln();
80
81        // Use index calculus if 4*sqrt(log(n)*log(log(n))) < log(order) - 10
82        if 4.0 * (log_n * log_log_n).sqrt() < log_order - 10.0 {
83            discrete_log_index_calculus(n, a, b, Some(order))
84        } else if *order < shanks_steps::MAX_ORDER {
85            discrete_log_shanks_steps(n, a, b, Some(order))
86        } else {
87            discrete_log_pollard_rho(n, a, b, Some(order))
88        }
89    } else {
90        discrete_log_pohlig_hellman(n, a, b, Some(order))
91    }
92}
93
94#[cfg(test)]
95mod tests {
96    use std::str::FromStr;
97
98    use rug::ops::Pow;
99
100    use super::*;
101
102    #[test]
103    fn discrete_log_() {
104        assert_eq!(
105            discrete_log(&587.into(), &(Integer::from(2).pow(9)), &2.into(),).unwrap(),
106            9
107        );
108        assert_eq!(
109            discrete_log(&2456747.into(), &(Integer::from(3).pow(51)), &3.into(),).unwrap(),
110            51
111        );
112        assert_eq!(
113            discrete_log(&32942478.into(), &(Integer::from(11).pow(127)), &11.into(),).unwrap(),
114            127
115        );
116        assert_eq!(
117            discrete_log(
118                &Integer::from_str("432751500361").unwrap(),
119                &(Integer::from(7).pow(324)),
120                &7.into(),
121            )
122            .unwrap(),
123            324
124        );
125        assert_eq!(
126            discrete_log(
127                &Integer::from_str("265390227570863").unwrap(),
128                &Integer::from_str("184500076053622").unwrap(),
129                &2.into(),
130            )
131            .unwrap(),
132            Integer::from_str("17835221372061").unwrap(),
133        );
134        assert_eq!(
135            discrete_log(
136                &Integer::from_str("22708823198678103974314518195029102158525052496759285596453269189798311427475159776411276642277139650833937").unwrap(),
137                &Integer::from_str("17463946429475485293747680247507700244427944625055089103624311227422110546803452417458985046168310373075327").unwrap(),
138                &123456.into(),
139            )
140            .unwrap(),
141            Integer::from_str("2068031853682195777930683306640554533145512201725884603914601918777510185469769997054750835368413389728895").unwrap(),
142        );
143        assert_eq!(
144            discrete_log(&5779.into(), &3528.into(), &6215.into(),).unwrap(),
145            687
146        );
147    }
148
149    #[test]
150    fn big_discrete_log() {
151        let n = Integer::from_str("83408372012221120677052349409462320990177094246143674474872152829440524098582262384066400107950985845255268335597502228206679771838750219696329523257176739436871327238322817403970284015587320158034304282786944710043150568360761457471641695390427267786485448748458445872307883254297662715749746270343116946519").unwrap();
152        let a = Integer::from_str("109770827223661560471527567179288748906402603483328748683689436879660543465776899146036833470531024202351087008847594392666852763100570391337823820240726499421306887565697452868723849092658743267256316770223643723095601213088336064635680075206929620159782416078143076506249031972043819429093074684182845530529249907297736582589125917235222921623698038868900282049587768700860009877737045693722732170123306528145661683416808514556360429554775212088169626620488741903267154641722293484797745665402402381445609873333905772582972140944493849645600529147490903067975300304532955461710562911203871840101407995813072692212").unwrap();
153        let b = Integer::from_str("65537").unwrap();
154
155        assert_eq!(
156            discrete_log(&n, &a, &b).unwrap(),
157            Integer::from_str("495604594360692646132957963901411709").unwrap(),
158        );
159    }
160
161    #[test]
162    fn discrete_log_n_equals_one() {
163        // Special case: n == 1 should return 0
164        assert_eq!(discrete_log(&1.into(), &0.into(), &0.into()).unwrap(), 0);
165    }
166
167    #[test]
168    fn discrete_log_n_less_than_one() {
169        // Invalid case: n < 1 will cause n_order to fail with NotRelativelyPrime
170        // when called through discrete_log wrapper
171        assert_eq!(
172            discrete_log(&0.into(), &1.into(), &2.into()),
173            Err(Error::NotRelativelyPrime)
174        );
175        // But when called directly with discrete_log_with_order, validation catches it
176        assert_eq!(
177            discrete_log_with_order(&0.into(), &1.into(), &2.into(), &10.into()),
178            Err(Error::LogDoesNotExist)
179        );
180        assert_eq!(
181            discrete_log_with_order(&(-1).into(), &1.into(), &2.into(), &10.into()),
182            Err(Error::LogDoesNotExist)
183        );
184    }
185}
discrete_logarithm/lib.rs

discrete_logarithm/
lib.rs
