Appendix D: Technical and Advanced Details - Codes: The Guide to Secrecy from Ancient to Modern Times - page 530

To find these b i , we proceed as follows. First, set β 0 = β = α e , and observe that

a − 1

b k q k − i − 1

( p − 1) ≡ ( p − 1) b i /q (mod p − 1) . (D.1)

k = i

1. Calculate b 0 . By (D.1),

β ( p − 1) /q
0

α ( p − 1) b 0 /q (mod p ) , ≡ (D.2)

using Fermat's Little Theorem (see Corollary A.2 on page 479). Thus, we
compute α ( p − 1) k/q (mod p ) until (D.2) occurs, in which case k is b 0 .

2. Calculate b i for i =1 , 2 ,...,a − 1. First, recursively define

1
k =0

i −

b k q k

β i = βα −

.

By (D.1),

α ( p − 1) a − 1 β ( p − 1) /q i +1

i

k = i b k q k − i − 1

α ( p − 1) b i /q (mod p ) , ≡ ≡ (D.3)

so we compute α ( p − 1) k/q modulo p for nonzero k

1 until the left and
right sides of (D.3) are congruent modulo p , in which case k is b i .

≤ a −

A small example is in order. This is, of course, not realistic in terms of the
degree of diGculty, but for pedagogical purposes, it will suGce, and we will do
this often for the same reasons throughout.

F 37 . Given β 0 = β =19 ,we

Example D.1 Let p =37 . Then α =2 generates

F 37 . We have

want to compute e = log 2 (19) in

1=36=2 2 3 2 = p a 1 p a 2 .

− ·

p

All congruences in the balance of this example are assumed to be modulo 37 .
For p 1 =2 :

k 0 1

α ( p − 1) k/p 1 2 18 1 ≡ 36

i 0 1

2 − 1 β i 19 19 · ≡ 28

β ( p − 1) /p i [phone]

≡ 36 ≡ 36

1

i

b i 1 1