modular_inverse_simple.cpp

Go to the documentation of this file.

 
#include <cassert>   
#include <cstdint>
#include <iostream>  
 
uint64_t imod(uint64_t x, uint64_t y) {
    uint64_t aux = 0;  // auxiliary variable
    uint64_t itr = 0;  // iteration counter
 
    do {  // run the algorithm while not find the inverse
        aux = y * itr + 1;
        itr++;
    } while (aux % x);  // while module aux % x non-zero
 
    return aux / x;
}
 
static void test() {
    std::cout << "First case testing... \n";
    // for a = 3 and b = 11 return 4
    assert(imod(3, 11) == 4);
    std::cout << "\nPassed!\n";
 
    std::cout << "Second case testing... \n";
    // for a = 3 and b = 26 return 9
    assert(imod(3, 26) == 9);
    std::cout << "\nPassed!\n";
 
    std::cout << "Third case testing... \n";
    // for a = 7 and b = 26 return 15
    assert(imod(7, 26) == 15);
    std::cout << "\nPassed!\n";
 
    std::cout << "\nAll test cases have successfully passed!\n";
}
int main() {
    test();  // run self-test implementations
};