Approximately counting semismooth integers

DOI10.1145/2465506.2465933MaRDI QIDQ2963209zbMATH OpenOpenAlexFDO

Authors Eric Bach, Jonathan P. Sorenson

Publication date 10 February 2017

Published in Proceedings of the 38th International Symposium on Symbolic and Algebraic Computation (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1301.5293

zbMATH Keywords

integer factoringnumber theoretic algorithmssemismooth numberssmooth numbers

Mathematics Subject Classification ID

Factorization (11Y05) Number-theoretic algorithms; complexity (11Y16) Symbolic computation and algebraic computation (68W30)

Abstract: An integer $n$ is $(y,z)$-semismooth if $n=pm$ where $m$ is an integer with all prime divisors $ley$ and $p$ is 1 or a prime $lez$. arge quantities of semismooth integers are utilized in modern integer factoring algorithms, such as the number field sieve, that incorporate the so-called large prime variant. Thus, it is useful for factoring practitioners to be able to estimate the value of $Psi(x,y,z)$, the number of $(y,z)$-semismooth integers up to $x$, so that they can better set algorithm parameters and minimize running times, which could be weeks or months on a cluster supercomputer. In this paper, we explore several algorithms to approximate $Psi(x,y,z)$ using a generalization of Buchstab's identity with numeric integration.

Recommendations

• Asymptotic semismoothness probabilities
• On the number of semismooth integers
• An algorithm for counting smooth integers
• scientific article; zbMATH DE number 1186936
• scientific article; zbMATH DE number 1643952

Cited in

(6)

• Approximating the number of integers without large prime factors
• Two compact incremental prime sieves
• Distribution of \(k\)-semismooth integers
• Asymptotic semismoothness probabilities
• A note on low order assumptions in RSA groups
• On the number of semismooth integers

This page was built for publication: Approximately counting semismooth integers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2963209)