Henry
Salvatori Professor of
Computer
Science
And Professor
of Molecular Biology
University
of Southern California
Los Angeles,
California 900890781
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:
1980Present
University of Southern California
1985
Henry Salvatori Professor
1983
Professor
1980
Associate Professor (with tenure)
19761980
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/948/31/00
(NO COST EXTENSION)
Total
Award: $1,317,629
CCR9403662
ONR/DARPA
Computational
Aspects of Molecular Science
05/01/9804/30/01
Total
Award: $1,602,380
N000149810664
JPL/NASA
Molecular
Computation
04/10/9812/31/00
Total
Award: $492,327
961352
DARPA
High
Speed Cell Analysis, BioSpice, Cellular Logic Devices ,and Exquisite Detection:
Towards Interactive Biology
07/01/9912/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 PublicKeyCryptography
(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 PublicKey
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 PublicKey Cryptosystems,"
Communications of the ACM, 21(2):120126,(February) 1978. (with R. Rivest and
A. Shamir).
This
paper presents the first incarnation of a publickey 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.,IT22) 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 publickey 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, 173206, 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, AddisonWesley, 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 n^{c} 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:409416,
1985. (with R.HeathBrown).
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:
x^{n}+y^{n}=z^{n}
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,
SpringerVerlag, 1979).
In
this paper (and the companion paper "Theorem de BrunTitchmarsh application
au theorem de Fermat" by E. Fouvry Invent. Math, 79: 383407, 1985) the
following was proved:
Theorem[Adleman,
Fouvry, HeathBrown] 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 MD
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 MonteCarlo Test For Primality,"
SIAM J. Comput. 6 (1977), 8485) 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: 10211024, (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, MingDeh A. Huang: Function Field Sieve Method for Discrete Logarithms
over Finite Fields. Information and Compuation151(12): 516 (1999)
Leonard
M. Adleman, Jonathan DeMarrais, MingDeh A. Huang: A Subexponential Algorithm
for Discrete Logarithms over Hyperelliptic Curves of Large Genus over GF(q).
TCS 226(12): 718(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. 129 (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.
3144 (1999).
Leonard
M. Adleman, Jonathan DeMarrais, MingDeh A. Huang: Quantum Computability. SIAMJ.
Comput. 26(5): 15241540 (1997)
Leonard
Adleman, David Wofsy: Blind Tcell homeostasis in CD4deficient mice. J Acquir
Immune Defic Syndr Hum Retrovirol 1996 Apr 1;11(4):33440
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. 121 (1996)
Leonard
Adleman, MingDeh Huang: Counting rational points on curves and Abelian varieties
over finite fields. Proceedings of the 1996 Algorithmic Number Theory Symposium,
Ed. H. Cohen. Cohen. SpringerVerlag Lecture Notes In Computer Science, 1122:116,
1996
Leonard
M. Adleman: Algorithmic Number Theory and Its Relationship to Computational
Complexity. Computer Science Today 1995: 159171
Leonard
M. Adleman, MingDeh A. Huang, Kireeti Kompella: Efficient Checkers for NumberTheoretic
Computations. Information and Computation121(1): 93102 (1995)
Leonard
Adleman: Molecular computation of solutions to combinatorial problems. Science,
266:10211024. (Nov. 11). 1994.
Leonard
M. Adleman: Algorithmic Number TheoryThe Complexity Contribution. FOCS 1994:88113
Leonard
Adleman: The function field sieve. Proceedings of the 1994 Algorithmic Number
Theory Symposium, Eds. L.M. Adleman and MD. Huang. SpringerVerlag Lecture
Notes In Computer Science, 877: 108121. 1994.
Leonard
Adleman, Kevin McCurley: Open problems in numbertheoretic complexity II. Proceedings
of the 1994 Algorithmic Number Theory Symposium, Eds. L.M. Adleman and MD.
Huang. SpringerVerlag Lecture Notes In Computer Science, 877: 291322. 1994.
Leonard
M. Adleman, Jonathan DeMarrais MingDeh 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 MD. Huang. SpringerVerlag Lecture Notes In
Computer Science, 877: 2840. 1994.
Leonard
M. Adleman, Jonathan DeMarrais: A Subexponential Algorithm for Discrete Logarithms
over All Finite Fields. Math. Comp., 61 (203):115.1993. Also Advances in Cryptology:
Crypto '93. Ed. D. R. Stinson, SpringerVerlag Lecture Notes In Computer Science,
773: 147158. 1993.
Leonard
Adleman, David Wofsy: Tcell Homeostasis: Implications in HIV. JAIDS, 6(2):144152.
1993.
Leonard
M. Adleman: Factoring Numbers Using Singular Integers. STOC 1991: 6471
Leonard
Adleman, MingDeh 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):891900. 1991.
Leonard
Adleman, David Wofsy: Selective Depletion Of CD4+ TCells Elicits The Production
Of CD8+ Tcells In Mice. Abstract. VII International Conference on AIDS. Flourence,
Italy, (June) 1991.
Leonard
Adleman, David Wofsy: Tcell Reconstitution Following Selective Depletion Of
CD4+ Tcells. Abstract. Clinical Research, 39:2, 1991.
Kireeti
Kompella, Leonard M. Adleman: Fast Checkers for Cryptography. Advances in CryptologyCRYPTO
'90, SpringerVerlag Lecture Notes In Computer Science, 1991: 515529.
Leonard
M. Adleman: An Abstract Theory of Computer Viruses. Advances in Cryptography
 Crypto `88, Springer Verlag Lecture Notes In Computer Science 1988: 354374.
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: 528538
Leonard
Adleman: On The Maintenance of T Cell Subpopulations. TRComputer 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):1728,
Leonard
M. Adleman, MingDeh A. Huang: Recognizing Primes in Random Polynomial Time.
STOC 1987: 462469
Leonard
M. Adleman, Hendrik W. Lenstra Jr.: Finding Irreducible Polynomials over Finite
Fields. STOC 1986: 350355
Leonard
Adleman, Kevin McCurley: Open Problems in Number Theoretic Complexity. Discrete
Algorithms and Complexity. 237262, Academic Press, 1986..
Leonard
Adleman, Roger HeathBrown: The First Case of Fermat's Last Theorem. Invent.
Math, 79:409416, 1985.
Dennis
Estes, Leonard M. Adleman, Kireeti Kompella, Kevin S. McCurley, Gary L. Miller:
Breaking the OngSchnorrShamir Signature Scheme for Quadratic Number Fields.
Lecture Notes in Computer Science, 218:313, 1986.
Leonard
Adleman, Robert Rumely, Carl Pomerance: On Distinguishing Prime Numbers From
Composite Numbers. Annals of Mathematics, 117: 173206, 1983.
Leonard
M. Adleman: On Breaking Generalized Knapsack Public Key Cryptosystems (Abstract).STOC
1983: 402412
Ronald
L. Rivest, Adi Shamir, Leonard M. Adleman: A Method for Obtaining Digital Signatures
and PublicKey Cryptosystems (Reprint). CACM 26(1):9699 (1983)
Leonard
M. Adleman: Implementing an Electronic Notary Public. CRYPTO 1982: 259265
Leonard
M. Adleman: On Breaking the Iterated MerkleHellman PublicKey Cryptosystem.
CRYPTO1982: 303308
Leonard
M. Adleman, Robert McDonnell: An Application of Higher Reciprocity to Computational
Number Theory (Abstract). FOCS 1982: 100106
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:409418
Leonard
M. Adleman, Michael C. Loui: SpaceBounded Simulation of Multitape Turing Machines.
Mathematical Systems Theory 14:215222 (1981)
Leonard
Adleman, F. T. Leighton: An O(n^{1/10.89}) Primality Testing Algorithm. Mathematics
of Computation, 36:261266, 1981.
Adi
Shamir, Ron Rivest, Leonard Adleman: Mental Poker. In The Mathematical Gardner,
Ed. Klarner D. E., Wadsworth Intrntl, 3743,1981.
Leonard
M. Adleman: On Distinguishing Prime Numbers from Composite Numbers (Abstract).FOCS
1980: 387406
Leonard
M. Adleman, Kenneth L. Manders: Reductions that Lie. FOCS 1979: 397410
Leonard
M. Adleman: A Subexponential Algorithm for the Discrete Logarithm Problem with
Applications to Cryptography (Abstract). FOCS1979: 5560
Leonard
M. Adleman: Two Theorems on Random Polynomial Time. FOCS 1978: 7583
Leonard
M. Adleman, Kenneth L. Manders: Intractability Proofs and the Computational
Complexity of Binary Quadratics. University of California (Berkeley) Electronics
Research Laboratory Memorandum No. ERLM78/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:
6177 (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 PublicKey Cryptosystems. CACM 21(2): 120126(1978)
Kenneth
L. Manders, Leonard M. Adleman: NPComplete Decision Problems for Binary Quadratics.
JCSS 16(2): 168184 (1978)
Leonard
M. Adleman, Kenneth L. Manders, Gary L. Miller: On Taking Roots in Finite Fields.
FOCS1977: 175178
Leonard
M. Adleman, Kenneth L. Manders: Reducibility, Randomness, and Intractability(Abstract).
STOC 1977: 151163
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: 8188
Kenneth
L. Manders, Leonard M. Adleman: NPComplete Decision Problems for Quadratic
Polynomials. STOC 1976: 2329
Leonard
M. Adleman, Kenneth L. Manders: Computational Complexity of Decision Procedures
for Polynomials (Extended Abstract). FOCS 1975:169177
Leonard Adleman:
Short Permutation Strings. Discrete Mathematics, 10:197200, 1974.