Section 2.6 Fermat's little theorem and computing inverses
Exponents in \(\F_p\ad\) have several useful and noteworthy properties. First, we have Fermat's little theorem, which essentially states that multiplying some element \(g\) in \(\F_p\ad\) by itself \(p\) times will always return to \(g\text{.}\)
Theorem 2.6.1. (Fermat's little theorem).
\(p\)\(a\)\(p \nmid a\text{,}\)Proof.
Fermat's little theorem gives us the ability to perform a relatively fast computation of inverses with the help of the fast powering algorithm.
Algorithm 2.6.2. Fast inverse mod \(p\).
\(a \in \F_p\ad\text{.}\)- Since \(a\) then must be smaller than \(p\text{,}\) \(p \nmid a\text{,}\) and so \(a^{p-1} = 1\) in \(\F_p\ad\text{.}\)
- But then \(a^{p-2} \equiv a\inv\text{.}\)
- Apply the fast powering algorithm to compute \(a^{p-2}\text{.}\) The result is \(a\inv\text{.}\)
Our final observation to close out this first unit of the course is to note that it is possible for an element to have a power \(c\) smaller than \(p - 1\) such that \(a^c = 1\) in \(\F_p\ad\text{.}\)
Definition 2.6.3.
The order of \(a\) in \(\F_p\ad\) is the smallest positive integer \(k\) so that \(a^k = 1\text{.}\)The following proposition follows directly from Fermat's little theorem (you should try to prove it!)
Proposition 2.6.4.
\(p\)\(a\)\(F_p\ad\text{.}\)\(a^k = 1\)\(\F_p\ad\text{.}\)\(k \mid (p-1)\text{.}\)Elements with order \(p - 1\) in \(F_p\ad\) are special, and of fundamental importance in cryptography.
Theorem 2.6.5. (Primitive root theorem).
\(p\)\(g \in \F_p\ad\)\(F_p\ad\text{.}\)For sufficiently large \(p\text{,}\) \(F_p\ad\) has lots of generators. (In fact equal to the totient function of \(p-1\text{.}\)) Be careful thinking about successive powers of \(g\text{:}\) while the symbols have increasing exponents, the numbers themselves will not in general be increasing, as they are subject to the mixing effect of repeated multiplication mod \(p\text{.}\)
