Laboratory for Molecular Science

Adleman Papers

 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 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: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:

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, 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.