Asymptotic semismoothness probabilities
HTML articles powered by AMS MathViewer
- by Eric Bach and René Peralta PDF
- Math. Comp. 65 (1996), 1701-1715 Request permission
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
- Eric Bach, How to generate factored random numbers, SIAM J. Comput. 17 (1988), no. 2, 179–193. Special issue on cryptography. MR 935336, DOI 10.1137/0217012
- 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
- C. J. Everett Jr., Annihilator ideals and representation iteration for abstract rings, Duke Math. J. 5 (1939), 623–627. MR 13
- C. J. Everett Jr., Annihilator ideals and representation iteration for abstract rings, Duke Math. J. 5 (1939), 623–627. MR 13
- 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 336952, DOI 10.1090/S0025-5718-1973-0336952-X
- 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, DOI 10.1090/S0025-5718-1990-1023043-8
- R. C. Griffiths, On the distribution of points in a Poisson Dirichlet process, J. Appl. Probab. 25 (1988), no. 2, 336–345. MR 938197, DOI 10.1017/s0021900200040973
- Donald E. Knuth and Luis Trabb Pardo, Analysis of a simple factorization algorithm, Theoret. Comput. Sci. 3 (1976/77), no. 3, 321–348. MR 498355, DOI 10.1016/0304-3975(76)90050-5
- 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, DOI 10.1090/S0002-9947-1978-0515545-6
- 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, DOI 10.1007/3-540-46885-4_{3}5
- Adolf Hildebrand, Integers free of large prime factors and the Riemann hypothesis, Mathematika 31 (1984), no. 2, 258–271 (1985). MR 804201, DOI 10.1112/S0025579300012481
- R. Lambert, Computational aspects of discrete logarithms, Ph.D. thesis, University of Waterloo, 1996.
- 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 247789, DOI 10.1090/S0025-5718-1969-0247789-3
- 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, DOI 10.1090/S0025-5718-1989-0969490-3
- P. L. Montgomery, An FFT extension of the elliptic curve method of factorization, Ph.D. thesis, University of California - Los Angeles, 1992.
- Peter L. Montgomery and Robert D. Silverman, An FFT extension to the $P-1$ factoring algorithm, Math. Comp. 54 (1990), no. 190, 839–854. MR 1011444, DOI 10.1090/S0025-5718-1990-1011444-3
- Karl K. Norton, Numbers with small prime factors, and the least $k$th power non-residue, Memoirs of the American Mathematical Society, No. 106, American Mathematical Society, Providence, R.I., 1971. MR 0286739
- N. Patterson, Letter to Eric Bach, November 1988.
- 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, DOI 10.1007/3-540-39757-4_{1}7
- Morgan Ward, Ring homomorphisms which are also lattice homomorphisms, Amer. J. Math. 61 (1939), 783–787. MR 10, DOI 10.2307/2371336
- 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, DOI 10.1090/S0025-5718-1984-0744939-5
- J. Barkley Rosser and Lowell Schoenfeld, Sharper bounds for the Chebyshev functions $\theta (x)$ and $\psi (x)$, Math. Comp. 29 (1975), 243–269. MR 457373, DOI 10.1090/S0025-5718-1975-0457373-7
- E. C. Titchmarsh, The Theory of Functions. Second Edition, Oxford Univ. Press, 1939.
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é 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
- 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.
- © Copyright 1996 American Mathematical Society
- 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