Suggestion for factorization of integers?
bearnol
Factoring modulo p:
"It is much easier to find the factors of an arbitrary polynomial of
degree n, ..., than to use any known method to find the factors of an
arbitrary n-bit ... number"
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?
J
Pubkeybreaker
> Knuth TAOCP Vol. 2 Section 4.6.2 Factorization of Polynomials:
> Factoring modulo p:
> "It is much easier to find the factors of an arbitrary polynomial of
> degree n, ..., than to use any known method to find the factors of an
> arbitrary n-bit ... number"
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.
evaluated
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
function
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
C-Z does
indirectly. The problem is that when working with an integer
factorization
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
that allows
lifting does not work in this instance. One reason it does not work
is that
over the local field, unique factorization fails. Consider, e.g. N
= 77.
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.
Pubkeybreaker
Another way to look at this question is in terms of CARRIES.
Polynomial
multiplication does not have any. Ordinary integer multiplication
does.
If one attempts to "reverse" the operation of multiplication by
setting
N = (a0 + a1*10 + a2*10^2 + ...) (b0 + b1 *10 + b2*10^2 ......)
etc
then setup up a system of equations in a0, a1, ..... b0, b1.... one
finds
that dealing with the carries gets in the way of solving the set of
equations
because one never knows whether a particular a_i * b_j will induce
a carry.
OTOH, because we do not have carries in polynomial multiplication, we
CAN set
up and solve a system of equations (essentially Berelkamp's method).
Andrew Taylor
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.)
David R Tribble
>> Knuth TAOCP Vol. 2 Section 4.6.2 Factorization of Polynomials:
>> Factoring modulo p:
>> "It is much easier to find the factors of an arbitrary polynomial of
>> degree n, ..., than to use any known method to find the factors of an
>> arbitrary n-bit ... number"
>> of powers of 10.
>
Pubkeybreaker wrote:
> 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.