A.M. TURING AWARD WINNERS BY...

December 31, 1945 in San Francisco, California

BA, Mathematics (University of California, Berkley, 1968); PhD, Computer Science (University of California, Berkley, 1976).

Massachusetts Institute of Technology, Department of Mathematics (1979-1980 Associate Professor, 1977-1979 Assistant Professor); University of Southern California (1980 Associate Professor, 1983 Professor, 1985 Henry Salvatori Professor).

ACM Paris Kanellakis Theory and Practice Award (1996); IEEE Kobayashi Award for Computers and Communications (2000-joint with Rivest and Shamir); Distinguished Professor title University of Southern California (2000); ACM Turing Award (2002); Fellow of the American Academy of Arts and Sciences (2006); member of the National Academy of Engineering (1996) and the National Academy of Sciences.

United States – 2002

CITATION

Together with Ronald Rivest and Adi Shamir, for their ingenious contribution to making public-key cryptography useful in practice.

*Professor Len Adleman had just finished a personal anecdote about the development of the RSA public-key cryptosystem and DNA computing. The roomful of University of Southern California Computer Science students took advantage of the casual atmosphere to pick the brain of one of the department’s most revered faculty members.*

*A student asked, "Given your past work, what is your current research project and objective?"*

*Len paused, "I am working on a new approach to Complex Analysis called Strata. I want to add a brick—even a small brick—to the wall of Mathematics."*

*"Isn't RSA already a brick in that wall?" the student continued.*

*Len reflected, "It is not close enough to the foundation where the bricks of Gauss, Riemann, and Euler lay."*

**Leonard Max Adleman was born December 31, 1945 in San Francisco, California, to a bank teller and an appliance salesman.** Admitted to the University of California in Berkeley with the intention of becoming a chemist, he finally graduated with a BS in Mathematics in 1968. After a brief stint as a computer programmer, he returned to UC Berkeley. His concurrent interests in Mathematics and Computer Science ultimately led him to his Ph.D. thesis in 1976, *Number-Theoretic Aspects of Computational Complexity*, under the inspiring guidance of Manuel Blum, the recipient of the 1995 Turing Award.

Len quickly secured positions as an Assistant, then Associate, Professor of Mathematics at the Massachusetts Institute of Technology. His collaboration with fellow Turing Awardees Ron Rivest and Adi Shamir led to the development of the RSA public-key cryptosystem and the 1978 publication of their seminal paper, "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems” [1]. RSA, an acronym for Rivest, Shamir and Adleman, uses algorithmic number theory to provide an efficient realization of a public-key cryptosystem, a concept first envisioned theoretically by Whitfield Diffie, Martin Hellman and Ralph Merkle. RSA is now the most widely used encryption method, with applications throughout the Internet to secure on-line transactions. It has also inspired breakthrough work in both theoretical computer science and mathematics.

Algorithmic number theory, and in particular the problem of testing for prime numbers, has been a longtime research focus of Adleman. With Carl Pomerance and Robert Rumely, he developed an "almost" polynomial time deterministic primality testing algorithm. The paper [2] describing this Adleman-Pomerance-Rumely primality test appears to be the first paper published in the prestigious journal *Annals of Mathematics* on a topic in theoretical computer science.

Drawn to beautiful Southern California, Len joined the faculty at the University of Southern California (USC) in 1980, where he is now the Henry Salvatori Professor of Computer Science and Professor of Molecular Biology. In 1987, he and his USC colleague Ming-Deh Huang described the first “Las Vegas” randomized algorithm for primality testing in a landmark paper titled "Recognizing Primes in Random Polynomial Time." [3] This result was the last major theoretical breakthrough in a long line of work before the current high point in primality testing, "PRIMES is in P" by Manindra Agrawal, Neeraj Kayal, and Nitin Saxena in 2002.

Len also worked on Fermat's Last Theorem, and in 1986, with colleagues Roger Heath-Brown and Etienne Fouvry, proved that the first case of the theorem holds for infinitely many primes [5] . This was a respectable result at the time, but became a footnote following Andrew Wiles famous proof of Fermat’s Last Theorem in 1995.

Len is also associated with the creation of an early computer virus, demonstrated in 1983 by his student Fred Cohen, who credited Len for coining the term "computer virus" to describe the self-replicating programs. In the 1980's his research took an interdisciplinary turn, from computer viruses to biological ones. With David Wofsy of University of California at San Francisco, he developed a theory of CD4-cell depletion in Acquired Immune Deficiency Syndrome (AIDS) as a homeostatic mechanism failure, and published several papers on the topic.

His professional interest in biology increased, and was further inspired by James Watson's book *The Molecular Biology of the Gene*. In a moment of clarity, he noticed the resemblance between the way the protein polymerase produces complementary strands of DNA, and the mechanism of the Turing machine. Len saw the biochemical processes of the cell as computation. Like a Turing machine that runs along a tape processing symbolic information, polymerase runs along a strand of DNA processing chemical information.

Great scientific breakthroughs sometimes arise from the realization that two seemingly unrelated fields are, in fact, related. In this regard, Len proved to be more than just a brilliant theoretician. By encoding a small instance of the NP-complete Hamiltonian Path problem in strands of DNA and then experimentally computing its solution, Len created what is probably the first computational device at a molecular scale. For this work [4] Len has been widely credited as the "Father of DNA Computing."

More recently, Len has returned to what he sees as the most beautiful of endeavors: mathematics. Along with students, he investigated analogies between chemistry and mathematics, and developed event systems as a mathematical version of the law of mass action~~.~~ in chemistry. This led to further study in complex analysis, where he and his students are currently developing a theory of "Strata" to describe multi-valued analytic functions.

Len Adleman is a unique and talented interdisciplinary scholar. His accomplishments in multiple fields have been driven by remarkable insight, curiosity, and persistence. Len is an inspiring teacher from whom both authors of this essay had the good fortune to take multiple courses.

He is also an intriguing person when away from the academy. Unable to resist the allure of Hollywood, he served as a mathematical and cryptography consultant for the film *Sneakers.* He enjoys discussing *Memes*, the theory of information evolution developed by Richard Dawkins. He converses regularly about history, art, music and culture, and is a mesmerizing storyteller. Perhaps in preparation for lifting his brick into the wall of mathematics, he has whipped himself into physical shape as an amateur boxer who has been in the ring with the likes of ten-time world champion James Toney.

Authors: Joseph Bebel and Shang-Hua Teng