An Algorithm for Ennola's Second Theorem and Counting Smooth Numbers in Practice

Abstract

Let Ψ( x, y ) count the number of positive integers n ≤ x such that every prime divisor of n is at most y . There are a number of ap-plications where values of Ψ( x, y ) are needed, such as in optimizing integer factoring and discrete logarithm algorithms [9, 19] and gener-ating factored smooth numbers uniformly at random [3]. Note that such numbers are useful in at least one post-quantum cryptography protocol [8, 21]. Given inputs x and y , what is the best way to estimate Ψ( x, y )? We address this problem in three ways: with a new algorithm to estimate Ψ( x, y ), with a performance improvement to an established algorithm, and with empirically based advice on how to choose an algorithm to estimate Ψ for the given inputs. Our new algorithm to estimate Ψ( x, y ) is based on Ennola’s second theorem [10], which applies when y < (log x ) 3 / 4 − (cid:15) for (cid:15) > 0. It takes O ( y 2 / log y ) arithmetic operations of precomputation and O ( y log y ) operations per evaluation of Ψ. We show how to speed up Algorithm HT [16], which is based on the saddle-point method of Hildebrand and Tenenbaum [14], by a factor proportional to log log x , by applying Newton’s method in a new way. And finally we give our empirical advice based on five algorithms to compute estimates for Ψ( x, y ). The challenge here is that the bound-1 aries of the ranges of applicability, as given in theorems, often include unknown constants or small values of (cid:15) > 0, for example, that cannot be programmed directly.