Welcome to the resource topic for 2016/334
Title:
Probability that the k-gcd of products of positive integers is B-friable
Authors: Jung Hee Cheon, 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.
ePrint: https://eprint.iacr.org/2016/334
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .