Arjen Lenstra
Encyclopedia
Arjen Klaas Lenstra is a Dutch
mathematician
. He studied mathematics at the University of Amsterdam.
He is currently a professor at the EPFL (Lausanne
), in the Laboratory for Cryptologic Algorithms, and
previously worked for Citibank
and Bell Labs
.
Lenstra is active in cryptography
and computational number theory
, especially in areas such as
integer factorization
.
With Mark Manasse, he was the first to seek volunteers over the internet for a large scale scientific distributed computing project. Such projects became more common after the Factorization of RSA-129 which was a high publicity distributed factoring success led by Lenstra along with Derek Atkins, Michael Graff and Paul Leyland
. He was also a leader in the successful factorizations of several other RSA numbers
.
Lenstra was also involved in the development of the number field sieve
. With coauthors, he showed the great potential of the algorithm early on by using it to factor the ninth Fermat number, which was far out of reach by other factoring algorithms of the time. He has since been involved with several other number field sieve factorizations including the current record, RSA-768.
Lenstra's most widely cited scientific result is the first polynomial time algorithm to factor polynomials with rational coefficients in the seminal paper that introduced the LLL lattice reduction algorithm
with Hendrik Willem Lenstra and László Lovász
.
Lenstra is also co-inventor of the XTR
cryptosystem
.
Lenstra's brother Hendrik Lenstra is a professor in mathematics at Leiden University
and his brother Jan Karel Lenstra
is the director of Centrum Wiskunde & Informatica (CWI).
On 1 March 2005, Arjen Lenstra, Xiaoyun Wang
, and Benne de Weger of Eindhoven University of Technology
demonstrated construction of two X.509
certificates with different public keys and the same MD5
hash, a demonstrably practical hash collision
. The construction included private keys for both public keys.
Lenstra is the recipient of the Excellence in the Field of Mathematics RSA Conference 2008 Award.
Netherlands
The Netherlands is a constituent country of the Kingdom of the Netherlands, located mainly in North-West Europe and with several islands in the Caribbean. Mainland Netherlands borders the North Sea to the north and west, Belgium to the south, and Germany to the east, and shares maritime borders...
mathematician
Mathematician
A mathematician is a person whose primary area of study is the field of mathematics. Mathematicians are concerned with quantity, structure, space, and change....
. He studied mathematics at the University of Amsterdam.
He is currently a professor at the EPFL (Lausanne
Lausanne
Lausanne is a city in Romandy, the French-speaking part of Switzerland, and is the capital of the canton of Vaud. The seat of the district of Lausanne, the city is situated on the shores of Lake Geneva . It faces the French town of Évian-les-Bains, with the Jura mountains to its north-west...
), in the Laboratory for Cryptologic Algorithms, and
previously worked for Citibank
Citibank
Citibank, a major international bank, is the consumer banking arm of financial services giant Citigroup. Citibank was founded in 1812 as the City Bank of New York, later First National City Bank of New York...
and Bell Labs
Bell Labs
Bell Laboratories is the research and development subsidiary of the French-owned Alcatel-Lucent and previously of the American Telephone & Telegraph Company , half-owned through its Western Electric manufacturing subsidiary.Bell Laboratories operates its...
.
Lenstra is active in cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
and computational number theory
Computational number theory
In mathematics, computational number theory, also known as algorithmic number theory, is the study of algorithms for performing number theoretic computations...
, especially in areas such as
integer factorization
Integer factorization
In number theory, integer factorization or prime factorization is the decomposition of a composite number into smaller non-trivial divisors, which when multiplied together equal the original integer....
.
With Mark Manasse, he was the first to seek volunteers over the internet for a large scale scientific distributed computing project. Such projects became more common after the Factorization of RSA-129 which was a high publicity distributed factoring success led by Lenstra along with Derek Atkins, Michael Graff and Paul Leyland
Paul Leyland
Paul Leyland is a British number theorist who has studied integer factorization and primality testing.He has contributed to the factorization of RSA-129, RSA-140, and RSA-155, as well as potential factorial primes as large as 400! + 1. He has also studied Cunningham numbers, Cullen numbers, Woodall...
. He was also a leader in the successful factorizations of several other RSA numbers
RSA numbers
In mathematics, the RSA numbers are a set of large semiprimes that are part of the RSA Factoring Challenge. The challenge was to find the prime factors but it was declared inactive in 2007...
.
Lenstra was also involved in the development of the number field sieve
General number field sieve
In number theory, the general number field sieve is the most efficient classical algorithm known for factoring integers larger than 100 digits...
. With coauthors, he showed the great potential of the algorithm early on by using it to factor the ninth Fermat number, which was far out of reach by other factoring algorithms of the time. He has since been involved with several other number field sieve factorizations including the current record, RSA-768.
Lenstra's most widely cited scientific result is the first polynomial time algorithm to factor polynomials with rational coefficients in the seminal paper that introduced the LLL lattice reduction algorithm
Lenstra–Lenstra–Lovász lattice basis reduction algorithm
The LLL-reduction algorithm is a polynomial time lattice reduction algorithm invented by Arjen Lenstra, Hendrik Lenstra and László Lovász in 1982, see...
with Hendrik Willem Lenstra and László Lovász
László Lovász
László Lovász is a Hungarian mathematician, best known for his work in combinatorics, for which he was awarded the Wolf Prize and the Knuth Prize in 1999, and the Kyoto Prize in 2010....
.
Lenstra is also co-inventor of the XTR
XTR
In cryptography, XTR is an algorithm for public-key encryption. XTR stands for ‘ECSTR’, which is an abbreviation for Efficient and Compact Subgroup Trace Representation. It is a method to represent elements of a subgroup of a multiplicative group of a finite field...
cryptosystem
Cryptosystem
There are two different meanings of the word cryptosystem. One is used by the cryptographic community, while the other is the meaning understood by the public.- General meaning :...
.
Lenstra's brother Hendrik Lenstra is a professor in mathematics at Leiden University
Leiden University
Leiden University , located in the city of Leiden, is the oldest university in the Netherlands. The university was founded in 1575 by William, Prince of Orange, leader of the Dutch Revolt in the Eighty Years' War. The royal Dutch House of Orange-Nassau and Leiden University still have a close...
and his brother Jan Karel Lenstra
Jan Karel Lenstra
Jan Karel Lenstra is a Dutch mathematician and operations researcher, known for his work on scheduling algorithms, local search, and the travelling salesman problem....
is the director of Centrum Wiskunde & Informatica (CWI).
On 1 March 2005, Arjen Lenstra, Xiaoyun Wang
Xiaoyun Wang
Wang Xiaoyun is a researcher and professor in the Department of Mathematics and System Science, Shandong University, Shandong, China....
, and Benne de Weger of Eindhoven University of Technology
Eindhoven University of Technology
The ' is a university of technology located in Eindhoven, Netherlands. The motto of the university is: Mens agitat molem . The university was the second of its kind in the Netherlands, only Delft University of Technology existed previously. Until mid-1980 it was known as the...
demonstrated construction of two X.509
X.509
In cryptography, X.509 is an ITU-T standard for a public key infrastructure and Privilege Management Infrastructure . X.509 specifies, amongst other things, standard formats for public key certificates, certificate revocation lists, attribute certificates, and a certification path validation...
certificates with different public keys and the same MD5
MD5
The MD5 Message-Digest Algorithm is a widely used cryptographic hash function that produces a 128-bit hash value. Specified in RFC 1321, MD5 has been employed in a wide variety of security applications, and is also commonly used to check data integrity...
hash, a demonstrably practical hash collision
Hash collision
Not to be confused with wireless packet collision.In computer science, a collision or clash is a situation that occurs when two distinct pieces of data have the same hash value, checksum, fingerprint, or cryptographic digest....
. The construction included private keys for both public keys.
Lenstra is the recipient of the Excellence in the Field of Mathematics RSA Conference 2008 Award.
See also
- Lenstra–Lenstra–Lovász lattice basis reduction algorithmLenstra–Lenstra–Lovász lattice basis reduction algorithmThe LLL-reduction algorithm is a polynomial time lattice reduction algorithm invented by Arjen Lenstra, Hendrik Lenstra and László Lovász in 1982, see...
- General Number Field SieveGeneral number field sieveIn number theory, the general number field sieve is the most efficient classical algorithm known for factoring integers larger than 100 digits...