Mathematics for Computer Science

8.6. Arithmetic with a Prime Modulus 207

For example, supposepD 5 andkD 3. Then the sequence:

rem„ ..1ƒ‚
3/;5/...

D 3

; rem„ ..2ƒ‚
3/;5/...

D 1

; rem„ ..3ƒ‚
3/;5/...

D 4

; rem„ ..4ƒ‚
3/;5/...

D 2

is a permutation of 1, 2, 3, 4. As long as the Nazis don’t know the secret keyk,
they don’t know how the set of possible messages are permuted by the process of
encryption and thus they can’t read encoded messages.

8.6.3 Fermat’s Little Theorem

An alternative approach to finding the inverse of the secret keykin Turing’s code
is to rely on Fermat’s Little Theorem, which is much easier than his famous Last
Theorem.

Theorem 8.6.4(Fermat’s Little Theorem). Supposepis a prime andkis not a
multiple ofp. Then:
kp^1 1 .modp/

Proof. We reason as follows:

.p1/ŠWWD 1 
 2 


.p1/

Drem.k;p/
rem.2k;p/


rem..p1/k;p/ (by Cor 8.6.3)

k
2k


.p1/k .modp/ (by Cor 8.5.3)

.p1/Š
kp^1 .modp/ (rearranging terms)

Now.p1/Šis not a multiple ofpbecause the prime factorizations of1;2;:::,
.p1/contain only primes smaller thanp. So by Lemma 8.6.2, we can cancel
.p1/Šfrom the first and last expressions, which proves the claim. 

Here is how we can find inverses using Fermat’s Theorem. Supposepis a prime
andkis not a multiple ofp. Then, by Fermat’s Theorem, we know that:

kp^2 
k1 .modp/

Therefore,kp^2 must be a multiplicative inverse ofk. For example, suppose that
we want the multiplicative inverse of 6 modulo 17. Then we need to compute
rem.6^15 ;17/, which we can do using the fast exponentiation procedure of Sec-
tion 6.2.5, with all the arithemetic done modulo 17. Namely,

.6;1;15/!.36;6;7/.2;6;7/!.4;12;3/

!.16;14;1/!.256;224;0/.1;3;0/: