An integer n is (y,z)-semismooth if n=pm where m is an integer with all prime divisors ≥ y and p is 1 or a prime ≥ z. Large quantities of semismooth integers are utilized in modern integer factoring algorithms, such as the number field sieve, that incorporate the so-called large prime variant. Thus, it is useful for factoring practitioners to be able to estimate the value of Ψ(x,y,z), the number of (y,z)-semismooth integers up to x, so that they can better set algorithm parameters and minimize running times, which could be weeks or months on a cluster supercomputer. In this paper, we explore several algorithms to approximate Ψ(x,y,z) using a generalization of Buchstab's identity with numeric integration.

Article An analysis of Lehmer's Euclidean GCD algorithm Share on Author: Jonathan Sorenson Department of Mathematics and Computer Science, Butler University, 4600 Sunset Ave., Indianapolis, Indiana Department of Mathematics and Computer Science, Butler University, 4600 Sunset Ave., Indianapolis, IndianaView Profile Authors Info & Claims ISSAC '95: Proceedings of the 1995 international symposium on Symbolic and algebraic computationApril 1995 Pages 254–258https://doi.org/10.1145/220346.220378Published:01 April 1995 12citation643DownloadsMetricsTotal Citations12Total Downloads643Last 12 Months14Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteGet Access