**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.

**Category / Keywords: **gcd of products of positive integers, B-friable, k-gcd

**Original Publication**** (with minor differences): **Journal of Number Theory
**DOI: **10.1016/j.jnt.2016.04.013

**Date: **received 25 Mar 2016, last revised 9 Jun 2016

**Contact author: **doodoo1204 at snu ac kr

**Available format(s): **PDF | BibTeX Citation

**Version: **20160609:085624 (All versions of this report)

**Short URL: **ia.cr/2016/334

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]