{'fraction_non_alphanumeric': 0.029529130087789304, 'fraction_numerical': 0.0031923383878691143, 'mean_word_length': 4.9714285714285715, 'pattern_counts': {'":': 0, '<': 0, '<?xml version=': 0, '>': 0, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Lenstra Elliptic Curve Factorization

The paper by H.W. Lenstra ”Factorizing Integers with Elliptic Curves” [3] outlines a method for finding nontrivial factors of integers. Asymptotically it is only the third fastest integer factorization algorithm known (beaten by the Quadratic Sieve and the General Number Field Sieve). Despite this, it is the fastest integer factorization algorithm known whose running time depends on the size of the smallest prime factor. In particular, although Lenstra’s method is slightly slower than the fastest algorithms on products of two similarly sized primes, it will run much quicker when the number in question (however large) has a small prime factor. It is for this reason that Lenstra’s algorithm is still widely used today. In this paper I will outline the most basic form of the algorithm. For modern implementations and performance techniques, refer to [1]. Lenstra’s algorithm is a vast improvement on a previously known integer factorization algorithm known as Pollard’s p − 1 method. In this paper, I will first cover the basic set theory, number theory, and group theory required to understand Pollard’s p − 1 method. Then will discuss fields and elliptic curves and discuss the details of Lenstra’s method.