techmedia-think https://blog.hatena.ne.jp/techmedia-think/ Develop with pleasure! https://techmedia-think.hatenablog.com/ Cryptography 最近の主要なゼロ知識証明システムで、多数の多項式の演算が必要になる。多項式の加算であれば、単に同じ次数の係数同士を加算するだけなので、必要な演算回数は係数の個数分。n-1次の多項式であればO(n)の加算で済む。一方、多項式の乗算の場合、その結果の次数が同じ項をまとめる必要があり、単純に計算するとO(n2)の乗算と同程度の加算が必要になる。 たとえば、2つの3次多項式を とした場合、その積は、 となる。 畳み込み演算 2つの多項式の積の各係数は、各多項式の係数列の畳み込みで求めることができる。具体的には、f(x)のk次の係数は、 で計算できる（が存在しない場合は0とみなす）。 たとえば、上記の2… 190 <iframe src="https://hatenablog-parts.com/embed?url=https%3A%2F%2Ftechmedia-think.hatenablog.com%2Fentry%2F2025%2F12%2F27%2F180447" title="数論変換（NTT） - Develop with pleasure!" 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 2025-12-27 18:04:47 rich https://techmedia-think.hatenablog.com/entry/2025/12/27/180447 1.0 100%