Talk:Kronecker substitution

Untitled

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) = 3x² + 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 x² term is in the hundreds place the coefficient for the x¹ term is in the tens place and the coefficient of x⁰ is in the ones place.

Doing the same example using base 2: p(x) = 11₂x^10₂ + 10₂x + 01₂. Evaluate at x = 100₂ and I find p(100₂) = 111001₂. Here the top two bits are the coefficient of x¹⁰ 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) = 3x² + 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) = 9x⁴ + 12x³ + 10x² + 4x + 1. — Preceding unsigned comment added by 24.229.139.56 (talk) 13:43, 13 October 2017 (UTC)