Consider the space $\mathbb{Z}_n$, where $n$ is a reasonably large prime, say, for example, 53. How can I quickly and efficiently write out the multiplicative inverses for each element of $\mathbb{Z}_{53}$? I don't want to use the Extended Euclidean algorithm 26 times (for the 52 total terms in this set). Is there a way to do this that's not just "brute force", so to speak?
To be clear, I want to do this by hand, not using a computer.
On
EDIT: I missed that you wanted every element in $\mathbb{Z}_p$; I'm sure there's a faster way than this for that application.
I will expand on my comment; Euler's theorem states that $$ a^{\phi(m)} \equiv 1 \mod m $$ where a is coprime to m and $\phi$ is the Euler totient function. Suppose m is the prime you speak of, then notice that $\phi(m) = m-1$. So then we find that: $$ a^{m-1} \equiv 1 \mod{m} \implies a^{m-2} \equiv a^{-1} \mod{m} $$ Therefore, if we take $m = 53$, as in your example, computing the multiplicative inverse is as simple as computing $a^{51}$, which can vary from being very easy (say if $a = 2$), to very bad (say if $a = 51$).
On
Here's an idea that might not be an iron-clad algorithm, but for numbers that you'd be willing to try by hand might be useful in practice.
Note that $53+1=54$ has several factorizations: $54=2\cdot27=3\cdot18=6\cdot9$. Since $54\equiv1\pmod{53}$, this instantly tells us that $2^{-1}\equiv27\pmod{53}$, $3^{-1}\equiv18\pmod{53}$, and $6^{-1}\equiv9\pmod{53}$. Note that the last of these congruences follows from the first two, since $2\cdot3=6$ and $27\cdot18=504\equiv9\pmod{53}$. And indeed we can use $2^{-1}\equiv27\pmod{53}$ and $3^{-1}\equiv18\pmod{53}$ to find $4^{-1}$, $8^{-1}$, $9^{-1}$ (which we already have), $12^{-1}$, $16^{-1}$, and so on.
Along the way we might stumble across more elements with small inverses, such as $32^{-1}\equiv5\pmod{53}$. Then we know that $5^{-1}\equiv32\pmod{53}$ as well, which allows us to calculate things like $10^{-1}$, $15^{-1}$, $20^{-1}$, $25^{-1}$, and so on.
We can also look at other multiples of $53$. For example, $160=3\cdot53+1\equiv1\pmod{53}$, and therefore any factorization of $160$ gives us an inverse pair as well. For instance, $8\cdot20=160$, and therefore $8^{-1}\equiv20\pmod{53}$ and vice versa. Similarly, $7\cdot31=213=4\cdot53+1\equiv1\pmod{53}$, and therefore $7^{-1}\equiv31\pmod{53}$.
On
Find a primitive root (test the small primes) and enumerate its powers. The inverses are the pairs of exponents totalling $p-1$.
For example, for $p=53$, $2$ is a primitive root, so the powers of $2\bmod 53$ visit all residue classes and $2^{k}$ and $2^{52-k}$ are inverses.
On
Expanding on my comment, it isn't too tedious to write out the multiplication table. E.g. let $n = 5$. Then the multiplication table is $$ \begin{array}{c|cccc} &1&2&3&4\\\hline 1&1&2&3&4\\ 2&2&4&1&3\\ 3&3&1&4&2\\ 4&4&3&2&1 \end{array} $$ To calculate the $i$-th row, you just start with $i$, and then add $i$ to the previous element in the row and subtract $5$ if the result exceeds $5$. Then you can read off the inverse of $i$ by looking for the $j$ that gives you $ij=1$. If you really only care about the inverses, you can stop calculating along each row once you get to the entry $1$.
On
Here's a well-known algorithm in competition programming for listing all multiplicative inverses mod p in linear time complexity (for a computer assuming fixed word size, that is all operations like division and mod on):
Let $\%$ be the modulo operation and let $a[1:p]$ be an array holding the multiplicative inverses. Then $a[1] = 1$, and for $i = 2, \dots, p-1$,
$$a[i] = p - (\lfloor p/i \rfloor \times a[p \% i]) \% p $$
Proof: $p\%i = p - \lfloor p/i \rfloor \times i = - \lfloor p/i \rfloor \times i \pmod p $, then divide by $i \times (p\%i)$ to get $a[i] = - \lfloor p/i \rfloor \times a[p \% i] \pmod p$.
Source: https://cp-algorithms.com/algebra/module-inverse.html#toc-tgt-3, http://e-maxx.ru/algo/reverse_element (in Russian)
Let $[a]$ be a residue class modulo the prime $p$ and let $[b] = [a]^{-1}$ be its multiplicative inverse. You can, for instance, find this inverse using the extended Euclidean algorithm. Then, \begin{align*} [a^2]^{-1} &= [b^2] \text{,} \\ [a^3]^{-1} &= [b^3] \text{,} \\ &\vdots \end{align*} So use the slow method to get one result, then go through successive powers to fill in more entries in your table of inverses. At some point, the powers cycle back, perhaps not filling in the entire table. Now pick one of the unfilled entries and start this process again. When you run out of empty entries, hooray!, you're done.
One interesting thing that can happen is that you can in one step work out the inverses of the powers of $[c^2]$. At a later step, you find you are working out the powers of $[c]$ because every even power is already in your table and every (or possibly most) odd powers are new entries. (Some entries may already be filled in as members of other cycles.)
As an example, modulo $17$, $[2]^{-1} \cong [9]$, so \begin{align*} [2^2]^{-1} \cong [4]^{-1} &\cong [9^2] \cong [13] \\ [2^3]^{-1} \cong [8]^{-1} &\cong [9\cdot 13] \cong [15] \\ [2^4]^{-1} \cong [16]^{-1} &\cong [9\cdot 15] \cong [16] \\ [2^5]^{-1} \cong [15]^{-1} &\cong [9 \cdot 16] \cong [8] \\ [2^6]^{-1} \cong [13]^{-1} &\cong [9 \cdot 8] \cong [4] \\ [2^7]^{-1} \cong [9]^{-1} &\cong [9 \cdot 4] \cong [2] \\ [2^8]^{-1} \cong [1]^{-1} &\cong [9 \cdot 2] \cong [1] \\ [2^9]^{-1} \cong [2]^{-1} &\text{and we've cycled.} \end{align*} Note that $2^8 \cong 1$ was a slightly earlier signal that we were about to cycle.
Notice we got half of the entries for the table. Now try it with $[3]$ and (I think) get the other half (or go around again with another new starting point).
There is a theoretical idea floating around in the above: primitive roots. Pulling a primitive root out of thin air is hard, so here, we just hope that we either picked a primitive root or picked a small power of a primitive root so we can fill in many table entries. Even if you don't, you get some table entries.
We could probably estimate the expected number of cycles to complete the table, which probably has a leading term of the approximate size $\frac{\varphi(p)}{\varphi(\varphi(p))}$, where $\varphi$ is the Euler totient function, to capture the number of residue classes that are a small power of one of the primitive roots modulo $p$.