Breadcrumbs Section. Click here to navigate to respective pages.

Chapter

Chapter

# Subexponential Factoring Algorithms

DOI link for Subexponential Factoring Algorithms

Subexponential Factoring Algorithms book

# Subexponential Factoring Algorithms

DOI link for Subexponential Factoring Algorithms

Subexponential Factoring Algorithms book

## ABSTRACT

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
exp
(
c
log
n
)
https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315275765/55ac6a0f-e1d1-4632-a7de-055ea0b169a6/content/inequ13_185_1.tif"/>
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
exp
(
c
(
ln
n
)
ln
ln
n
)
https://s3-euw1-ap-pe-df-pch-content-public-p.s3.eu-west-1.amazonaws.com/9781315275765/55ac6a0f-e1d1-4632-a7de-055ea0b169a6/content/inequ13_185_2.tif"/>
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.