Kronecker substitution is a technique named after
Leopold Kronecker
Leopold Kronecker (; 7 December 1823 – 29 December 1891) was a German mathematician who worked on number theory, algebra and logic. He criticized Georg Cantor's work on set theory, and was quoted by as having said, "'" ("God made the integers, ...
for determining the coefficients of an unknown
polynomial
In mathematics, a polynomial is an expression consisting of indeterminates (also called variables) and coefficients, that involves only the operations of addition, subtraction, multiplication, and positive-integer powers of variables. An example ...
by evaluating it at a single value. If ''p''(''x'') is a polynomial with integer coefficients, and ''x'' is chosen to be both a
power of two
A power of two is a number of the form where is an integer, that is, the result of exponentiation with number two as the base and integer as the exponent.
In a context where only integers are considered, is restricted to non-negativ ...
and larger in magnitude than any of the coefficients of ''p'', then the coefficients of each term of can be read directly out of the
binary representation
A binary number is a number expressed in the base-2 numeral system or binary numeral system, a method of mathematical expression which uses only two symbols: typically "0" (zero) and "1" (one).
The base-2 numeral system is a positional notation ...
of ''p''(''x'').
One application of this method is to
reduce
Reduction, reduced, or reduce may refer to:
Science and technology Chemistry
* Reduction (chemistry), part of a reduction-oxidation (redox) reaction in which atoms have their oxidation state changed.
** Organic redox reaction, a redox react ...
the computational problem of multiplying polynomials to the (potentially simpler) problem of multiplying integers.
If ''p''(''x'') and ''q''(''x'') are polynomials with known coefficients, then one can use these coefficients to determine a value of ''x'' that is a large enough power of two for the coefficients of the product ''pq''(''x'') to be able to be read off from the binary representation of the number ''p''(''x'')''q''(''x''). Since ''p''(''x'') and ''q''(''x'') are themselves straightforward to determine from the coefficients of ''p'' and ''q'', this result shows that polynomial multiplication may be performed in the time of a single binary multiplication.
[.]
See also
*
Kronecker product
In mathematics, the Kronecker product, sometimes denoted by ⊗, is an operation on two matrices of arbitrary size resulting in a block matrix. It is a generalization of the outer product (which is denoted by the same symbol) from vectors ...
References
Computer algebra
{{algebra-stub