Kronecker substitution とは

クロネッカー(Kronecker)置換は、未知の多項式の係数を単一の値で評価することによって、Leopold Kroneckerの名前をつけた技術です。 p(x)が整数係数を有する多項式であり、xがpの係数のいずれかより大きさが2のべき乗であるように選択された場合、各項の係数はバイナリから直接読み取られるp(x)の表現。
この方法の1つの応用は、多項式を乗算する計算上の問題を、整数を乗算する(潜在的に簡単な)問題に低減することである。 p(x)およびq(x)が既知の係数を有する多項式である場合、これらの係数を使用して、読み出される積p q(x)の係数が十分大きい2のべき乗であるxの値を決定することができる数p(x)q(x)のバイナリ表現から切り捨てる。 p(x)およびq(x)自体はpおよびqの係数から決定するのが簡単であるので、この結果は、多項式乗算が単一の2進乗算の時間に実行され得ることを示す。