Asymptotic semismoothness probabilities

Bach, Eric; Peralta, René

doi:10.1090/S0025-5718-96-00775-2

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.