18 views

Skip to first unread message

Dec 7, 2010, 9:58:50 AM12/7/10

to

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"

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

Dec 7, 2010, 10:20:03 AM12/7/10

to

On Dec 7, 9:58 am, bearnol <bear...@gmail.com> wrote:

> 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"

> 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.

Dec 7, 2010, 10:25:47 AM12/7/10

to

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).

Dec 7, 2010, 1:02:32 PM12/7/10

to

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.)

Dec 8, 2010, 12:04:24 PM12/8/10

to

bearnol wrote:

>> 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"

>> 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"

>> But surely any integer, m, can be written (in denary) as a polynomial

>> of powers of 10.

>

>> 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.

Reply all

Reply to author

Forward

0 new messages

Search

Clear search

Close search

Google apps

Main menu