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 .
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 .
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
- 1 but not a factor of
- 1 for
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
= 1 4- X +
from which the recursion