COUNTING THE INTEGERS FACTORABLE VIA CYCLOTOMIC METHODS

Let F(x, t, A) denote the number of integers up to x that algorithm A can completely factor with probability at least 1/2 using at most t ar ithmetic operations with integers at most x. Ln this paper we analyze F(x, t, A) for the p - 1 and p + 1 integer factoring algorithms based on the first two cyclotomic polynomials. We show that the p +/- 1 algo rithms each factor a positive proportion more integers in t steps than trial division but far fewer than the elliptic curve method. (C) 1995 Academic Press, Inc.