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

DOI:
https://doi.org/10.1090/S0025-5718-96-00775-2

MathSciNet review:
1370848

Full-text PDF

Abstract | References | Similar Articles | Additional Information

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

**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 and free of prime factors ,*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 factoring algorithm,*Math. Comp.*, 54:839--854, 1990. MR**90j:11142****17.**K. K. Norton, Numbers with small prime factors, and the least 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 and free of prime divisors , 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 and . II,*Math. Comp.*, 30:337--360, 1976. MR**56:15581b****23.**E. C. Titchmarsh,*The Theory of Functions.*Second Edition, Oxford Univ. Press, 1939.

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

Email:
bach@cs.wisc.edu

**Ren\a’e Peralta**

Affiliation:
Department of Electrical Engineering and Computer Science, University of Wisconsin–Milwaukee, P.O. Box 784, Milwaukee, Wisconsin 53201

Email:
peralta@cs.uwm.edu

DOI:
https://doi.org/10.1090/S0025-5718-96-00775-2

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