Решение задачи №72 от UniLecs

modpow.rs

type Base = u64;

//Тип возможной ошибки при вычислении степени
#[derive(Debug, PartialEq)]
enum ModPowErr {
    ZeroModulus,    //Деление на ноль не определено
    ZeroPowerOfZero //Выражение 0^0 не определено
}

//Считает x ≡ init^power (mod modulus).
//Используется метод быстрого возведения в степень
//(https://en.wikipedia.org/wiki/Exponentiation_by_squaring)
//с модификацией: вычислением остатка от деления на modulus
//на каждом шаге
fn modular_power(init: Base, power: Base, modulus: Base) -> Base {
    match (init, power, modulus) {
        (_, _, 0) => return Err(ModPowErr::ZeroModulus),
        (0, 0, _) => return Err(ModPowErr::ZeroPowerOfZero),
        (0, _, _) => return Ok(0),
        (1, _, _) => return Ok(1),
        (_, 0, _) => return Ok(1),
        _         => (),
    }

    let mut acc = 1;
    let offset = power.leading_zeros();
    let mut p = power << offset;
    let bits = significant_bits(power);
    
    for _ in 0..bits {
        acc = (acc * acc) % modulus;
        if begins_with_one(p) {
            acc = (acc * init) % modulus;
        }
        p <<= 1;
    }
    
    Ok(acc)
}

//Считает количество значащих битов в двоичном виде числа,
//т. е. номер справа самой левой единицы
fn significant_bits(x: Base) -> usize {
    let mut acc = 0;
    let mut x = x;
    while x != 0 {
        x >>= 1;
        acc += 1;
    }
    acc
}

//Проверяет, является ли самый старший бит единичным
fn begins_with_one(x: Base) -> bool {
    const MASK: Base = !0 ^ (!0 >> 1);
    (x & MASK) != 0
}

//Наивная реализация решения задачи.
//Используется для тестирования более продвинутого варианта
fn modular_power_naive(init: Base, power: Base, modulus: Base) -> Base {
    let mut acc = init;
    for _ in 1..power {
        acc = (acc * init) % modulus;
    }
    acc
}

//=====================================================================

//Тесты
#[test]
fn do_tests() {
    let (a, b, m) = (595, 703, 991);
    assert_eq!(
        modular_power_naive(a, b, m),
        modular_power(a, b, m).unwrap()
    );

    let (a, b, m) = (1_000_000_000, 3_000_000, 32677);
    assert_eq!(
        modular_power_naive(a, b, m),
        modular_power(a, b, m).unwrap()
    );
    
    let (a, b, m) = (1, 10_000, 991);
    assert_eq!(
        1,
        modular_power(a, b, m).unwrap()
    );
    
    let (a, b, m) = (0, 10_000, 991);
    assert_eq!(
        0,
        modular_power(a, b, m).unwrap()
    );
    
    let (a, b, m) = (334, 0, 991);
    assert_eq!(
        1,
        modular_power(a, b, m).unwrap()
    );
    
    let (a, b, m) = (0, 0, 0);
    assert_eq!(
        Err(ModPowErr::ZeroModulus),
        modular_power(a, b, m)
    );
    
    let (a, b, m) = (0, 0, 1);
    assert_eq!(
        Err(ModPowErr::ZeroPowerOfZero),
        modular_power(a, b, m)
    );
}

Playground (rev. 1): https://play.rust-lang.org/?gist=3cc1f92f25d781e726020147a60c3caa&version=stable

Playground (rev. 4): https://play.rust-lang.org/?gist=16c02f7213a928907acaa8fbbe04791f&version=stable

Playground (rev. 5): https://play.rust-lang.org/?gist=e136d01214270bae679e16d6b36ee0a9&version=stable