Paper 2012/639

Coarse-grained integer - Smooth? Rough? Both!

Daniel Loebenberger and Michael Nüsken

Abstract

We count ]B, C]-grained, k-factor integers which are simultaneously B-rough and C-smooth and have a fixed number k of prime factors. Our aim is to exploit explicit versions of the prime number theorem as much as possible to get good explicit bounds for the count of such integers. This analysis was inspired by certain inner procedures in the general number field sieve. The result should at least provide some insight in what happens there. We estimate the given count in terms of some recursively defined functions. Since they are still difficult to handle, only another approximation step reveals their orders. Finally, we use the obtained bounds to perform numerical experiments that show how good the desired count can be approximated for the parameters of the general number field sieve in the mentioned inspiring application.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
Smooth numbersrough numberscountingprime number theoremgeneral number field sieveRSA.
Contact author(s)
daniel @ bit uni-bonn de
History
2012-11-11: received
Short URL
https://ia.cr/2012/639
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/639,
      author = {Daniel Loebenberger and Michael Nüsken},
      title = {Coarse-grained integer - Smooth? Rough? Both!},
      howpublished = {Cryptology ePrint Archive, Paper 2012/639},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/639}},
      url = {https://eprint.iacr.org/2012/639}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.