Created
June 1, 2024 08:45
-
-
Save J16N/fea6b0fe85b254db67445183520f5e54 to your computer and use it in GitHub Desktop.
Finding multiplicative inverse using extended euclidean algorithm.
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| def multiplicative_inverse(a: int, b: int, t1: int = 0, t2: int = 1): | |
| if b > a: | |
| return multiplicative_inverse(b, a, t1, t2) | |
| if b == 0: | |
| return t1 | |
| q = a // b | |
| r = a % b | |
| t = t1 - t2 * q | |
| return multiplicative_inverse(b, r, t2, t) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment