10 M. R. SCHROEDER

fraction of all possible permutations. Not counting cyclical shifts and

reflections, there are (p - 2) !/2 "inequivalent" permutations. For p = 17,

we have thus 653 837 184 000 such permutations, of which ((( 16) = 8 (about

one in

1011)

have the flat Fourier property. Questions: are there other

permutations that, when used instead of

gn

in (5), have this property?

5. Forbidding property of the Fermat primes

Since Gauss's great discovery of 30 March 1796 concerning the

factorization of

xp

- 1, where p is a Fermat prime,

p =

22n

+ 1 ,

these primes have enjoyed great esteem, spreading from the factoring factories

of the experts to the sweatshops of the amateur. The

4

geometrical"

constructions of regular p-gons rests on the fact that p - 1 has only one

prime factor, namely 2. Now, in the context of wave diffraction, this same

property - instead of permitting a particular construction -forbids a desirable

application, namely the construction of two (or higher) dimensional phase

arrays with the flat Fourier property mentioned above.

The two-dimensional generalization of the periodic sequence (5) is the

periodic array rkt with

k =

(n)modK

and € = (n)

m o d L

,

where K and L (in best Chinese remainder fashion) are two coprime factors of

p - 1. Thus there are no n-dimensional (n 1) phase gratings based on the

known Fermat primes 3, 5, 17, 257, 65 537. (The smallest prime for a three-

dimensional array is 31, having a 2 • 3 • 5 "unit cell.'*)

6. Euler totients and cryptography

One of the most spectacular applications of number theory in recent times

is public-key cryptography in which each potential recipient of a secret

message publishes his encryption key, thereby avoiding the (often substantial)

problems of secure secret-key distribution. But how can a key be public and

yet produce secret messages? The answer is based on Euler's totient function

|(r) and the role it plays in inverting modular exponentiation. The public key

consists of a modulus r and an exponent s, coprime to |(r). The message is

represented by an integer M, 1 M r, and the encrypted message E is