Pollard's Kangaroo Method Algorithm

kangaroo.rs

extern crate rand;
extern crate num;

use kangaroo::rand::Rng;
use num::ToPrimitive;
use num::{Integer, Zero, One};
use std::collections::HashMap;
use std::sync::Mutex;

#[derive(Debug)]
pub struct DiscreteLogParameters {
    pub prime: num::BigInt,
    pub generator: num::BigInt,
    pub result: num::BigInt,
}

#[derive(Debug)]
struct JumpParameters {
    jump_count: num::BigInt,
    jump_group: num::BigInt,
}

#[derive(Debug)]
struct JumpResult {
    position: num::BigInt,
    distance_jumped: num::BigInt,
}

lazy_static! {
    static ref POWER_MOD_MAP: Mutex<HashMap<(num::BigInt, num::BigInt, num::BigInt), num::BigInt>> = Mutex::new(HashMap::with_capacity(1_000));
}

pub fn calculate_discrete_log(params: &DiscreteLogParameters) -> Option<num::BigInt> {
    let jump_params: JumpParameters = get_bounds(&params);
    let tame_initial_offset: u32 = {
        let mut rng = rand::thread_rng();

        let result: num::BigInt = (num::BigInt::from(rng.gen::<u32>() as i64) % (&params.prime - 1)) + 1;

        result.to_u32().unwrap()
    };

    println!("Performing tame jumps...");
    let tame_jumps = perform_tame_jumps(&num::BigInt::from(tame_initial_offset as i64), &params, &jump_params);

    println!("Performing wild jumps...");
    let wild_jumps = perform_wild_jumps(&params, &jump_params);

    for i in wild_jumps.keys() {
        if tame_jumps.contains_key(i) {
            //we mod by the cardinality of the group which is totient(prime) = prime - 1
            //because the result is technically: x + k * totient(prime)

            let mut result = (tame_initial_offset
                + tame_jumps.get(i).unwrap()
                - wild_jumps.get(i).unwrap()) % (&params.prime - 1);

            result = result + &params.prime - 1;
            result = result % (&params.prime - 1);

            return Some(result);
        }
    }

    return None;
}

fn perform_tame_jumps(tame_initial_offset: &num::BigInt, params: &DiscreteLogParameters, jump_params: &JumpParameters) -> HashMap<num::BigInt, num::BigInt> {
    let mut jumps = HashMap::with_capacity(&jump_params.jump_count.to_usize().unwrap() + 1);

    let tame_initial_position = calculate_initial_tame_location(tame_initial_offset, &params);

    let mut previous_position = tame_initial_position;
    let mut total_distance = num::BigInt::zero();

    let mut iterator = num::BigInt::one();

    while iterator <= jump_params.jump_count {
        let result = calculate_jump(&previous_position, &params, &jump_params);

        previous_position = result.position;
        total_distance = total_distance + result.distance_jumped;

        jumps.insert(previous_position.clone(), total_distance.clone());

        iterator = iterator + 1;
    }

    return jumps;
}

fn perform_wild_jumps(params: &DiscreteLogParameters, jump_params: &JumpParameters) -> HashMap<num::BigInt, num::BigInt> {
    let mut jumps = HashMap::with_capacity(jump_params.jump_count.to_usize().unwrap() + 1);

    let mut previous_position = params.result.clone();
    let mut total_distance = num::BigInt::zero();

    let mut iterator = num::BigInt::one();

    while iterator <= jump_params.jump_count {
        let result = calculate_jump(&previous_position, &params, &jump_params);
        let position = result.position.clone();

        previous_position = position;
        total_distance = total_distance + result.distance_jumped;

        jumps.insert(previous_position.clone(), total_distance.clone());

        iterator = iterator + 1;
    }

    return jumps;
}


fn calculate_initial_tame_location(tame_initial_offset: &num::BigInt, discrete_params: &DiscreteLogParameters) -> num::BigInt {
    power_mod(&discrete_params.generator, tame_initial_offset, &discrete_params.prime)
}

