12 M. R. SCHROEDER

Not so long ago, the most efficient factoring algorithms on a very fast

computer were estimated to take trillions of years. But algorithms get more

efficient by the month and computers become faster and faster every year, and

there is no guarantee that one day a so-called "polynomial-time" algorithm

will not emerge that will allow fast factoring of even 1000-digit numbers.

Few mathematicians believe that a true polynomial-time algorithm is just

around the corner, but there also seems to be little prospect of proving that

this will never occur. This is the Achilles heel of public key cryptography.

7. Sequences fromfinitefields

Certain periodic sequences with elements from the finite (Galois) field

GF(p), formed with the help of irreducible polynomials over GF(pm), have

unique and much sought-after correlation and Fourier transform properties [7].

These Galois sequences, as I have called them, have found ingenious

applications in error-correcting codes (compact discs and picture

transmissions from inter-planetary satellites) and in precision measurements

from physiology to general relativity. Other applications are in radar and

sonar camouflage, because Galois sequences, like quadratic residues (see

above), permit the design of surfaces that scatter incoming waves very

broadly, thereby making the reflected energy "invisible" or "inaudible." A

similar application occurs in work with coherent light, where a "roughening"

of wavefronts (phase randomization) is often desired (for example, to avoid

"speckles" in holograms). Light diffusors whose design is based on Galois

arrays are in a sense the ultimate in frosted (milk) glass. Finally, Galois

sequences allow the design of loudspeaker and antenna arrays with very broad

radiation characteristics [2].

8. Error correction codes from Galois fields

Galois sequences, with periods n = pm - 1, are constructed with the

help of an irreducible polynomial g(x) of degree m with coefficients from

GF(p), such that g(x) is a factor of

xn

- 1 but not a factor of

xr

- 1 for

r n.

Binary Galois sequences (p = 2) with elements 0 and 1 (or, in certain

other applications, 1 and -1) are the most important practical case. For

p = 2 and m = 4, an irreducible polynomial with the stated property is

g(x)

= 1 4- X +

X4

,

from which the recursion