THE COMPLEXITY OF NUMBER-THEORETIC CONSTANTS

We show that Artin's constant and two related number-theoretic quantit ies can be computed to t bits of precision using t(3+o(1)) bit operati ons. The factor implied by the symbol o(1) depends on the cost of the underlying arithmetic, but for practical purposes can be taken as log t. As a by-product of this work, we estimate the complexity of computi ng Bernoulli numbers and evaluating the Riemann zeta function at posit ive integers. We also give examples of constants that seem hard to com pute, such as Brun's twin prime constant and the exact density of prim es for which a given base is a primitive root. This last cannot be com puted quickly unless factorization of certain RSA moduli is easy. (C) 1997 Elsevier Science B.V.