Subexponential Factoring Algorithms

This chapter deals with integer factoring algorithms whose complexity grows more slowly than an exponential function of log n, the length of the input number n. (An exponential function of log n means a function of the form exp(c log n) = e^c log n = n^c, for some constant c > 0. The complexity functions in this chapter have roughly the form https://www.w3.org/1998/Math/MathML"> exp   ( c log   n ) https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315275765/933deb48-c3c6-4caa-9bb1-e4b3630043c6/content/inequ13_185_1.tif" xmlns:xlink="https://www.w3.org/1999/xlink"/> for some constant c > 0, or even slower growth.) We have already mentioned one of these algorithms, the elliptic curve factoring method, which factors n in about https://www.w3.org/1998/Math/MathML"> exp   ( c ( ln   n )     ln   ln   n ) https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315275765/933deb48-c3c6-4caa-9bb1-e4b3630043c6/content/inequ13_185_2.tif" xmlns:xlink="https://www.w3.org/1999/xlink"/> steps. The complexity of that algorithm is actually a slowly increasing function of the prime factor p it discovers. The complexity of the factoring algorithms described in this chapter depends only on n and not on the size of any prime factor of n. In this respect, they are similar to SQUFOF, whose complexity is O(n ^1/4) steps.