格子縮小アルゴリズムの進展
とはいえ多項式時間じゃなくって, 指数時間掛かる方ですけどね.
Ajtai, Kumar, Sivakumar (STOC 2001) を真面目に解析したら時間計算量2^{5.9n}, 空間計算量2^{2.95n}だったよとNguyen and Vidickが報告したのが今年の話 (J. Math. Crypt. 2009).
Voulgaris and Micciancio曰く, 時間計算量2^{3.199n}, 空間計算量2^{1.325n}まで改良出来ました. またヒューリスティックな改良案も示していて, そっちは実験的に時間計算量2^{0.48n}, 空間計算量2^{0.21n}だそうです (ECCC - TR09-065).
最適化の人とか向けですかね, これ.