Решение задачи №72 от UniLecs (вариант с итератором по битам)

modpower2.rs

//Тип, по которому строится битовый итератор
type BitBase = u64;

//Чтобы избежать случайной модификации,
//выносим итератор в отдельный модуль
mod bit_iter {
    //Импортируем тип из вышележащего модуля
    use super::BitBase;

    //Структура итератора по битам
    pub struct Bits {
        template: BitBase,
        current: BitBase,
    }

    impl Bits {
        //At MSD = at most significant digit
        //Конструктор. Создаёт итератор, выдающий биты
        //template, начиная с самого левого ненулевого
        pub fn at_msd(template: BitBase) -> Self {
            const MASK: BitBase = !0 ^ (!0 >> 1);
            let current = MASK >> template.leading_zeros();
            Self { template, current }
        }
    }

    //Реализация функционала итератора для Bits
    impl ::std::iter::Iterator for Bits {
        type Item = usize;
        fn next(&mut self) -> Option<Self::Item> {
            if self.current == 0 {
                None
            } else {
                let res = if self.current & self.template == 0 {
                    0
                } else {
                    1
                };
                self.current >>= 1;
                Some(res)
            }
        }
    }
}

//Тип, с которым проводятся вычисления степени.
//Выбирается так, чтобы вместить наибольшие значения
//по условию задачи
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: BitBase, modulus: Base) -> Result<Base, ModPowErr> {
    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 bits = bit_iter::Bits::at_msd(power);

    for i in bits {
        acc = (acc * acc) % modulus;
        if i == 1 {
            acc = (acc * init) % modulus;
        }
    }

    Ok(acc)
}

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, 10_000, 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) = (577_488, 45_335, 355);
    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: https://play.rust-lang.org/?gist=9bbb5eeacd4be3dcc89d7f4bc5b2070c&version=stable