Step by Step solution about How to resolve the algorithm Modular inverse step by step in the C++ programming language

Solution 1:

The provided code calculates the multiplicative inverse of a given number using the extended Euclidean algorithm. The multiplicative inverse of a number a modulo m is a number b such that (a * b) % m = 1.

• In the first snippet, a recursive function mul_inv is defined to calculate the multiplicative inverse.
• The algorithm works by repeatedly dividing a by b and updating the values of a, b, x0, and x1 until a becomes 1.
• At this point, x1 will contain the multiplicative inverse of a modulo b0 (the original value of b).
• If x1 is negative, it is adjusted to be positive by adding b0.
• Finally, the function returns x1 as the multiplicative inverse.

In the main function, the mul_inv function is called with the values 42 and 2017, and the result (which is 1165) is printed to the console.

Solution 2:

The second snippet also calculates the multiplicative inverse of a given number using a different recursive algorithm.

• A function ObtainMultiplicativeInverse is defined to calculate the multiplicative inverse.
• The algorithm works by recursively calling itself with the values b and a % b.
• The base case is when b becomes zero, in which case s0 is returned as the multiplicative inverse.
• Otherwise, the function updates the values of s0 and s1 and calls itself again.
• Finally, the function returns s0 as the multiplicative inverse.

In the main function, the ObtainMultiplicativeInverse function is called with the values 42 and 2017, and the result (which is 1165) is printed to the console.

Both snippets implement different recursive algorithms for calculating the multiplicative inverse of a given number. The first snippet uses the extended Euclidean algorithm, while the second snippet uses a different recursive algorithm. Both algorithms are correct and will produce the same result for the given input values.

#include <iostream>
 
int mul_inv(int a, int b)
{
	int b0 = b, t, q;
	int x0 = 0, x1 = 1;
	if (b == 1) return 1;
	while (a > 1) {
		q = a / b;
		t = b, b = a % b, a = t;
		t = x0, x0 = x1 - q * x0, x1 = t;
	}
	if (x1 < 0) x1 += b0;
	return x1;
}
 
int main(void) {
	std::cout << mul_inv(42, 2017) << std::endl;
	return 0;
}


#include <iostream>

short ObtainMultiplicativeInverse(int a, int b, int s0 = 1, int s1 = 0)
{
    return b==0? s0: ObtainMultiplicativeInverse(b, a%b, s1, s0 - s1*(a/b));
}

int main(int argc, char* argv[])
{
    std::cout << ObtainMultiplicativeInverse(42, 2017) << std::endl;
    return 0;
}