{"categories":["crypt"],"image_url":null,"type":"rich","published":"2009-08-11 21:47:29","author_url":"https://blog.hatena.ne.jp/smoking186/","blog_title":"186 @ hatenablog","provider_name":"Hatena Blog","html":"<iframe src=\"https://hatenablog-parts.com/embed?url=https%3A%2F%2F186.hatenablog.com%2Fentry%2F20090811%2F1249994849\" title=\" \u683c\u5b50\u7e2e\u5c0f\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u9032\u5c55 - 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>","author_name":"smoking186","provider_url":"https://hatena.blog","description":"\u3068\u306f\u3044\u3048\u591a\u9805\u5f0f\u6642\u9593\u3058\u3083\u306a\u304f\u3063\u3066, \u6307\u6570\u6642\u9593\u639b\u304b\u308b\u65b9\u3067\u3059\u3051\u3069\u306d.Ajtai, Kumar, Sivakumar (STOC 2001) \u3092\u771f\u9762\u76ee\u306b\u89e3\u6790\u3057\u305f\u3089\u6642\u9593\u8a08\u7b97\u91cf2^{5.9n}, \u7a7a\u9593\u8a08\u7b97\u91cf2^{2.95n}\u3060\u3063\u305f\u3088\u3068Nguyen and Vidick\u304c\u5831\u544a\u3057\u305f\u306e\u304c\u4eca\u5e74\u306e\u8a71 (J. Math. Crypt. 2009). Voulgaris and Micciancio\u66f0\u304f, \u6642\u9593\u8a08\u7b97\u91cf2^{3.199n}, \u7a7a\u9593\u8a08\u7b97\u91cf2^{1.325n}\u307e\u3067\u6539\u826f\u51fa\u6765\u307e\u3057\u305f. \u307e\u305f\u30d2\u30e5\u30fc\u30ea\u30b9\u30c6\u30a3\u30c3\u30af\u306a\u6539\u826f\u6848\u3082\u793a\u3057\u3066\u3044\u3066, \u305d\u3063\u3061\u306f\u5b9f\u9a13\u7684\u306b\u6642\u9593\u8a08\u7b97\u91cf2^{0.48n}, \u7a7a\u9593\u8a08\u7b97\u91cf2^{0.21n}\u3060\u305d\u3046\u3067\u2026","title":" \u683c\u5b50\u7e2e\u5c0f\u30a2\u30eb\u30b4\u30ea\u30ba\u30e0\u306e\u9032\u5c55","height":"190","blog_url":"https://186.hatenablog.com/","version":"1.0","url":"https://186.hatenablog.com/entry/20090811/1249994849","width":"100%"}