On Reduction Probability Models in Lattice Sieving↗ (원문, 새 창)

본문 미리보기

In lattice sieving, the sphere model assumes that sieving elements are distributed close to or on a sphere with uniformly distributed direction. It is extensively used to predict how lattice sieving behaves. In the sphere model the probability that a random pair of vectors reduces is asymptotically $p_n={(3/4)}^{n/2}/\sqrt{3\pi n/8}$. In practice sieving algorithms have been observed to perform better than predicted by the sphere model. It is an open question how this gap behaves asymptotica