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 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.**Eric Bach,*How to generate factored random numbers*, SIAM J. Comput.**17**(1988), no. 2, 179–193. Special issue on cryptography. MR**935336**, 10.1137/0217012**2.**Eric Bach,*Exact analysis of a priority queue algorithm for random variate generation*, Proceedings of the Fifth Annual ACM-SIAM Symposium on Discrete Algorithms (Arlington, VA, 1994) ACM, New York, 1994, pp. 48–56. MR**1285150****3.**N. G. de Bruijn,*On the number of positive integers ≤𝑥 and free of prime factors >𝑦*, Nederl. Acad. Wetensch. Proc. Ser. A.**54**(1951), 50–60. MR**0046375****4.**N. G. de Bruijn,*The asymptotic behaviour of a function occurring in the theory of primes*, J. Indian Math. Soc. (N.S.)**15**(1951), 25–32. MR**0043838****5.**Jean-Marie-François Chamayou,*A probabilistic approach to a differential-difference equation arising in analytic number theory*, Math. Comp.**27**(1973), 197–203. MR**0336952**, 10.1090/S0025-5718-1973-0336952-X**6.**A. Y. Cheer and D. A. Goldston,*A differential delay equation arising from the sieve of Eratosthenes*, Math. Comp.**55**(1990), no. 191, 129–141. MR**1023043**, 10.1090/S0025-5718-1990-1023043-8**7.**R. C. Griffiths,*On the distribution of points in a Poisson Dirichlet process*, J. Appl. Probab.**25**(1988), no. 2, 336–345. MR**938197****8.**Donald E. Knuth and Luis Trabb Pardo,*Analysis of a simple factorization algorithm*, Theoret. Comput. Sci.**3**(1976/77), no. 3, 321–348. MR**0498355****9.**G. Kolesnik and E. G. Straus,*On the first occurrence of values of a character*, Trans. Amer. Math. Soc.**246**(1978), 385–394. MR**515545**, 10.1090/S0002-9947-1978-0515545-6**10.**Arjen K. Lenstra and Mark S. Manasse,*Factoring by electronic mail*, Advances in cryptology—EUROCRYPT ’89 (Houthalen, 1989) Lecture Notes in Comput. Sci., vol. 434, Springer, Berlin, 1990, pp. 355–371. MR**1083962**, 10.1007/3-540-46885-4_35**11.**Adolf Hildebrand,*Integers free of large prime factors and the Riemann hypothesis*, Mathematika**31**(1984), no. 2, 258–271 (1985). MR**804201**, 10.1112/S0025579300012481**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**(1969), 417–421. MR**0247789**, 10.1090/S0025-5718-1969-0247789-3**14.**George Marsaglia, Arif Zaman, and John C. W. Marsaglia,*Numerical solution of some classical differential-difference equations*, Math. Comp.**53**(1989), no. 187, 191–201. MR**969490**, 10.1090/S0025-5718-1989-0969490-3**15.**P. L. Montgomery,*An FFT extension of the elliptic curve method of factorization*, Ph.D. thesis, University of California - Los Angeles, 1992.**16.**Peter L. Montgomery and Robert D. Silverman,*An FFT extension to the 𝑃-1 factoring algorithm*, Math. Comp.**54**(1990), no. 190, 839–854. MR**1011444**, 10.1090/S0025-5718-1990-1011444-3**17.**Karl K. Norton,*Numbers with small prime factors, and the least 𝑘th power non-residue*, Memoirs of the American Mathematical Society, No. 106, American Mathematical Society, Providence, R.I., 1971. MR**0286739****18.**N. Patterson, Letter to Eric Bach, November 1988.**19.**Carl Pomerance,*The quadratic sieve factoring algorithm*, Advances in cryptology (Paris, 1984) Lecture Notes in Comput. Sci., vol. 209, Springer, Berlin, 1985, pp. 169–182. MR**825590**, 10.1007/3-540-39757-4_17**20.**V. Ramaswami,*The number of positive integers ≤𝑥 and free of prime divisors >𝑥^{𝑐}, and a problem of S. S. Pillai*, Duke Math. J.**16**(1949), 99–109 (German). MR**0029413****21.**C.-P. Schnorr and H. W. Lenstra Jr.,*A Monte Carlo factoring algorithm with linear storage*, Math. Comp.**43**(1984), no. 167, 289–311. MR**744939**, 10.1090/S0025-5718-1984-0744939-5**22.**Lowell Schoenfeld,*Sharper bounds for the Chebyshev functions 𝜃(𝑥) and 𝜓(𝑥). II*, Math. Comp.**30**(1976), no. 134, 337–360. MR**0457374**, 10.1090/S0025-5718-1976-0457374-X**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