{"height":"190","type":"rich","description":"\u3057\u307e\u3063\u305f. n\u3092\u7d20\u6570\u306b\u3059\u308b\u3068FFT\u304c\u4f7f\u3048\u306a\u3044. \u3068\u306a\u308b\u3068, \u8a08\u7b97\u91cf\u306fO(n^2 log^c n)\u304b. \u30e1\u30ea\u30c3\u30c8\u304c\u6d88\u3048\u3066\u3057\u307e\u3046\u306a. \u76f4\u305d\u3046. \u76f4\u3063\u305f\u304b\u3068\u601d\u3063\u305f\u304c\u30c0\u30e1\u307d\u3044? n=2^k\u3068\u3057\u3066, x^n+1\u306fZ\u4e0a\u65e2\u7d04. \u307e\u305f2n\u304cq-1\u3092\u5272\u308a\u5207\u3089\u306a\u3044\u3068\u304d, Zq\u4e0a\u3067\u3082\u65e2\u7d04\u304b\u3068\u601d\u3063\u305f\u304c\u305d\u3046\u3067\u306f\u306a\u3044. \u6839\u306f\u6301\u305f\u306a\u3044\u3093\u3060\u304c\u306a\u3041. \u5b9f\u306f, n\u304c2\u51aa\u3067\u7121\u3044\u3068\u3057\u3066\u3082, N=2^k\u22672n\u3068\u3057\u3066\u304a\u304f\u3068\u51fa\u6765\u308b. F_q'[x]/(x^n-1)\u3067\u8a08\u7b97\u3057\u3066\u304b\u3089, \u623b\u3059\u30a4\u30e1\u30fc\u30b8.","author_name":"smoking186","provider_url":"https://hatena.blog","width":"100%","author_url":"https://blog.hatena.ne.jp/smoking186/","published":"2008-01-14 18:36:11","blog_url":"https://186.hatenablog.com/","provider_name":"Hatena Blog","title":"FFT\u3068\u304bNTT\u3068\u304b","url":"https://186.hatenablog.com/entry/20080114/1200303371","categories":[],"version":"1.0","html":"<iframe src=\"https://hatenablog-parts.com/embed?url=https%3A%2F%2F186.hatenablog.com%2Fentry%2F20080114%2F1200303371\" title=\"FFT\u3068\u304bNTT\u3068\u304b - 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>","image_url":null,"blog_title":"186 @ hatenablog"}