International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Peter L. Montgomery

Publications

Year
Venue
Title
2010
EPRINT
Factorization of a 768-bit RSA modulus
This paper reports on the factorization of the 768-bit number RSA-768 by the number field sieve factoring method and discusses some implications for RSA.
2010
EPRINT
Pushing the Limits of ECM
This paper describes our implementation of phase one of the elliptic curve method on the Cell processor and reports on actual record factors obtained. Our implementation uses a new and particularly efficient variable radix multiplication of independent interest.
2010
EPRINT
An Analysis of Affine Coordinates for Pairing Computation
Kristin E. Lauter Peter L. Montgomery Michael Naehrig
In this paper we analyze the use of affine coordinates for pairing computation. We observe that in many practical settings, for example when implementing optimal ate pairings in high security levels, affine coordinates are faster than using the best currently known formulas for projective coordinates. This observation relies on two known techniques for speeding up field inversions which we analyze in the context of pairing computation. We give detailed performance numbers for a pairing implementation based on these ideas, including timings for base field and extension field arithmetic with relative ratios for inversion-to-multiplication costs, timings for pairings in both affine and projective coordinates, and average timings for multiple pairings and products of pairings.
2010
CRYPTO
2003
EPRINT
Improved Weil and Tate pairings for elliptic and hyperelliptic curves
We present algorithms for computing the {\it squared} Weil and Tate pairings on an elliptic curve and the {\it squared} Tate pairing for hyperelliptic curves. The squared pairings introduced in this paper have the advantage that our algorithms for evaluating them are deterministic and do not depend on a random choice of points. Our pairings save about 20-30\% over the usual pairings.
2003
EPRINT
Trading Inversions for Multiplications in Elliptic Curve Cryptography
Recently, Eisentraeger-Lauter-Montgomery proposed a method for speeding up scalar multiplication on elliptic curves. That method relies on improved formulae for evaluating S = 2P + Q from given points P and Q on an elliptic curve. Compared to the naive approach, the improved formulae save a field multiplication each time the operation is performed. This paper proposes a variant which is faster whenever a field inversion is more expensive than six field multiplications. We also give an improvement when tripling or quadrupling a point, and present a ternary/binary method to perform efficient scalar multiplication.
2002
EPRINT
An Efficient Procedure to Double and Add Points on an Elliptic Curve
We present an algorithm that speeds exponentiation on a general elliptic curve by an estimated 3.8% to 8.5% over the best known general exponentiation methods when using affine coordinates. This is achieved by eliminating a field multiplication when we compute 2P + Q from given points P, Q on the curve. We give applications to simultaneous multiple exponentiation and to the Elliptic Curve Method of factorization. We show how this improvement together with another idea can speed the computation of the Weil and Tate pairings by up to 7.8%.
2000
EUROCRYPT
1999
ASIACRYPT
1996
ASIACRYPT
1995
EUROCRYPT