Appendix G: Exercises - Codes: The Guide to Secrecy from Ancient to Modern Times - page 578

and you may use the fact that if f ( x )= x 2

F [ x ] for any field
F , then c is the sum of th e roots o f f ( x ) and d is the product of the roots.

− cx + d ∈

Note, as well, that ( x + √ x 2 − 4 a ) / 2 lies in the extension field F q 2 . Also,

Equation (G.1) is called the functional equation of D n ( x,a ) . )
4.51. A permutation polynomial on a finite field ✰ F q is a polynomial f ( x ) ∈ F q [ x ]

such that f permutes the elements of F q . In other words, f is a one-to-one
and onto mapping of F q to itself.

∈ F q , D n ( x,a ) is a permutation polynomial on

Prove that for a F q if and

only if gcd( n,q 2

1) = 1.
( Hint: Prove first that x n permutes

−

F q if and only if gcd( n,q − 1) = 1 .

Then use Exercise 4.50. )

Let k = j =1 p a j

4.52. .A

polynomial is a permutation polynomial modulo k , or permutation poly-
nomial of

be the canonical prime factorization of k ∈ N

j

Z Z Z Z

. With
somewhat more di G culty than the above, it can be shown that D n ( x,a )is
a permutation polynomial modulo k if and only if gcd( n,ν ( k )) = 1, where
ν ( k ) = lcm j ( p a j − 1
j

/k ,if f is a one-to-one and onto function of /k

( p j −

1)) .

(Exercise 4.51 is provided as an indication of that process for the simpler
case.) Once we have a permutation polynomial, we can form its inverse
and this provides a basis for developing a cryptosystem.
The following public-key cipher is called a Dickson cryptosystem .
Let Bob's public enciphering exponent be e B with gcd( e B ,ν ( k )) =

1. Alice enciphers a message m to Bob via computation of

∈ Z /k Z

≡

D e B ( m,a ) c (mod k )

where a =1or a = /k/Z . To decrypt, Bob uses his private key

d B obtained via the linear congruence,
e B d B ≡

− 1in Z

1 (mod ν ( k )) ,

and computes D d B ( c,a ) (mod k ). Prove that the latter actually recovers
m . Moreover, show that if k = pq is an RSA modulus, and
µ ( k )=( p 2 1)( q 2 − − 1)

is used in place of ν ( k ), then this is similar to the RSA cipher, and for
a =0it is the RSA cipher.

4.53. With reference to Exercises 4.50-4.52, Dickson polynomials may also be
used as a basis for digital signatures. Suppose that Alice wishes to sign a
message m , and k is given to be a product of large primes. If ( e A ,d A )is
Alice's public/private key pair, assume she computes

D d A ( m,a ) ≡ s (mod k ) ,

and sends the signature s to Bob.