Peter L. Montgomery

Bio
Peter L. Montgomery was a 1967 Putnam fellow while at the University of California at Berkeley. He worked 17 years at Unisys before receiving the PhD degree from the University of California at Los Angeles in 1992. Now, he's a principal researcher at Microsoft Research in Redmond, Washington. His speciality is computational number theory. He is best known as the inventor of Montgomery multiplication. He has improved integer factorization algorithms.




Publications

Compilers

• Evaluation of boolean expressions on one's complement machines, by Peter L. Montgomery, in ACM SIGPLAN Notices, volume 13, issue 12, 1978
• Division by Invariant Integers using Multiplication, by Torbjörn Granlund and Peter L. Montgomery, Proceedings of the ACM SIGPLAN 1994 conference on Programming language design and implementation, 1994
  

Arithmetic

• Efficient SIMD arithmetic modulo a Mersenne number, by Joppe W. Bos, Thorsten Kleinjung, Arjen K. Lenstra and Peter L. Montgomery, in 20th IEEE Symposium on Computer Arithmetic (ARITH-20), pages 213-221, 2011
• Solving a 112-bit Prime Elliptic Curve Discrete Logarithm Problem on Game Consoles using Sloppy Reduction, by Joppe W. Bos, Marcelo E. Kaihara, Thorsten Kleinjung, Arjen K. Lenstra, Peter L. Montgomery, in The International Journal of Applied Cryptography, 2011 (to appear)
• Pollard rho on the PlayStation 3, by Joppe W. Bos, Marcelo E. Kaihara, Peter L. Montgomery, in handouts of Special-purpose Hardware for Attacking Cryptographic Systems (SHARCS'09), pages 35-50, 2009
• Trading Inversions for Multiplications in Elliptic Curve Cryptography, by Mathieu Ciet, Marc Joye, Kristin Lauter, Peter L. Montgomery, in Design Codes and Cryptography, vol. 39, no. 2, pp. 189-206, 2006
• Five, Six, and Seven-Term Karatsuba-Like Formulae, by Peter L. Montgomery, IEEE Transactions on Computers,  vol. 54, no. 3, pp. 362-369, 2005
  
• Modular Multiplication Without Trial Division, by Peter L. Montgomery, Mathematics of Computation, volume 44, pp. 519-521, 1985
  
• Evaluating Recurrences of Form X_m+n = f(X_m, X_n, X_m-n) Via Lucas Chains, Peter L. Montgomery, 1983 (unpublished)
  

Factoring

• A heterogeneous computing environment to solve the 768-bit RSA challenge, by Thorsten Kleinjung, Joppe W. Bos, Arjen K. Lenstra, Dag Arne Osvik, Kazumaro Aoki, Scott Contini, Jens Franke, Emmanuel Thomé, Pascal Jermini, Michela Thiémard, Paul Leyland, Peter L. Montgomery, Andrey Timofeev, Heinz Stockinger, in Cluster Computing: the Journal of Networks, Software Tools and Applications, pp. 1-16, 2010
• Factorization of a 768-bit RSA modulus, by Thorsten Kleinjung, Kazumaro Aoki, Jens Franke, Arjen Lenstra, Emmanuel Thomé, Joppe Bos, Pierrick Gaudry, Alexander Kruppa, Peter Montgomery, Dag Arne Osvik, Herman te Riele, Andrey Timofeev, and Paul Zimmermann, in CRYPTO 2010, volume 6223 of LNCS, pages 333-350, 2010 
• Improved Stage 2 to P±1 Factoring Algorithms, by Peter L. Montgomery, Alexander Kruppa, in Algorithmic Number Theory (ANTS-VIII), volume 5011 of LNCS, pp. 180-195, 2008
• Factorization of a 512-Bit RSA Modulus, by Stefania Cavallar, Bruce Dodson, Arjen K. Lenstra, Walter M. Lioen, Peter L. Montgomery, Brian Murphy, Herman J. J. te Riele, Karen Aardal, Jeff Gilchrist, Gérard Guillerm, Paul C. Leyland, Joël Marchand, François Morain, Alec Muffett, Chris Putnam, Craig Putnam, Paul Zimmermann, in EUROCRYPT 2000, volume 1807 of LNCS, pp. 1-18, 2000
• Factorization of RSA-140 Using the Number Field Sieve, by Stefania Cavallar, Bruce Dodson, Arjen K. Lenstra, Paul C. Leyland, Walter M. Lioen, Peter L. Montgomery, Brian Murphy, Herman J. J. te Riele, Paul Zimmermann, in ASIACRYPT 1999, volume 1716 of LNCS, pp. 195-207, 1999
• A new world record for the special number field sieve factoring method, by Peter L. Montgomery, Stefania Cavallar, Herman te Riele, in CWI quarterly, volume 10, pp. 105-107, 1997
• A World Wide Number Field Sieve Factoring Record: On to 512 Bits, by James Cowie, Bruce Dodson, R. Marije Elkenbracht-Huizing, Arjen K. Lenstra, Peter L. Montgomery, Jörg Zayer, in ASIACRYPT 1996, volume 1163 of LNCS, pp. 382-394, 1996
• A Block Lanczos Algorithm for Finding Dependencies Over GF(2), by Peter L. Montgomery, in EUROCRYPT 1995, volume 921 of LNCS, pp. 106-120, 1995
• A survey of modern integer factorization algorithms, by Peter L. Montgomery, in CWI quarterly, volume 7, pp. 337-365, 1994
• Square roots of products of algebraic numbers, by Peter L. Montgomery, in Mathematics of Computation 1943-1993: a Half-Century of Computational Mathematics, Proceedings of Symposia in Applied Mathematics, American Mathematical Society, pp. 567-571, 1994
• An FFT Extension of the Elliptic Curve Method of Factorization, by Peter L. Montgomery, PhD thesis, University of California, Los Angeles, 1992
• An FFT extension to the P-1 factoring algorithm, by Peter L. Montgomery, Robert D. Silverman, in Mathematics of Computation, volume 54, 1990
• Tables of Fibonacci and Lucas factorizations, by John Brillhart, Peter L. Montgomery, Robert D. Silverman, in Mathematics of Computation, volume 50, pp. 251-260, 1988
• Speeding the Pollard and elliptic curve methods of factorization, by Peter L. Montgomery, in Mathematics of Computation, volume 48, pp. 243-264, 1987
  

Pairing

• An Analysis of Affine Coordinates for Pairing Computation, by Kristin Lauter, Peter L. Montgomery, Michael Naehrig, in Pairing 2010, volume 6487 of LNCS, pp. 1-20, 2010
• Improved Weil and Tate Pairings for Elliptic and Hyperelliptic Curves, by Kirsten Eisenträger, Kristin Lauter, Peter L. Montgomery, in Algorithmic Number Theory (ANTS-VI), volume 3076 in LNCS, pp. 169-183, 2004
• Fast Elliptic Curve Arithmetic and Improved Weil Pairing Evaluation, by Kirsten Eisenträger, Kristin Lauter, Peter L. Montgomery, in CT-RSA 2003, volume 2612 in LNCS, pp. 343-354, 2003

Diophantine equations

• The period of the Bell numbers modulo a prime, by Peter L. Montgomery, Sangil Nahm, Samuel S. Wagstaff Jr., in Mathematics of Computation, volume 79, pp. 1793-1800, 2010
• New solutions of a^p-1 = 1 (mod p²), by Peter L. Montgomery, in Mathematics of Computation, volume 61, pp. 361-363, 1993
  

Cryptographic Key Sizes

• On the Security of 1024-bit RSA and 160-bit Elliptic Curve Cryptography, by Joppe W. Bos, Marcelo E. Kaihara, Thorsten Kleinjung, Arjen K. Lenstra, Peter L. Montgomery, in Cryptology ePrint Archive: Report 2009/389, 2009

Miscellaneous

• Side Channel Leakage Profiling in Software, by Daniel Shumow, Peter L. Montgomery, in Workshop Proceedings COSADE 2010 First International Workshop on Constructive Side-Channel Analysis and Secure Design, 2010
• Euclidean Ramsey theorems. I, by Paul Erdös, Ronald L. Graham, Peter L. Montgomery, Bruce L. Rothschild, Joel Spencer, Ernst G. Straus, in Journal of Combinatorial Theory, Series A, volume 14, issue 3, pp. 341-363, 1973
• Euclidean Ramsey theorems. II, by Paul Erdös, Ronald L. Graham, Peter L. Montgomery, Bruce L. Rothschild, Joel Spencer, Ernst G. Straus, in Colloquia Mathematica Societatis János Bolyai, 10 Infinite and Finite Sets, pp. 529-557, 1973
• Euclidean Ramsey theorems. III, by Paul Erdös, Ronald L. Graham, Peter L. Montgomery, Bruce L. Rothschild, Joel Spencer, Ernst G. Straus, in Colloquia Mathematica Societatis János Bolyai, 10 Infinite and Finite Sets, pp. 559-583, 1973