Henry
Salvatori Professor of
Computer
Science
And Professor
of Molecular Biology
University
of Southern California
Los Angeles,
California 90089-0781
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.