International Association
for Cryptologic Research

In 1849, Dirichlet[5] 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 kth 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-smooth is prod_{p>B}[1-{1-(1-1/p)^n}^m] for m\ge2. We show that it is lower bounded by 1/zeta(s) for some s>1 if B>n^{m/(m-1)}, which completes the heuristic proof in the cryptanalysis of cryptographic multilinear maps by Cheon et al.[2]. We extend this result to the case of k-gcd: the probability is prod_{p>B}[1-{1-(1-1/p)^n(1+_{n}H_{1}/p+...+_{n}H_{k-1}p^{k-1})}^{m}], where _{n}H_{i}={n+i-1\choose i}.