Studying the Bounds on Required Samples Numbers for Solving the General Approximate Common Divisors Problem
Xiaoling Yu, Yuntao Wang, Chungen Xu, Tsuyoshi Takagi · 2018
General approximate common divisors (GACD) problem was proposed which can be used to construct Fully homomophic encryption scheme based on its hardness. So the research on its hardness plays a vital role in cryptography. In the paper, we study the algorithm proposed by Ding and Tao in 2014 to solve GACD problem, and get a new bound of GACD sample numbers t ≥ 5/3(η-ρ-√(η-ρ)2-1.2γ) using Geometric Series Assumption under some reasonable conditions, here γ,η,ρ are parameters in GACD problem. We also give some experimental results about success probability of Ding and Tao's algorithm under our bound for corresponding GACD parameters and comprision with success probability of algorithm under the bound of Gebregiyorgis.