Paper 2016/334

Probability that the k-gcd of products of positive integers is B-friable

Jung Hee Cheon and Duhyeong Kim

Abstract

In 1849, Dirichlet~\cite{D49} proved that the probability that two positive integers are relatively prime is 1/\zeta(2). Later, it was generalized into the case that positive integers has no nontrivial $k$th power common divisor. In this paper, we further generalize this result: the probability that the gcd of m products of n positive integers is B-friable is \prod_{p>B}[1-{1-(1-\frac{1}{p})^{n}}^{m}] for m >= 2. We show that it is lower bounded by \frac{1}{\zeta(s)} for some s>1 if B>n^{\frac{m}{m-1}}, which completes the heuristic proof in the cryptanalysis of cryptographic multilinear maps by Cheon et al.~\cite{CHLRS15}. We extend this result to the case of $k$-gcd: the probability is \prod_{p>B}[1-{1-(1-\frac{1}{p})^{n}(1+\frac{_{n}H_{1}}{p}+\cdot\cdot\cdot+\frac{_{n}H_{k-1}}{p^{k-1}})}^{m}], where _{n}H_{i} = n+i-1 \choose i.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. Journal of Number Theory
DOI
10.1016/j.jnt.2016.04.013
Keywords
gcd of products of positive integersB-friablek-gcd
Contact author(s)
doodoo1204 @ snu ac kr
History
2016-06-09: revised
2016-03-30: received
See all versions
Short URL
https://ia.cr/2016/334
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/334,
      author = {Jung Hee Cheon and Duhyeong Kim},
      title = {Probability that the k-gcd of products of positive integers is B-friable},
      howpublished = {Cryptology ePrint Archive, Paper 2016/334},
      year = {2016},
      doi = {10.1016/j.jnt.2016.04.013},
      note = {\url{https://eprint.iacr.org/2016/334}},
      url = {https://eprint.iacr.org/2016/334}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.