ABSTRACT
This chapter introduces methods of factoring integers that are slower than the fastest known ones. They require time O(n c), where c > 0 is a constant, to factor n. They are called “exponential algorithms” because their time complexity is exponential in log n, the length of the input, since nc = ec ln n . We study them because they are fairly simple, some are used as procedures in faster factoring methods, and because, since they sometimes work surprisingly quickly, we have to avoid numbers they can factor when choosing cryptographic keys that must not be factored. See the books by Crandall and Pomerance [33], Cohen [28], and Riesel [96] for more about these factoring algorithms.
