Wikipedia says that Lenstra's factorization algorithm is the fastest algorithm for factoring out divisors not exceeding 20-25 digits. I have tried to look for a reference on integer factorization speeds that makes it where Lenstra's is beaten by General Number Sieves, and not been able to find something completely explicit. I don't care if it supports Wikipedia's claim exactly, but I would like help in trying to find a reference on modern integer factorization speeds and where a database lookup yields to the next fastest algorithm, and so on.

Currently, it is still the best algorithm for divisors not greatly exceeding 20 to 25 digits (64 to 83 bits or so), as its running time is dominated by the size of the smallest factor p rather than by the size of the number n to be factored -Wikipedia : Lenstra's elliptic curve factorization

Does anyone know of such a paper/article/book I could reference?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.