modular_inverse_simple.cpp File Reference

Simple implementation of modular multiplicative inverse More...

#include <cassert>
#include <iostream>

Include dependency graph for modular_inverse_simple.cpp:

Functions
uint64_t	imod (uint64_t x, uint64_t y)
	for IO operations
static void	test ()
	self-test implementations
int	main ()
	Main function.

Detailed Description

Simple implementation of modular multiplicative inverse

this algorithm calculates the modular inverse x^{-1} \mod y iteratively

Function Documentation

imod()

uint64_t imod	(	uint64_t	x,
		uint64_t	y )

for IO operations

for assert

Function imod Calculates the modular inverse of x with respect to y, x^{-1} \mod y

Parameters

x	number
y	number

Returns

the modular inverse

                                      {
    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;
}

main()

int main

(

void

)

Main function.

Returns

0 on exit

           {
    test();  // run self-test implementations
};

Here is the call graph for this function:

test()

static void test ( )

static

self-test implementations

Returns

void

                   {
    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";
}

Here is the call graph for this function: