Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
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
xnumber
ynumber
Returns
the modular inverse
20 {
21 uint64_t aux = 0; // auxiliary variable
22 uint64_t itr = 0; // iteration counter
23
24 do { // run the algorithm while not find the inverse
25 aux = y * itr + 1;
26 itr++;
27 } while (aux % x); // while module aux % x non-zero
28
29 return aux / x;
30}

◆ main()

int main ( void )

Main function.

Returns
0 on exit
58 {
59 test(); // run self-test implementations
60};
static void test()
self-test implementations
Definition modular_inverse_simple.cpp:36
Here is the call graph for this function:

◆ test()

static void test ( )
static

self-test implementations

Returns
void
36 {
37 std::cout << "First case testing... \n";
38 // for a = 3 and b = 11 return 4
39 assert(imod(3, 11) == 4);
40 std::cout << "\nPassed!\n";
41
42 std::cout << "Second case testing... \n";
43 // for a = 3 and b = 26 return 9
44 assert(imod(3, 26) == 9);
45 std::cout << "\nPassed!\n";
46
47 std::cout << "Third case testing... \n";
48 // for a = 7 and b = 26 return 15
49 assert(imod(7, 26) == 15);
50 std::cout << "\nPassed!\n";
51
52 std::cout << "\nAll test cases have successfully passed!\n";
53}
uint64_t imod(uint64_t x, uint64_t y)
for IO operations
Definition modular_inverse_simple.cpp:20
Here is the call graph for this function: