Střídání v týmu Kronecker - Kronecker substitution

Střídání v týmu Kronecker je technika pojmenovaná po Leopold Kronecker pro stanovení koeficientů neznámého polynomiální vyhodnocením na jednu hodnotu. Li str(X) je polynom s celočíselnými koeficienty a X je zvolen jako a síla dvou a větší než kterýkoli z koeficientů str, pak koeficienty každého členu z lze číst přímo z binární reprezentace z str(X).

Jednou z aplikací této metody je snížit výpočetní problém násobení polynomů na (potenciálně jednodušší) problém násobení celých čísel str(X) a q(X) jsou polynomy se známými koeficienty, pak lze pomocí těchto koeficientů určit hodnotu X to je dostatečně velká síla dvou na to, aby koeficienty produktu pq(X), které mají být odečteny z binární reprezentace čísla str(X)q(X). Od té doby str(X) a q(X) jsou samy o sobě přímo určitelné z koeficientů str a q, tento výsledek ukazuje, že polynomiální násobení může být provedeno v čase pro jediné binární násobení.^[1]

Viz také

Produkt Kronecker

Reference

^ von zur Gathen, Joachim; Gerhard, Jürgen (1999), Moderní počítačová algebra, Cambridge University Press, s. 243–244, ISBN 978-0-521-64176-0.

Tento algebra související článek je a pahýl. Wikipedii můžete pomoci pomocí rozšiřovat to.

[1] von zur Gathen, Joachim; Gerhard, Jürgen (1999), Moderní počítačová algebra, Cambridge University Press, s. 243–244, ISBN 978-0-521-64176-0.

[1]