Let
be a prime and
be a nonzero integer such that
does not divide
.
It follows from Fermat's little Theorem that the inverse
of
can be computed by

(6) 
 (1)
 Explain why this leads to an algorithm
requiring
word operations.
 (2)
 Is this better than the modular inversion
via Euclide's Algorithm?
Answer 2
Answer 3
Marc Moreno Maza
20080131