Notes - Computer Security MT24, Number theory
Flashcards
Euclid’s algorithm computes the $\gcd$ of two numbers $m$ and $n$. What does it also compute along the way?
The numbers $x$ and $y$ giving the Bezout identity
\[g = mx + ny\]Suppose Euclid’s algorithm is used to compute $\gcd(m, n)$. What is the time complexity?
Can you give a equivalent condition to an integer $a$ having a multiplicative inverse mod $n$?
How can you quickly find the multiplicative inverse of an integer $a$ mod $n$?
Since $\gcd(a, n) = 1$, you can use Euclid’s algorithm to compute $x$ and $y$ such that
\[ax + ny = 1\]and hence $a^{-1} \equiv x \pmod n$.
@Prove that for a prime $p$,
\[a^{p-1} \equiv \begin{cases}
0 \pmod p &\text{if } p \mid a \\\\
1 \pmod p &\text{otherwise}
\end{cases}\]
Case $p \mid a$: Then $p \mid a^{p-1}$, and so $a^{p-1} \equiv 0 \pmod p$.
Case $p \not\mid a$: Consider the sets
- $A = \{1, 2, \ldots, p-1\}$
- $B = \{a \cdot 1 \pmod p, a \cdot 2 \pmod p, \ldots, a \cdot (p-1) \pmod p\}$
No members of $b$ can be zero since then either $p \mid a$ or $p \mid x$ for some $x$ smaller than $p$, which doesn’t happen. And likewise, all members of $B$ must be different since if $a \cdot x \equiv a \cdot y \pmod p$, then $p \mid a \cdot (x - y)$ means that $p \mid a$ or $p \mid x- y$, which doesn’t happen.
Hence $A$ and $B$ are the same set. Then multiplying the elements of each set together separately yields
\[\begin{aligned} \prod^{p-1} _ {i=1} i &\equiv \prod^{p-1} _ {i = 1} (a\cdot i) \pmod p\\\\ &\equiv a^{p-1} \prod^{p-1} _ {i = 1} i \pmod p \end{aligned}\]Since $\prod^{p-1} _ {i = 1} i$ is coprime to $a$, it must have a multiplicative inverse and so we can divide through by $\prod^{p-1} _ {i=1} i$ to yield
\[a^{p-1} \equiv 1 \pmod p\]as required.