Asymptotic semismoothness probabilities
Open Access
- 1 October 1996
- journal article
- Published by American Mathematical Society (AMS) in Mathematics of Computation
- Vol. 65 (216) , 1701-1715
Abstract
We call an integer semismooth with respect to y y and z z if each of its prime factors is ≤ y \le y , and all but one are ≤ z \le z . Such numbers are useful in various factoring algorithms, including the quadratic sieve. Let G ( α , β ) G(\alpha ,\beta ) be the asymptotic probability that a random integer n n is semismooth with respect to n β n^\beta and n α n^\alpha . We present new recurrence relations for G G and related functions. We then give numerical methods for computing G G , tables of G G , and estimates for the error incurred by this asymptotic approximation.Keywords
This publication has 14 references indexed in Scilit:
- A Differential Delay Equation Arising from the Sieve of EratosthenesMathematics of Computation, 1990
- An FFT Extension to the P - 1 Factoring AlgorithmMathematics of Computation, 1990
- Numerical Solution of Some Classical Differential-Difference EquationsMathematics of Computation, 1989
- Integers free of large prime factors and the Riemann hypothesisMathematika, 1984
- A Monte Carlo Factoring Algorithm With Linear StorageMathematics of Computation, 1984
- On the First Occurrence of Values of a CharacterTransactions of the American Mathematical Society, 1978
- Analysis of a simple factorization algorithmTheoretical Computer Science, 1976
- A Probabilistic Approach to a Differential-Difference Equation Arising in Analytic Number TheoryMathematics of Computation, 1973
- Numbers with small prime factors, and the least 𝑘th power non-residueMemoirs of the American Mathematical Society, 1971
- On the Numerical Solution of a Differential-Difference Equation Arising in Analytic Number TheoryMathematics of Computation, 1969