Algorithmic Algebra - A Classical Introduction to Cryptography: Applications for Communications Security - page 177

Exercise 6.8. Let G be the set of all x ∈ Z p 2 such that x ≡ 1 (mod p ) . Show that G

x − 1
p

is a multiplicative group, that L : G → Z p defined by L ( x ) = is an isomorphism,

that p + 1 is a generator of G, and that L is the logarithm in base p + 1 in L. Infer

( p 2 ) 1) . 6

that ϕ = p ( p −

Exercise 6.9. Considering the reduction modulo p as a group homomorphism on
Z p α → Z p , prove that ( p α ) 1) p α − 1 . ϕ = ( p −

Infer that if p 1 ,..., p r are distinct prime integers and if α 1 ,...,α r are nonzero

positive integers, then

r

( p α 1
1

1) p α i − 1
i

p α r )

ϕ ×···× =

( p i −

.

i = 1

6

This exercise was inspired by the Okamoto-Uchiyama cryptosystem. See Ref. [143].