How to resolve the algorithm Modular inverse step by step in the tsql programming language

Published on 12 May 2024 09:40 PM

How to resolve the algorithm Modular inverse step by step in the tsql programming language

Table of Contents

Problem Statement

From Wikipedia: In modular arithmetic,   the modular multiplicative inverse of an integer   a   modulo   m   is an integer   x   such that Or in other words, such that: It can be shown that such an inverse exists   if and only if   a   and   m   are coprime,   but we will ignore this for this task.

Either by implementing the algorithm, by using a dedicated library or by using a built-in function in your language,   compute the modular inverse of   42 modulo 2017.

Let's start with the solution:

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

Source code in the tsql programming language

;WITH Iterate(N,A,B,X0,X1)
	AS (
		SELECT 
			1
			,CASE WHEN @a < 0 THEN @b-(-@a % @b) ELSE @a END
			,CASE WHEN @b < 0 THEN -@b ELSE @b END
			,0
			,1
		UNION ALL
		SELECT 
			N+1
			,B
			,A%B
			,X1-((A/B)*X0)
			,X0
		FROM Iterate
		WHERE A != 1 AND B != 0
	),
	ModularInverse(Result)
	AS (
		SELECT
			-1
			FROM Iterate
			WHERE A != 1 AND B = 0
		UNION ALL
		SELECT
			TOP(1)
			CASE WHEN X1 < 0 THEN X1+@b ELSE X1 END AS Result
			FROM Iterate
			WHERE (SELECT COUNT(*) FROM Iterate WHERE A != 1 AND B = 0) = 0
			ORDER BY N DESC
	)
	SELECT *
	FROM ModularInverse


  

You may also check:How to resolve the algorithm Sorting algorithms/Merge sort step by step in the AppleScript programming language
You may also check:How to resolve the algorithm Draw a clock step by step in the Tcl programming language
You may also check:How to resolve the algorithm Arrays step by step in the Gambas programming language
You may also check:How to resolve the algorithm Partition function P step by step in the Delphi programming language
You may also check:How to resolve the algorithm Loops/For with a specified step step by step in the Vala programming language