Remote Access Mathematics of Computation
Green Open Access

Mathematics of Computation

ISSN 1088-6842(online) ISSN 0025-5718(print)



Asymptotic semismoothness probabilities

Authors: Eric Bach and Ren\a’e Peralta
Journal: Math. Comp. 65 (1996), 1701-1715
MSC (1991): Primary 11N25; Secondary 11Y05, 11Y70
MathSciNet review: 1370848
Full-text PDF

Abstract | References | Similar Articles | Additional Information

Abstract: We call an integer semismooth with respect to $y$ and $z$ if each of its prime factors is $\le y$, and all but one are $\le z$. Such numbers are useful in various factoring algorithms, including the quadratic sieve. Let $G(\alpha ,\beta )$ be the asymptotic probability that a random integer $n$ is semismooth with respect to $n^\beta $ and $n^\alpha $. We present new recurrence relations for $G$ and related functions. We then give numerical methods for computing $G$, tables of $G$, and estimates for the error incurred by this asymptotic approximation.

References [Enhancements On Off] (What's this?)

  • 1. E. Bach, How to generate factored random numbers, SIAM J. Comput., 17:179--193, 1988. MR 89e:11082
  • 2. ------, Exact analysis of a priority queue algorithm for random variate generation, Proc. 5th Ann. ACM-SIAM Symposium on Discrete Algorithms, pp. 48--52, 1994. MR 95h:65005
  • 3. N. G. de Bruijn, On the number of positive integers $\leq x$ and free of prime factors $> y$, Indag. Math., 13:50--60, 1951. MR 13:724e
  • 4. ------, The asymptotic behavior of a function occurring in the theory of primes, J. Indian Math. Soc. (N.S.), 15:25--32, 1951. MR 13:326f
  • 5. J.-M.-F. Chamayou, A probabilistic approach to a differential-difference equation arising in analytic number theory, Math. Comp., 27:197--203, 1973. MR 49:1725
  • 6. A. Y. Cheer and D. A. Goldston, A differential delay equation arising from the sieve of Eratosthenes, Math. Comp., 55:129--141, 1990. MR 90j:11091
  • 7. R. C. Griffiths, On the distribution of points in a Poisson Dirichlet process, J. Appl. Probab., 25:336--345, 1988. MR 89g:92026
  • 8. D. Knuth and L. Trabb Pardo, Analysis of a simple factorization algorithm, Theoret. Comput. Sci., 3:321--348, 1976. MR 58:16485
  • 9. G. Kolesnik and E. G. Straus, On the first occurrence of values of a character, Trans. Amer. Math. Soc., 246:385--394, 1978. MR 80c:10045
  • 10. A.K. Lenstra and M.S. Manasse, Factoring by electronic mail, In EUROCRYPT 89, volume 434 of Lecture Notes in Computer Science, pages 355--371. Springer-Verlag, 1990. MR 91i:11182
  • 11. A. Hildebrand, Integers free of large prime factors and the Riemann hypothesis, Mathematika, 31:258-271, 1984. MR 87a:11086
  • 12. R. Lambert, Computational aspects of discrete logarithms, Ph.D. thesis, University of Waterloo, 1996.
  • 13. J. van de Lune and E. Wattel, On the numerical solution of a differential-difference equation arising in analytic number theory, Math. Comp., 23:417--421, 1969. MR 40:1050
  • 14. G. Marsaglia, A. Zaman, and J. C. W. Marsaglia, Numerical solution of some classical differential-difference equations, Math. Comp., 53:191--201, 1989. MR 90h:65124
  • 15. P. L. Montgomery, An FFT extension of the elliptic curve method of factorization, Ph.D. thesis, University of California - Los Angeles, 1992.
  • 16. P. L. Montgomery and R. D. Silverman, An FFT extension to the $p-1$ factoring algorithm, Math. Comp., 54:839--854, 1990. MR 90j:11142
  • 17. K. K. Norton, Numbers with small prime factors, and the least $k$th power non-residue, Mem. Amer. Math. Soc., 106, 1971. MR 44:3948
  • 18. N. Patterson, Letter to Eric Bach, November 1988.
  • 19. C. Pomerance, The quadratic sieve factoring algorithm, In EUROCRYPT '84, volume 209 of Lecture Notes in Computer Science, pages 169-182. Springer-Verlag, 1985. MR 87d:11098
  • 20. V. Ramaswami, The number of positive integers $< x$ and free of prime divisors $> x^c$, and a problem of S.S. Pillai, Duke Math. J., 16:99--109, 1949. MR 10:597b
  • 21. C.-P. Schnorr and H. W. Lenstra, Jr., A Monte Carlo factoring algorithm with linear storage, Math. Comp., 43:289--311, 1984. MR 85d:11106
  • 22. L. Schoenfeld, Sharper bounds for the Chebyshev functions $\theta (x)$ and $\psi (x)$. II, Math. Comp., 30:337--360, 1976. MR 56:15581b
  • 23. E. C. Titchmarsh, The Theory of Functions. Second Edition, Oxford Univ. Press, 1939.

Similar Articles

Retrieve articles in Mathematics of Computation of the American Mathematical Society with MSC (1991): 11N25, 11Y05, 11Y70

Retrieve articles in all journals with MSC (1991): 11N25, 11Y05, 11Y70

Additional Information

Eric Bach
Affiliation: Computer Sciences Department, University of Wisconsin–Madison, 1210 W. Dayton St., Madison, Wisconsin 53706

Ren\a’e Peralta
Affiliation: Department of Electrical Engineering and Computer Science, University of Wisconsin–Milwaukee, P.O. Box 784, Milwaukee, Wisconsin 53201

Received by editor(s): December 14, 1992
Received by editor(s) in revised form: July 5, 1994, and October 23, 1995
Additional Notes: The first author was supported in part by NSF Grants DCR-8552596 and CCR-9208639. The second author was supported in part by NSF Grant CCR-9207204.
Article copyright: © Copyright 1996 American Mathematical Society

American Mathematical Society