RUS  ENG
Full version
JOURNALS // Izvestiya Vysshikh Uchebnykh Zavedenii. Matematika // Archive

Izv. Vyssh. Uchebn. Zaved. Mat., 2017 Number 11, Pages 60–67 (Mi ivm9301)

This article is cited in 2 papers

On power smooth numbers

F. F. Sharifullina

Kazan Federal University, 18 Kremlyovskaya str., Kazan, 420008 Russia

Abstract: A natural number $n$ is called the $y$-power smooth for some positive number $y$ if every prime power dividing $n$ is bounded from above by the number $y$. Let us denote by $\psi^*(x,y)$ the amount of $y$-power smooth integers in the range from $0$ to $x$. In this paper we investigate the function $\psi^*(x,y)$ and $y$-power smooth numbers in general. We derive formulas for finding exact calculation of $\psi^*(x,y)$ for large $x$ and relatively small $y$, and give theoretical estimates for this function and for function of the greatest powersmooth number. This results can be used in the cryptography and number theory to estimate the convergence of the factorization algorithms.

Keywords: smooth integers, powersmooth integers, factorization, estimates for cryptographic algorithms, Lenstra elliptic curve factorization method, Pollard's $(p-1)$-factorization algorithm, RSA.

UDC: 519.7

Received: 27.06.2016


 English version:
Russian Mathematics (Izvestiya VUZ. Matematika), 2017, 61:11, 53–59

Bibliographic databases:


© Steklov Math. Inst. of RAS, 2024