Exponential Multiplication Schemes
Bernd Borchert, Klaus Reinhardt · 2006
We present an idea to describe a polynomial with 2 n distinct integer zeros by an n-tuple of integers via a scheme of n recurring equations. We call such an n-tuple an exponential multiplication scheme of size n. Exponential multiplication schemes of size 1, 2, 3, and 4 are presented. Under the assumption that fast exponential multiplication scheme generators exist we suggest a fast randomized heuristic for the factorization problem. 1 Exponential Multiplication Schemes Consider the following value x3, defined on x via two intermediate values x1 and x2: x1: = x(x − 11) x2: = x1(x1 − 28) x3: = x2(x2 − 180) The term x3, seen as an polynomial in x, is of degree 8 and has 8 different integer zeros: 0, 1, 2, 4, 7, 9, 10, 11. In other words: x3 = x(x − 1)(x − 2)(x − 4)(x − 7)(x − 9)(x − 10)(x − 11). This can be checked by comparing the two expansions of the two sides of the equation. More