Andrew Odlyzko: Papers on Algorithms and Computational Complexity

• Discrete logarithms: The past and the future, A. M. Odlyzko, Designs, Codes, and Cryptography 19 (2000), pp. 129-145. Reprinted in Towards a Quarter-Century of Public Key Cryptography, N. Koblitz, ed., Kluwer, 2000, pp. 59-75. [Abstract] [PDF]

• The future of integer factorization, A. M. Odlyzko, CryptoBytes (The technical newsletter of RSA Laboratories) 1 (no. 2) (1995), pp. 5-12. [PDF] [CryptoBytes issue]

• Short proofs for nondivisibility of sparse polynomials under the extended Riemann hypothesis, D. Yu. Grigoriev, M. Karpinski, and A. M. Odlyzko, Fund. Inform. 28 (1996), pp. 297-301. Preliminary version on pp. 117-122 in Proc. Intern. Symp. Symbolic Algebraic Computation: ISSAC '92, P. S. Wang (ed.), ACM Press, (1992). [PDF]

• Search for the maximum of a random walk, A. M. Odlyzko, Random Struct. Alg. 6 (1995), pp. 275-295. Short abstract in Adv. Appl. Prob. 24 (1992) p. 768. Extended abstract in Proc. 26-th ACM Symp. Theory Comp. (1994), pp. 336-345. [PDF]

• Discrete logarithms and smooth polynomials, A. M. Odlyzko, pp. 269-278 in Finite Fields: Theory, Applications and Algorithms, G. L. Mullen and P. Shiue, eds., Amer. Math. Soc., Contemporary Math. #168 (1994). [PDF]

• Analytic computations in number theory, A. M. Odlyzko, Mathematics of Computation 1943-1993: A Half-Century of Computational Mathematics, W. Gautschi (ed.), Amer. Math. Soc., Proc. Symp. Appl. Math. #48 (1994), pp. 451-463. [PDF]

• Public key cryptography, A. M. Odlyzko, AT&T Tech. J., 73:5 (Sept.-Oct. 1994), pp. 17-23. [PDF]

• Fast parallel solution of fixed point equations for the performance evaluation of circuit-switched networks, A. G. Greenberg, A. M. Odlyzko, J. Rexford, and D. Espinosa, pp.59-74 in Performance '93: Proc. 16-th IFIP W.G.7.3 Intern. Symp. Computer Perf. Modeling, Measurement, and Evaluation, G. Iazeolla and S. S. Lavenberg (eds.), Elsevier, (1993). [PDF]

• Improved low-density subset sum algorithms, M. J. Coster, A. Joux, B. A. LaMacchia, A. M. Odlyzko, C. P. Schnorr, and J. Stern, Computational Complexity, 2 (1992), pp. 111-128. [PDF]

• An improved low-density subset sum algorithm, M. J. Coster, B. A. LaMacchia, A. M. Odlyzko, and C. P. Schnorr, pp. 54-67 in Advances in Cryptology - EUROCRYPT '91, D. W. Davies (ed.), Springer Verlag, Lecture Notes in Computer Science #547 (1991). [PDF]

• Computation of discrete logarithms in prime fields, B. A. LaMacchia and A. M. Odlyzko, Designs, Codes, and Cryptography, 1 (1991), pp. 46-62, Extended abstract in Advances in Cryptology - CRYPTO '90, A. J. Menezes, and S. A. Vanstone (eds.), Springer Verlag, Lecture Notes in Computer Science #537, 1991, pp. 616-618. [PDF]

• Solving large sparse linear systems over finite fields, B. A. LaMacchia and A. M. Odlyzko, pp. 109-133 in Advances in Cryptology - CRYPTO '90, A. J. Menezes and S. A. Vanstone (eds.), Springer Verlag, Lecture Notes in Computer Science #537 (1991). [PDF]

• Cryptanalysis: A survey of recent results, E. F. Brickell and A. M. Odlyzko, pp. 501-540 in Contemporary Cryptology, G. J. Simmons (ed.), IEEE Press (1991). Preliminary version in Proc. IEEE 76, 1988, pp. 578-593. [PDF]

• The rise and fall of knapsack cryptosystems, A. M. Odlyzko, pp. 75-88 in Cryptology and Computational Number Theory, C. Pomerance (ed.), Am. Math. Soc., Proc. Symp. Appl. Math. #42 (1990). [PDF]

