You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
Copy file name to clipboardExpand all lines: src/algebra/module-inverse.md
+16-15Lines changed: 16 additions & 15 deletions
Original file line number
Diff line number
Diff line change
@@ -77,36 +77,37 @@ From these results, we can easily find the modular inverse using the [binary exp
77
77
78
78
Even though this method is easier to understand than the method described in previous paragraph, in the case when $m$ is not a prime number, we need to calculate Euler phi function, which involves factorization of $m$, which might be very hard. If the prime factorization of $m$ is known, then the complexity of this method is $O(\log m)$.
79
79
80
-
## Finding the modular inverse for prime mods using Euclidean Division
## Finding the modular inverse for prime moduli using Euclidean Division
81
82
82
-
Given that $p > i$ (or we can modulo to make it smaller in 1 step), according to [Euclidean Division](https://en.wikipedia.org/wiki/Euclidean_division)
83
+
Given a prime modulus $m > a$ (or we can apply modulo to make it smaller in 1 step), according to [Euclidean Division](https://en.wikipedia.org/wiki/Euclidean_division)
83
84
84
-
$$p = k \cdot i + r$$
85
+
$$m = k \cdot a + r$$
85
86
86
-
where $k = \left\lfloor \frac{p}{i} \right\rfloor$ and $r = p \bmod i$, then
87
+
where $k = \left\lfloor \frac{m}{a} \right\rfloor$ and $r = m \bmod a$, then
87
88
88
89
$$
89
90
\begin{align*}
90
-
& \implies & 0 & \equiv k \cdot i + r & \mod p \\
91
-
& \iff & r & \equiv -k \cdot i & \mod p \\
92
-
& \iff & r \cdot i^{-1} & \equiv -k & \mod p \\
93
-
& \iff & i^{-1} & \equiv -k \cdot r^{-1} & \mod p
91
+
& \implies & 0 & \equiv k \cdot a + r & \mod m \\
92
+
& \iff & r & \equiv -k \cdot a & \mod m \\
93
+
& \iff & r \cdot a^{-1} & \equiv -k & \mod m \\
94
+
& \iff & a^{-1} & \equiv -k \cdot r^{-1} & \mod m
94
95
\end{align*}
95
96
$$
96
97
97
-
Note that this reasoning does not hold if $p$ is not prime, since the existence of $i^{-1}$ does not imply the existence of $r^{-1}$
98
+
Note that this reasoning does not hold if $m$ is not prime, since the existence of $a^{-1}$ does not imply the existence of $r^{-1}$
98
99
in the general case. To see this, lets try to calculate $5^{-1}$ modulo $12$ with the above formula. We would like to arrive at $5$,
99
100
since $5 \cdot 5 \equiv 1 \bmod 12$. However, $12 = 2 \cdot 5 + 2$, and we have $k=2$ and $r=2$, with $2$ being not invertible modulo $12$.
100
101
101
-
If the modulus is prime however, all $i$ with $0 < i < p$
CAA9
are invertible modulo $p$, and we can have the following recursive function (in C++) for computing the modular inverse for number $i$ with respect to $p$
102
+
If the modulus is prime however, all $a$ with $0 < a < m$ are invertible modulo $m$, and we can have the following recursive function (in C++) for computing the modular inverse for number $a$ with respect to $m$
102
103
103
104
```{.cpp file=modular_inverse_euclidean_division}
104
-
intinv(int i) {
105
-
return i <= 1 ? i : m - (long long)(m/i) * inv(m % i) % m;
105
+
intinv(int a) {
106
+
return a <= 1 ? a : m - (long long)(m/a) * inv(m % a) % m;
106
107
}
107
108
```
108
109
109
-
The exact time complexity of the this recursion is not known. It's is somewhere between $O(\frac{\log m}{\log\log m})$ and $O(n^{\frac{1}{3} - \frac{2}{177} + \epsilon})$.
110
+
The exact time complexity of the this recursion is not known. It's is somewhere between $O(\frac{\log m}{\log\log m})$ and $O(m^{\frac{1}{3} - \frac{2}{177} + \epsilon})$.
110
111
See [On the length of Pierce expansions](https://arxiv.org/abs/2211.08374).
111
112
In practice this implementation is fast, e.g. for the modulus $10^9 + 7$ it will always finish in less than 50 iterations.
112
113
@@ -115,8 +116,8 @@ Applying this formula, we can also precompute the modular inverse for every numb
0 commit comments