**Fast Algorithm to solve a family of SIS problem with $l_\infty$ norm**

*Jintai Ding*

**Abstract: **In this paper, we present a new algorithm, such that, for the
small integer solution (SIS) problem, if the solution is bounded ( by an integer $\beta$
in $l_\infty$ norm, which we call a bounded SIS (BSIS) problem, {\it and if the difference between the row dimension $n$ and the column dimension $m$ of the corresponding matrix is relatively small with respect the row dimension $m$}, we can solve it easily with a complexity of polynomial in $m$.

**Category / Keywords: **foundations / SIS, Lattice, $l_\infty$ norm bounded, multivariate polynomials, linerization

**Date: **received 15 Nov 2010

**Contact author: **jintai ding at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20101118:032633 (All versions of this report)

**Short URL: **ia.cr/2010/581

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]