Lenstra's Elliptic Curve Factorization Method

Explore Lenstra's elliptic curve factorization method in this 31-minute Churchill CompSci Talk by Leo Lai. Delve into the intersection of computational number theory and cryptography, focusing on the fundamental problem of factoring large integers. Learn about the innovative algorithm developed by Lenstra in 1987, which utilizes elliptic curves to create one of the fastest special-purpose factorization methods to date. Discover how this algorithm has not only advanced factorization techniques but also contributed to new developments in number theory. Gain insights into integer factorization, special-purpose algorithms, the p-1 algorithm, elliptic curves, group law, point counting, and complexity analysis. No advanced knowledge is required beyond basic number theory to understand this comprehensive exploration of a crucial topic in computer science and cryptography.

Intro
Integer factorization
Special purpose factorization algorithms
Motivational consideration
The p-1 algorithm
Observations
Extension
Elliptic curves
Group law
Reduction mod p
Point count
Basic algorithm
Complexity analysis
Estimation of
Choice of B
Factorization record