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