# Notes - Computer Security MT24, Number theory

> Source: https://ollybritton.com/notes/uni/part-b/mt24/computer-security/notes/number-theory/ · Updated: 2025-05-25 · Tags: uni, notes

- [Course - Computer Security MT24](https://ollybritton.com/notes/uni/part-b/mt24/computer-security/)
	- [Notes - Computer Secuirty MT24,  Asymmetric key ciphers](https://ollybritton.com/notes/uni/part-b/mt24/computer-security/notes/asymmetric-key-ciphers/)
	- [Notes - Groups HT23, HCF and LCM](https://ollybritton.com/notes/uni/prelims/ht23/groups/notes/hcf-and-lcm/)
	- [Notes - Groups HT23, Modular arithmetic](https://ollybritton.com/notes/uni/prelims/ht23/groups/notes/modular-arithmetic/)

### 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, with and without ignoring the complexity of the underlying arithmetic operations?::

There are
$$
O(\log \min(m, n))
$$
steps. Assuming $m, n$ are each $O(b)$ bits, each step requires an $O(b^2)$ arithmetic operation, for a total of $O(b^3)$.

Can you give a equivalent condition to an integer $a$ having a multiplicative inverse mod $n$?::

$$
\text{gcd}(a, n) = 1
$$

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.

---
Olly Britton — https://ollybritton.com. Machine-readable index: https://ollybritton.com/llms.txt