• Fast algorithms for multiple evaluations of the Riemann zeta function, A. M. Odlyzko and A. Schoenhage, Trans. Am. Math. Soc., 309 (1988), pp. 797-809. [online journal version]

• Simple, efficient asynchronous parallel algorithms for maximization, A. G. Greenberg, B. D. Lubachevsky, and A. M. Odlyzko, ACM Trans. Programming Languages and Systems, 1988, pp. 313-337. Preliminary version in Proc. 4th ACM Symp. Principles Distrib. Computing, 1985, pp. 300-308.

• New analytic algorithms in number theory, A. M. Odlyzko, pp. 466-475 in Proceedings 1986 International Congress of Mathematicians, Amer. Math. Soc., 1987, [PDF]

• Computing pi(x): An analytic method, J. C. Lagarias and A. M. Odlyzko, J. Algorithms, 8 (1987), pp. 173-191. [PDF]

• On the complexity of computing discrete logarithms and factoring integers, A. M. Odlyzko, pp. 113-116 in Open Problems in Communication and Computation, T. M. Cover and B. Gopinath (eds.), Springer, 1987. [PDF]

• Probabilistic analysis of optimum partitioning, N. Karmarkar, R. M. Karp, G. S. Lueker, and A. M. Odlyzko, J. Appl. Prob., 23 (1986), pp. 626-645. [comments]

• Discrete logarithms in GF(p), D. Coppersmith, A. M. Odlyzko, and R. Schroeppel, Algorithmica, 1 (1986), pp. 1-15.

• Discrete logarithms in finite fields and their cryptographic significance , A. M. Odlyzko, pp. 224-314 in Advances in Cryptology: Proceedings of EUROCRYPT 84, T. Beth, N. Cot, and I. Ingemarsson (eds.), Springer-Verlag, Lecture Notes in Computer Science #209, 1985. [PDF]

• Computing pi(x): The Meissel-Lehmer method, J. C. Lagarias, V. S. Miller, and A. M. Odlyzko, Math. Comp., 44 (1985), pp. 537-560. [online journal version]

• Solving low-density subset sum problems, J. C. Lagarias and A. M. Odlyzko, J. ACM, 32 (1985), pp. 229-246. Preliminary version in Proc. 24th IEEE Foundations Computer Science Symp., pp. 1-10, 1983.

• Cryptanalytic attacks on the multiplicative knapsack cryptosystem and on Shamir's signature scheme, A. M. Odlyzko, IEEE Trans. Information Theory, IT-30 (1984), pp. 594-601. [PDF]

• Evaluation of the Adleman attack on multiply iterated knapsack cryptosystems, E. F. Brickell, J. C. Lagarias, and A. M. Odlyzko, pp. 39-42 in Advances in Cryptology: Proceedings of Crypto 83, D. Chaum (ed.), Plenum Press, 1984.

• New algorithms for computing pi(x), J. C. Lagarias and A. M. Odlyzko, pp. 176-193 in Number Theory: New York 1982, D. V. Chudnovsky, G. V. Chudnovsky, H. Cohn and M. B. Nathanson (eds.), Springer-Verlag, Lecture Notes in Mathematics #1052, 1984.

• Irreducibility testing and factorization of polynomials, L. M. Adleman and A. M. Odlyzko, Math. Comp., 41 (1983), pp. 699-709. Preliminary version in Proc. 22nd IEEE Foundations Computer Science Symp., pp. 409-418, 1981. [online Math. Comp. version]

• String overlaps, pattern matching, and nontransitive games, L. J. Guibas and A. M. Odlyzko, J. Comb. Theory A, 30 (1981), pp. 183-208.

• A new proof of the linearity of the Boyer-Moore string searching algorithm, L. J. Guibas and A. M. Odlyzko, SIAM J. Computing, 9 (1980), pp. 672-682. Preliminary version in Proc. 18th IEEE Foundations Computer Science Symp., pp. 189-195, 1977.

• On computing Artin L-functions in the critical strip, J. C. Lagarias and A. M. Odlyzko, Math. Comp., 33 (1979), pp. 1081-1095. [online journal version]

• On DSN antenna scheduling, L. H. Harper, R. J. McEliece, and A. M. Odlyzko, JPL Deep Space Network Progress Reports, 42-20 (1974), pp. 53-56.