Jan. 2000

 

Vitae

Leonard M. Adleman

Henry Salvatori Professor of
Computer Science
And Professor of Molecular Biology
University of Southern California
Los Angeles, California 90089-0781
 
 

 Personal:

 
  Born December 31, 1945 (San Francisco, Ca.). Married, 3 Children.

  Education:
  Ph.D.
  Computer Science, University of California, Berkeley, 1976.
  Thesis: "Number Theoretic Aspects of Computational Complexity."
  Advisor: Manuel Blum.
  B.S.
  Mathematics, University of California, Berkeley, 1968.

 
  Professional Experience:
 
  1980-Present University of Southern California
  1985- Henry Salvatori Professor
  1983- Professor
  1980- Associate Professor (with tenure)

 
  1976-1980 Massachusetts Institute of Technology
  Department of Mathematics
  1979- Associate Professor
 1977- Assistant Professor
  1976- Instructor

 
 Professional Interests:
 
 Algorithms
 Computational Complexity
 Computer Viruses
 Cryptography
 DNA Computing
 Immunology
 Molecular Biology
 Number Theory
 Quantum Computing

 
 Current Grants:

 
 NSF
 Computational Complexity and its Relationship to Number Theory
 9/15/94-8/31/00 (NO COST EXTENSION)
 Total Award: $1,317,629
 CCR-9403662

 
 ONR/DARPA
 Computational Aspects of Molecular Science
 05/01/98-04/30/01
 Total Award: $1,602,380
 N00014-98-1-0664

 
 JPL/NASA
 Molecular Computation
 04/10/98-12/31/00
 Total Award: $492,327
 961352

 
 DARPA
 High Speed Cell Analysis, BioSpice, Cellular Logic Devices ,and Exquisite Detection: Towards Interactive Biology
 07/01/99-12/31/01
 Total Award (for USC subcontract): $850,000 (approximately)

 
 Patents:
 
 "Cryptographic Communication System and Method" (with Rivest and
 Shamir - assigned to MIT)

 
 "Molecular Computation", pending

 
 Awards and Honors:

 
 2000- IEEE Kobayashi Award for Computers and Communications (Joint with Rivest and Shamir).

 
 2000- Distinguished Professor title University of Southern California

 
 1997- RSA Chair created at MIT in honor of inventors of RSA Cryptosystem. (First holder: Professor Shafi Goildwasser - Dept. of Computer Science, MIT)

 
 1996- ACM Paris Kanallakis Award for Theory and Practice. For work on Public-Key-Cryptography (joint with Diffie, Hellman, Merkle, Rivest and Shamir).+

 
 1996- Elected to the National Academy of Engineering.

 
 1995- Distinguished Alumnus Award
 Department of Computer Science and Engineering
 University of California, Berkeley

 
 1991- Senior Research Award University of Southern California
 School of Engineering

 
 1978- Best paper award of the IEEE Group on Information Theory "A
 Method for Obtaining Digital Signatures and Public-Key
 Cryptosystems," Communications of the ACM, 21(2):120-
 126,(February) 1978. (with R. Rivest and A. Shamir).

 
 Elaborations on Selected Publications:
 
 1. "A Method for Obtaining Digital Signatures and Public-Key Cryptosystems," Communications of the ACM, 21(2):120-126,(February) 1978. (with R. Rivest and A. Shamir).

 
 This paper presents the first incarnation of a public-key cryptosystem. The principal computation used for encryption and decryption is exponentiation with respect to a composite modulus. This paper together with the papers of W. Diffie and M. Hellman ("New Directions in Cryptography," IEEE Trans. on Inf. Th.,IT-22) and R. Merkle (`Secure Communications Over Insecure Channels' Commun. ACM, vol. 17, no. 4, 294 -299) are generally regarded as the seminal papers in the field of public-key cryptography. The 'RSA' system continues to occupy a central place in both the theoretical and practical development of the field. More than 400,000,000 copies of the RSA algorithm are currently installed and it is the primary cryptosystem used for security on the internet and world wide web.

 
 2. "On Distinguishing Prime Numbers From Composite Numbers," Annals of Mathematics, 117, 173-206, 1983. (with R. S. Rumely and C. Pomerance).

 
 `The problem of distinguishing prime numbers from composites, and of resolving composite numbers into their prime factors, is one of the most important and useful in all of arithmetic.... The dignity of science seems to demand that every aid to the solution of such an elegant and celebrated problem be zealously cultivated.'
 - Karl Freidrich Gauss
 Disquisitiones Arithmetica ART. 329 (1801)
 (translation from D.E. Knuth's "The Art of Computer Programming,"
 Vol.2, second edition, Addison-Wesley, 1981, pg 398.)

 
 The problem of distinguishing prime numbers from composite numbers is ancient. Since the time of Eratosthenes' sieve it has attracted the attention of many distinguished researchers. This paper presents a 'nearly polynomial time' deterministic algorithm for the problem. More specifically, there exists a positive real c such that for sufficiently large n, the algorithm halts within log nc log(log(log(n))) steps. The next best deterministic algorithm is strictly exponential. The primary methods used in the algorithm are from algebraic number theory and class field theory (higher reciprocity laws). H. W. Lenstra, A.K. Lenstra and H. Cohen were able to simplify and implement the algorithm. Their implementation can test the primality of numbers of hundreds of digits in a few minutes.

 
 It appears that this is the first result in theoretical computer science ever published in Annals of Mathematics.

 
 3. "The First Case of Fermat's Last Theorem", Invent. Math 79:409-416, 1985. (with R.Heath-Brown).

 
 Note: This result has since been superseded by the brilliant work of A. Wiles in settling Fermat's last Theorem.

 
 'Fermat's last theorem' is, of course, the conjecture that:
 
 xn+yn=zn has no solutions in the positive integers when n > 2

 
 By 1976 enough was known that it was possible to establish by computation that the so called `first case' of Fermat's last theorem held for all primes p < 3xlO^9 (see "13 Lecture on Fermat's Last Theorem," by P. Ribenboim, Springer-Verlag, 1979).

 
 In this paper (and the companion paper "Theorem de Brun-Titchmarsh- application au theorem de Fermat" by E. Fouvry Invent. Math, 79: 383-407, 1985) the following was proved:

 
 Theorem[Adleman, Fouvry, Heath-Brown] There exist infinitely many primes for which the first case of Fermat's last theorem holds.

 
 
 4. "Primality Testing And Two Dimensional Abelian Varieties Over Finite Fields," Springer Verlag Lecture Notes In Mathematics 1512, 142 pages, 1992. (with M-D A. Huang).

 
 The existence of a random polynomial time algorithm for the set of primes is demonstrated. The techniques used are from arithmetic algebraic geometry, algebraic number theory and analytic number theory. The result complements the well known result of Solovay and Strassen ("A Fast Monte-Carlo Test For Primality," SIAM J. Comput. 6 (1977), 84-85) that there exists a random polynomial time algorithm for the set of composites.

 
 If one is willing to accept randomness in computation, then this result settles the theoretical question of the existence of a polynomial time algorithm for distinguishing prime numbers from composite numbers.

 
 5. "Molecular Computation of Solutions To Combinatorial Problem," Science, 266: 1021-1024, (Nov. 11) 1994.

 
 A small instance of the' Hamiltonian path problem' is encoded in molecules of DNA and solved in a test tube using the tools of molecular biology. This is apparently the first example of computation carried out at the molecular level and suggests the possibility of fundamental connections between biology and computer science.

 
 
 Publications:
 
 
 Leonard M. Adleman, Ming-Deh A. Huang: Function Field Sieve Method for Discrete Logarithms over Finite Fields. Information and Compuation151(1-2): 5-16 (1999)

 
 Leonard M. Adleman, Jonathan DeMarrais, Ming-Deh A. Huang: A Subexponential Algorithm for Discrete Logarithms over Hyperelliptic Curves of Large Genus over GF(q). TCS 226(1-2): 7-18(1999)

 
 Sam Roweis, Erik Winfree, Richard Burgoyne, Nickolas Chelyapov, Myron Goodman, Paul Rothemund, Leonard Adleman: A sticker based architecture for DNA computation. 2nd annual workshop on DNA Computing, Princeton University. Eds. L. Landweber and E. Baum, DIMACS: series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society. 1-29 (1999).

 
 
 Leonard Adleman, Paul W. K. Rothemund, Sam Roweis, Erik Winfree: On applying molecular computation to the Data Encryption Standard. 2nd annual workshop on DNA Computing, Princeton University, Eds. L. Landweber and E. Baum, DIMACS: series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society. 31-44 (1999).

 
 Leonard M. Adleman, Jonathan DeMarrais, Ming-Deh A. Huang: Quantum Computability. SIAMJ. Comput. 26(5): 1524-1540 (1997)

 
 Leonard Adleman, David Wofsy: Blind T-cell homeostasis in CD4-deficient mice. J Acquir Immune Defic Syndr Hum Retrovirol 1996 Apr 1;11(4):334-40

 
 Leonard Adleman: On constructing a molecular computer, DNA Based Computers, Eds. R. Lipton and E. Baum, DIMACS: series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society. 1-21 (1996)

 
 Leonard Adleman, Ming-Deh Huang: Counting rational points on curves and Abelian varieties over finite fields. Proceedings of the 1996 Algorithmic Number Theory Symposium, Ed. H. Cohen. Cohen. Springer-Verlag Lecture Notes In Computer Science, 1122:1-16, 1996

 
 Leonard M. Adleman: Algorithmic Number Theory and Its Relationship to Computational Complexity. Computer Science Today 1995: 159-171

 
 Leonard M. Adleman, Ming-Deh A. Huang, Kireeti Kompella: Efficient Checkers for Number-Theoretic Computations. Information and Computation121(1): 93-102 (1995)

 
 Leonard Adleman: Molecular computation of solutions to combinatorial problems. Science, 266:1021-1024. (Nov. 11). 1994.

 
 Leonard M. Adleman: Algorithmic Number Theory-The Complexity Contribution. FOCS 1994:88-113

 
 Leonard Adleman: The function field sieve. Proceedings of the 1994 Algorithmic Number Theory Symposium, Eds. L.M. Adleman and M-D. Huang. Springer-Verlag Lecture Notes In Computer Science, 877: 108-121. 1994.

 
 Leonard Adleman, Kevin McCurley: Open problems in number-theoretic complexity II. Proceedings of the 1994 Algorithmic Number Theory Symposium, Eds. L.M. Adleman and M-D. Huang. Springer-Verlag Lecture Notes In Computer Science, 877: 291-322. 1994.

 
 Leonard M. Adleman, Jonathan DeMarrais Ming-Deh Huang A subexponential algorithm for discrete logarithms in the rational subgroup of the Jacobian of a hyperelliptic curve over a finite field. Proceedings of the 1994 Algorithmic Number Theory Symposium, Eds. L.M. Adleman and M-D. Huang. Springer-Verlag Lecture Notes In Computer Science, 877: 28-40. 1994.

 
 Leonard M. Adleman, Jonathan DeMarrais: A Subexponential Algorithm for Discrete Logarithms over All Finite Fields. Math. Comp., 61 (203):1-15.1993. Also Advances in Cryptology: Crypto '93. Ed. D. R. Stinson, Springer-Verlag Lecture Notes In Computer Science, 773: 147-158. 1993.

 
 Leonard Adleman, David Wofsy: T-cell Homeostasis: Implications in HIV. JAIDS, 6(2):144-152. 1993.

 
  Leonard M. Adleman: Factoring Numbers Using Singular Integers. STOC 1991: 64-71

 
 Leonard Adleman, Ming-Deh Huang: Primality Testing And Abelian Varieties Over Finite Fields. Springer Verlag Lecture Notes In Mathematics, 1512, 142 pages. 1992.

 
 Leonard Adleman, Manuel Blum: Inductive Inference and Unsolvability. Journal of Symbolic Logic, 56(2):891-900. 1991.

 
 Leonard Adleman, David Wofsy: Selective Depletion Of CD4+ T-Cells Elicits The Production Of CD8+ T-cells In Mice. Abstract. VII International Conference on AIDS. Flourence, Italy, (June) 1991.

 
 Leonard Adleman, David Wofsy: T-cell Reconstitution Following Selective Depletion Of CD4+ T-cells. Abstract. Clinical Research, 39:2, 1991.

 
 Kireeti Kompella, Leonard M. Adleman: Fast Checkers for Cryptography. Advances in Cryptology-CRYPTO '90, Springer-Verlag Lecture Notes In Computer Science, 1991: 515-529.

 
 Leonard M. Adleman: An Abstract Theory of Computer Viruses. Advances in Cryptography - Crypto `88, Springer- Verlag Lecture Notes In Computer Science 1988: 354-374. Also chapter in ``Rogue Programs'', Ed. L.J. Hoffman, Van Nostrand Reinhold, New York, 1990.

 
 Leonard M. Adleman, Kireeti Kompella: Using Smoothness to Achieve Parallelism (Abstract).STOC 1988: 528-538

 
 Leonard Adleman: On The Maintenance of T Cell Subpopulations. TR-Computer Science Department, University of Southern California, 1988.

 
 Leonard Adleman, Dennis Estes, Kevin McCurley: Solving Bivariate Quadratic Congruences in Random Polynomial Time. Mathematics of Computation, 48 (177):17-28,

 
 Leonard M. Adleman, Ming-Deh A. Huang: Recognizing Primes in Random Polynomial Time. STOC 1987: 462-469

 
 Leonard M. Adleman, Hendrik W. Lenstra Jr.: Finding Irreducible Polynomials over Finite Fields. STOC 1986: 350-355

 
 Leonard Adleman, Kevin McCurley: Open Problems in Number Theoretic Complexity. Discrete Algorithms and Complexity. 237-262, Academic Press, 1986..

 
 Leonard Adleman, Roger Heath-Brown: The First Case of Fermat's Last Theorem. Invent. Math, 79:409-416, 1985.

 
 Dennis Estes, Leonard M. Adleman, Kireeti Kompella, Kevin S. McCurley, Gary L. Miller: Breaking the Ong-Schnorr-Shamir Signature Scheme for Quadratic Number Fields. Lecture Notes in Computer Science, 218:3-13, 1986.

 
 Leonard Adleman, Robert Rumely, Carl Pomerance: On Distinguishing Prime Numbers From Composite Numbers. Annals of Mathematics, 117: 173-206, 1983.

 
 Leonard M. Adleman: On Breaking Generalized Knapsack Public Key Cryptosystems (Abstract).STOC 1983: 402-412

 
 Ronald L. Rivest, Adi Shamir, Leonard M. Adleman: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems (Reprint). CACM 26(1):96-99 (1983)

 
 Leonard M. Adleman: Implementing an Electronic Notary Public. CRYPTO 1982: 259-265

 
 Leonard M. Adleman: On Breaking the Iterated Merkle-Hellman Public-Key Cryptosystem. CRYPTO1982: 303-308

 
 Leonard M. Adleman, Robert McDonnell: An Application of Higher Reciprocity to Computational Number Theory (Abstract). FOCS 1982: 100-106

 
 Leonard Adleman: Implementing an Electronic Notary Public. Proc. Workshop on Theory and Application of Cryptographic Techniques, Santa Barbara, CA, August 1982.

 
 Leonard M. Adleman: Primality Testing. CRYPTO1981: 10

 
 Leonard M. Adleman, Andrew M. Odlyzko: Irreducibility Testing and Factorization of Polynomials (Extended Abstract). FOCS 1981:409-418

 
 Leonard M. Adleman, Michael C. Loui: Space-Bounded Simulation of Multitape Turing Machines. Mathematical Systems Theory 14:215-222 (1981)

 
 Leonard Adleman, F. T. Leighton: An O(n^{1/10.89}) Primality Testing Algorithm. Mathematics of Computation, 36:261-266, 1981.

 
 Adi Shamir, Ron Rivest, Leonard Adleman: Mental Poker. In The Mathematical Gardner, Ed. Klarner D. E., Wadsworth Intrntl, 37-43,1981.

 
 Leonard M. Adleman: On Distinguishing Prime Numbers from Composite Numbers (Abstract).FOCS 1980: 387-406

 
 Leonard M. Adleman, Kenneth L. Manders: Reductions that Lie. FOCS 1979: 397-410

 
 Leonard M. Adleman: A Subexponential Algorithm for the Discrete Logarithm Problem with Applications to Cryptography (Abstract). FOCS1979: 55-60

 
 Leonard M. Adleman: Two Theorems on Random Polynomial Time. FOCS 1978: 75-83

 
 Leonard M. Adleman, Kenneth L. Manders: Intractability Proofs and the Computational Complexity of Binary Quadratics. University of California (Berkeley) Electronics Research Laboratory Memorandum No. ERL-M78/30, 1978.

 
 Leonard M. Adleman, Kellogg S. Booth, Franco P. Preparata, Walter L. Ruzzo: Improved Time and Space Bounds for Boolean Matrix Multiplication.Acta Informatica 11: 61-77 (1978)

 
 Leonard Adleman, Ron Rivest: The Use of Public Key Cryptography in Communications System Design. Proceedings of the National Telecommunications Conference, Birmingham, 1978.

 
 Leonard Adleman, Michael L. Dertozos Ron Rivest: On Data Banks and Privacy Homomorphisms. Foundations of Secure Computation, Academic Press, 1978.

 
 Ronald L. Rivest, Adi Shamir, Leonard M. Adleman: A Method for Obtaining Digital Signatures and Public-Key Cryptosystems. CACM 21(2): 120-126(1978)

 
 Kenneth L. Manders, Leonard M. Adleman: NP-Complete Decision Problems for Binary Quadratics. JCSS 16(2): 168-184 (1978)

 
 Leonard M. Adleman, Kenneth L. Manders, Gary L. Miller: On Taking Roots in Finite Fields. FOCS1977: 175-178

 
 Leonard M. Adleman, Kenneth L. Manders: Reducibility, Randomness, and Intractability(Abstract). STOC 1977: 151-163

 
 Leonard M. Adleman: Number Theoretic Aspects of Computational Complexity. Ph.D. Thesis, University of California (Berkeley), 1976.

 
 Leonard M. Adleman, Kenneth L. Manders: Diophantine Complexity. FOCS 1976: 81-88

 
 Kenneth L. Manders, Leonard M. Adleman: NP-Complete Decision Problems for Quadratic Polynomials. STOC 1976: 23-29

 
 Leonard M. Adleman, Kenneth L. Manders: Computational Complexity of Decision Procedures for Polynomials (Extended Abstract). FOCS 1975:169-177

 

 Leonard Adleman: Short Permutation Strings. Discrete Mathematics, 10:197-200, 1974.