Exercise 2.

Let $p \in {\mbox{${\mathbb{N}}$}}$ be a prime and $a \in {\mbox{${\mathbb{Z}}$}}$ be a non-zero integer such that $p$ does not divide $a$ . It follows from Fermat's little Theorem that the inverse of $a \mod{\, p}$ can be computed by

$$a^{-1} \ \equiv \ a^{p-2} \mod{\, p}$$ (6)

(1)

Explain why this leads to an algorithm requiring ${\cal O}({\log}^3_2(p))$ word operations.

(2)

Is this better than the modular inversion via Euclide's Algorithm?

Answer 2  

Answer 3