Paper 2016/334
Probability that the kgcd of products of positive integers is Bfriable
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 Bfriable 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}{m1}}, 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_{k1}}{p^{k1}})}^{m}], where _{n}H_{i} = n+i1 \choose i.
Metadata
 Available format(s)
 Publication info
 Published elsewhere. Minor revision. Journal of Number Theory
 DOI
 10.1016/j.jnt.2016.04.013
 Keywords
 gcd of products of positive integersBfriablekgcd
 Contact author(s)
 doodoo1204 @ snu ac kr
 History
 20160609: revised
 20160330: received
 See all versions
 Short URL
 https://ia.cr/2016/334
 License

CC BY
BibTeX
@misc{cryptoeprint:2016/334, author = {Jung Hee Cheon and Duhyeong Kim}, title = {Probability that the kgcd of products of positive integers is Bfriable}, 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} }