podstawienie Kroneckera
Podstawianie Kroneckera to technika nazwana na cześć Leopolda Kroneckera , służąca do określania współczynników nieznanego wielomianu poprzez oszacowanie go na jednej wartości. Jeśli p ( x ) jest wielomianem o współczynnikach całkowitych, a x jest zarówno potęgą dwójki , jak i większym niż którykolwiek ze współczynników p , to współczynniki każdego składnika można odczytać bezpośrednio z binarnego reprezentacja p ( x ) .
Jednym z zastosowań tej metody jest zredukowanie problemu obliczeniowego mnożenia wielomianów do (potencjalnie prostszego) problemu mnożenia liczb całkowitych. Jeśli p ( x ) i q ( x ) są wielomianami o znanych współczynnikach, to można użyć tych współczynników do wyznaczenia wartości x , która jest wystarczająco dużą potęgą dwójki, aby współczynniki iloczynu pq ( x ) mogły można odczytać z binarnej reprezentacji liczby p ( x ) q ( x ). Ponieważ p ( x ) i q ( x ) same są łatwe do wyznaczenia ze współczynników p i q , wynik ten pokazuje, że mnożenie wielomianowe może być wykonane w czasie pojedynczego mnożenia binarnego.
Zobacz też