Cryptology ePrint Archive: Report 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.

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 ]