smoking186 https://blog.hatena.ne.jp/smoking186/ 186 @ hatenablog https://186.hatenablog.com/ crypt とはいえ多項式時間じゃなくって, 指数時間掛かる方ですけどね.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}だそうで… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2F186.hatenablog.com%2Fentry%2F20090811%2F1249994849" title=" 格子縮小アルゴリズムの進展 - 186 @ hatenablog" class="embed-card embed-blogcard" scrolling="no" frameborder="0" style="display: block; width: 100%; height: 190px; max-width: 500px; margin: 10px 0px;"></iframe> Hatena Blog https://hatena.blog 2009-08-11 21:47:29 rich https://186.hatenablog.com/entry/20090811/1249994849 1.0 100%