fn calculate_jump(previous_position: &num::BigInt, discrete_params: &DiscreteLogParameters, jump_params: &JumpParameters) -> JumpResult {
    let jump_power = previous_position % &jump_params.jump_group;
    let distance = &num::BigInt::one() << jump_power.to_usize().unwrap(); //2 ^ jump_power
    let new_position = (previous_position
        * power_mod(&discrete_params.generator,
                  &distance,
                  &discrete_params.prime))
        % &discrete_params.prime;
    return JumpResult {
        position: new_position,
        distance_jumped: distance
    };
}

/* left for posterity
pub fn big_power(base: &num::BigInt, power: &num::BigInt) -> num::BigInt {
    if power.is_zero() {
        num::BigInt::one()
    }
    else if power.eq(&num::BigInt::from(1)) {
        base.clone()
    } else {
        let new_base = base * base;
        let new_power = power >> 1;
        let base_modifier = if power.is_even() { num::BigInt::one() } else { base.clone() };

         base_modifier * big_power(&new_base, &new_power)
    }
}
*/

pub fn power_mod(base: &num::BigInt, power: &num::BigInt, group: &num::BigInt) -> num::BigInt {
    let map_key = (base.clone(), power.clone(), group.clone());
    let has_entry = POWER_MOD_MAP.lock().unwrap().contains_key(&map_key);

    let result = if power.eq(&num::BigInt::one()) {
        base.clone()
    } else if has_entry {
        POWER_MOD_MAP.lock().unwrap().get(&map_key).unwrap().clone()
    } else {
        let new_base = (base * base) % group;
        let new_power = power >> 1;

        let base_modifier = if power.is_even() { num::BigInt::one() } else { base.clone() };

        base_modifier * power_mod(&new_base, &new_power, group)
    } % group;

    if !has_entry {
        POWER_MOD_MAP.lock().unwrap().insert((base.clone(), power.clone(), group.clone()), result.clone());
    }

    return result;
}

/// Returns a result that is guaranteed to be sqrt(value) <= x < 2 * sqrt(value)
fn rough_sqrt(value: &num::BigInt) -> num::BigInt {
    let result = value.clone();
    let bits = log_2_floor(&result);

    result >> (bits >> 1).to_usize().unwrap()
}

fn log_2_floor(value: &num::BigInt) -> num::BigInt {
    num::BigInt::from(value.bits() as i64 - 1)
}

fn get_bounds(params: &DiscreteLogParameters) -> JumpParameters {
    let jump_count = rough_sqrt(&params.prime);
    let jump_group = log_2_floor(&params.prime);

    return JumpParameters {
        jump_count,
        jump_group
    };
}

main.rs

#[macro_use]
extern crate lazy_static;
use std::env;

mod kangaroo;

extern crate num;

enum CliParams {
    Generator = 1,
    Prime = 2,
    Result = 3,
}

fn main() {
    let result = get_parameters();

    match result {
        Some(params) => {
            let discrete_log = kangaroo::calculate_discrete_log(&params);

            match discrete_log {
                Some(log) => println!("{}", log),
                None => println!("-1")
            };
        },
        _ => {},
    }
}

fn get_parameters() -> Option<kangaroo::DiscreteLogParameters> {
    let params: Vec<String> = env::args().collect();

    //execution path + 3 cli parameters
    if params.len() == 4 {
        return Some(kangaroo::DiscreteLogParameters {
            prime: params[CliParams::Prime as usize].parse::<num::BigInt>().unwrap(),
            generator: params[CliParams::Generator as usize].parse::<num::BigInt>().unwrap(),
            result: params[CliParams::Result as usize].parse::<num::BigInt>().unwrap(),
        });
    } else {
        print_help();

        return None;
    }
}

fn print_help() {
    println!("Calculates discrete logs using Kangaroo Method from Pollard");
    println!("Solves log_<base>(<result>) = `x` for multiplicative group mod <prime>");
    println!("Expects 32 bit integers for all parameters\n");
    println!("Usage: kangaroo <base> <prime> <result>");
    println!("Returns 32 integer result if successful, -1 otherwise.");
}

it gives an error on line 180 due to type annotations