Talk:Kronecker substitution
 | This article is rated Stub-class on Wikipedia's content assessment scale. It is of interest to the following WikiProjects: | ||||||||||
| |||||||||||
This article claims that this only works with powers of two. That's a misunderstanding. If you're going to do this using a computer, you'll use powers of two since it makes things easier on a binary computer. But that this works at all is more a property of multiplication. One can use any base. If you wanted to do this by hand you'd likely want to base ten. For instance.
If I have the polynomial p(x) = 3x2 + 2x + 1, and I evaluate it at x = 10, I find, p(10) = 321. This is then the coefficients of p(x), where the coefficient for the x2 term is in the hundreds place the coefficient for the x1 term is in the tens place and the coefficient of x0 is in the ones place.
Doing the same example using base 2: p(x) = 112x102 + 102x + 012. Evaluate at x = 1002 and I find p(1002) = 1110012. Here the top two bits are the coefficient of x10 and so on.
Since this works to project the coefficients of the polynomial into a single number we can then multiply those single numbers together to find the coefficients of the product of the polynomials. Again an example in base 10: p(x) = 3x2 + 2x + 1, let us compute q(x) = p(x) * p(x). First evaluate p(100) = 30201 (do you see the coefficients of p(x) in there again?). Then find 30201 * 30201 = 912100401. The coefficients of q(x) are then each group of two digits, as 09 12 10 04 01 or q(x) = 9x4 + 12x3 + 10x2 + 4x + 1.