You are here

American Mathematical Monthly -February 2004

February 2004

Polynomials in the Nation’s Service: Using Algebra to Design the Advanced Encryption Standard
by Susan Landau
susan.landau@sun.com
Cryptography, the science of transforming communications so that only the intended recipient can understand them, should be a mathematician’s playground. Certain aspects of cryptography are indeed quite mathematical. Both Diffie-Hellman key exchange and the RSA encryption algorithm (http://www.rsasecurity.com/rsalabs/faq3-1.html) rely on elementary number theory, while elliptic curves power more advanced public-key systems.

Such public-key cryptography has captured mathematicians’ attention, but this type of cryptography is in fact far too slow for most needs and is typically used only for key exchange. Private- or symmetric-key cryptosystems are the real workhorses of the encryption world. Until recently most private-key cryptosystems lacked an overarching mathematical theory. That changed in 2001, with the government’s choice of Rijndael as the Advanced Encryption Standard (http://www.esat.kuleuven.ac.be/~rijmen/rijndael).

Rijndael variously uses x-1, x7 +x6 + x2 + x, x7 + x6 + x5 + x4 + 1, x4 + 1, 3x3 + x2 + x + 2, and x8 +1 to provide cryptographic security. (Of course, x-1 is not strictly a polynomial, but in the finite field GF(28) x-1 = x254 and so we will consider it one.) Polynomials provide Rijndael’s structure and yield proofs of security. This paper demonstrates how polynomials came to play a critical role in what may become the most widely used cryptographic algorithm of the new century.

 

Isoperimetric and Isoparametric Problems
by Tom M. Apostol and Mamikon A. Mnatsakanian
Traditional isoperimetric problems ask for the region of maximal area among all plane regions having equal perimeters. This paper deals instead with plane regions that have equal perimeters and equal areas. We call such regions isoparametric and introduce the isoparametric problem: find incongruent isoparametric regions of specified shapes. Surprisingly, incredibly many solutions exist, and the problem opens a broad new field of research. Simple examples include a square and two different circular sectors, a rectangle and two different isosceles triangles. The general problem is analyzed with the help of the contour ratio, a replacement of the classical isoperimetric quotient. Two contours can be scaled to become isoparametric if and only if they have the same contour ratio. The problem becomes more interesting and more difficult when it is extended to rings, regions between two similar simple closed curves. General conditions, involving certain constraints, are formulated for two rings to be isoparametric. For example, although a square and a circular disk are never isoparametric, a square ring and a circular ring can be isoparametric, unless the hole in the circular ring is too small to make a significant contribution to the total perimeter and area.

 

Orbits of Orbs: Sphere Packing Meets Penrose Tilings
by Charles Radin
radin@math.utexas.edu
The venerable study of optimum density problems, such as arranging spheres as efficiently as possible, has been revitalized by investigations on aperiodicity, a subject best known through the Penrose kite & dart tilings. The result is a generalization of the basic notion of geometric symmetry for patterns in space.

 

Notes

When are There Infinitely Many Irreducible Elements in a Principal Ideal Domain?
by Fabrizio Zanello
fabrizio@mast.queensu.ca

Solving Inequalities and Proving Farkas’s Lemma Made Easy
by David Avis and Bohdan Kaluzny
avis@cs.mcgill.ca, beezer@cs.mcgill.ca

Cauchy’s Interlace Theorem for Eigenvalues of Hermitian Matrices
by Suk-Geun Hwang
sghwang@knu.ac.kr

New Designs for the Descartes Rule of Signs
by Michael Schmitt
mschmitt@lmi.ruhr-uni-bochum.de

Problems and Solutions

Reviews

Inequalities from Complex Analysis
by John P. D’Angelo
Reviewed by Steven R. Bell
bell@math.purdue.edu

A Course in Convexity
by Alexander Barvinok
Reviewed by Margaret M. Bayer
bayer@math.ukans.edu