Modular inverse problem
programming
Statement
Modular inverse problem
Given 2 $n$-bit integers $x, N \geq 0$ what is $x^{-1}$ mod $N$.
Solutions
- Modular inverse algorithm (extended Euclidean algorithm)
- This has run time $O(n^3)$.
Given 2 $n$-bit integers $x, N \geq 0$ what is $x^{-1}$ mod $N$.