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 Free Access

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?)

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