But surely any integer, m, can be written (in denary) as a polynomial
of powers of 10.
So if we just take any p>m, why can't we factor (integer) m using (our
choice of) Berlekamp/Cantor-Zassenhaus/LLL?
If r(x) = p(x)q(x), then this must hold true for all values of x.
This places strong restrictions on what the factors can be.
> But surely any integer, m, can be written (in denary) as a polynomial
> of powers of 10.
It can be written as a particular INSTANCE of a polynomial. i.e.
at one point. But it is nor a function.
> So if we just take any p>m, why can't we factor (integer) m using (our
> choice of) Berlekamp/Cantor-Zassenhaus/LLL?
Because integers are not functions. Berelamp/C-Z/LLL work over
fields, not number fields.
If you want to get deeper one can explain it as follows:
One can take a polynomial function (over some global field), reduce
it over a
local field, or several local fields, deduce some information, and
then LIFT the
result back to the global field. This is what Berlekamp does and what
indirectly. The problem is that when working with an integer
we can not reduce the integer over local fields, factor the integer
in the local fields,
then lift the result back to a global field. The (Minkowski) theorem
lifting does not work in this instance. One reason it does not work
over the local field, unique factorization fails. Consider, e.g. N
Reduce it (say) mod 13. We get N = 12 mod 13. But now N has many
(count the units in Z/13Z*)
factorizations mod 13. There is no way to (say) lift the
factorization N = 12 = 5*5 mod 13
back to Z. e.g. we also have N = 12 = 2*6 = 3*4 = .... mod 13.
There is no way to take
an integer N, reduce it modulo multiple primes, factor N modulo
those primes, and then
use (say) the CRT to paste the results together.
Another way to look at this question is in terms of CARRIES.
multiplication does not have any. Ordinary integer multiplication
If one attempts to "reverse" the operation of multiplication by
N = (a0 + a1*10 + a2*10^2 + ...) (b0 + b1 *10 + b2*10^2 ......)
then setup up a system of equations in a0, a1, ..... b0, b1.... one
that dealing with the carries gets in the way of solving the set of
because one never knows whether a particular a_i * b_j will induce
OTOH, because we do not have carries in polynomial multiplication, we
up and solve a system of equations (essentially Berelkamp's method).
To give a simple concrete example, the polynomial
x^2 + x + 1 is irreducible over the integers, but if x=10
its value is 111 = 3*37, (whereas if x=2 its value is
the prime 7.)
> It can be written as a particular INSTANCE of a polynomial. i.e.
> evaluated at one point. But it is not a function.
Another point to make is that the factors of a polynomial are
themselves polynomials (of lesser degree), not plain numbers.