Authors : Konstantin L. Maksimov and Shamil T. Ishmukhametov
Abstract: An integer n>0 is called y-smooth if p≤y condition is performed for every prime divisor. If the boundary y is considerably smaller than the number n, then such a number is the product of a large number of small prime factors (it is a smooth one) as opposed to simple numbers which are not decomposable into simpler factors. Smooth numbers play an important role in the theory of numbers and cryptography. In particular, the fastest modern algorithm of integer factorization (decomposition into a product of prime factors) is based on the idea of a large number of y-smooth numbers finding where y is the boundary of the so-called factor base which is much less than factorisable number n. Let’s denote the number of y-smooth numbers via ψ(x, y) within the interval from 1 to x. The calculation of ψ(x, y) function is a complex computational problem, therefore, the researchers proposed various algorithms for the approximate calculation of this function for different ratios of the argument values. In this study, we describe a new polynomial algorithm for the approximation of ψ(x, y) function concerning the number of y-smooth numbers within the interval from 1 to x. The algorithm is based on the formula of Euler-Maclaurin summation and provides a sufficiently high level of accuracy. The study shows the experimental data for the calculation of smooth numbers number for the argument x≤1025 and y≤log x.
Konstantin L. Maksimov and Shamil T. Ishmukhametov, 2015. About Algorithm of Smooth Numbers Calculation. Research Journal of Applied Sciences, 10: 376-380.