Mathematics of Computation of the American Mathematical Society

	Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
\|

			Journals Home Search Author Info Subscribe Tech Support My Subscriptions Browser Compatibility Info Help
ISSN 1088-6842(online) ISSN 0025-5718(print)

Previous issue | This issue | Most recent issue | All issues (1943–Present) | Next issue
Previous article | Articles in press | Recently posted articles | Next article

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.

1. Eric Bach, How to generate factored random numbers, SIAM J. Comput. 17 (1988), no. 2, 179–193. Special issue on cryptography. MR 935336 (89e:11082), http://dx.doi.org/10.1137/0217012
2. Eric Bach, Exact analysis of a priority queue algorithm for random variate generation, Algorithms (Arlington, VA, 1994) ACM, New York, 1994, pp. 48–56. MR 1285150 (95h:65005)
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 (13,724e)
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 (13,326f)
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 (49 #1725), http://dx.doi.org/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 (90j:11091), http://dx.doi.org/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 (89g:92026)
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 (58 #16485)
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 (80c:10045), http://dx.doi.org/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 (91i:11182), http://dx.doi.org/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 (87a:11086), http://dx.doi.org/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 (40 #1050), http://dx.doi.org/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 (90h:65124), http://dx.doi.org/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 (90j:11142), http://dx.doi.org/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 (44 #3948)
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 (87d:11098), http://dx.doi.org/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 (10,597b)
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 (85d:11106), http://dx.doi.org/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 (56 #15581b), http://dx.doi.org/10.1090/S0025-5718-1976-0457374-X
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
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: http://dx.doi.org/10.1090/S0025-5718-96-00775-2
PII: S 0025-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

Previous issue | This issue | Most recent issue | All issues (1943–Present) | Next issue
Previous article | Articles in press | Recently posted articles | Next article