Mathematics of Computation

Author(s): Eric Bach; Ren\a'e Peralta.
Journal: Math. Comp. 65 (1996), 1701-1715.
MSC (1991): Primary 11N25; Secondary 11Y05, 11Y70
Retrieve article in: PDF DVI PostScript
This article is available free of charge

Abstract: We call an integer semismooth with respect to $y$

and

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.

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 $\leq x$ and free of prime factors $> y$ ,

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 $p-1$ factoring algorithm,

Math. Comp., 54:839--854, 1990. MR 90j:11142

17.

K. K. Norton,

Numbers with small prime factors, and the least $k$ 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 $< x$ and free of prime divisors $> x^c$ , 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 $\theta (x)$ and $\psi (x)$ . 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 with MSC (1991): 11N25, 11Y05, 11Y70

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: 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.
Copyright of article: Copyright 1996, American Mathematical Society

			Journals Home Search Author Info Subscribe Tech Support Help
ISSN 1088-6842(e) ISSN 0025-5718(p)

Previous issue \| Table of contents \| Next issue Articles in press \| Recently posted articles \| Most recent issue \| All issues Previous Article \| Next Article


	Comments: webmaster@ams.org © Copyright 2008, American Mathematical Society Privacy Statement		Search the AMS