# Gao: Factoring Polynomials under GRH

We consider the following problem: Given a prime and , where , is separable, and splits completely, find a proper factor of (in deterministic polynomial time).

Berlekamp algorithm reduces general polynomials in ( a power of ) to polynomials of the above type. Without GRH, we are stuck already at . So throughout we assume GRH.

Ronyai (1988) shows that this can be done in time , or more precisely whenever , , so in particular if is even can be split in deterministic polynomial time. Bach, von zur Gathen and Lenstra (2001) give an algorithm with polynomial time if is smooth for some where is the th cyclotomic polynomial. Evdokimov (1994) shows for any and , can be factored in time . We discuss work in Cheng and Huang (2000), and Gao (2001) plus some unpublished results. GRH will be needed only to compute an th nonresidue in or in its extensions, for .

Definition. An algebra is called elementary if for some .

Let be elementary over . Then we write where the are primitive idempotents, which are unique in .

Fact.

1. If , then can be defined properly and can be computed in deterministic polynomial time for any elementary algebra .

2. If is monic, separable (i.e. ), and splits completely, then is also elementary. Given a zerodivisor in , one can compute a proper factor of or a zerodivisor of .

3. Given a nontrivial ring endomorphism of over , one can find a proper factor of or a zerodivisor of . (Need GRH to get an th nonresidue, for , where .)

4. Given a quadratic nonresidue in , there is a deterministic polynomial time algorithm for computing square roots in . More precisely we have a function , such that (i) is a square root of if is a square in , (ii) if , , then

and (iii) for , . For example, if , then we can take , and for ,

Now let be separable, so that

To factor , define

which is the tensor product of with itself. Then is an elementary algebra. In the following, we will identity and with their images in . Let

and

Then , , are all the primitive idempotents of . They have the following properties:

and

Let

which can be computed in deterministic polynomial time. Then

where

Hence encodes information about the "squareness" of the differences of the roots of . By using characteristic polynomials and gcd technique, one can extract the factors of .

Definition. For , define

Theorem. We can always find a proper factor of in except when

 (1)

and in this exception case can be factored over as

where

To further factor over , we compute in the ring

and similarly for . Theorem. We can always split or except when

 (2)

and in this exception case, is factored over as

where both of degree ; similarly over the ring ,

A system of subsets satisfying () and () is called an Hadamard design. When is a prime, there is always an Hadamard design.

To further split , let , and we compute in the ring

Similarly for , , and . Theorem. We can always split , , , or except when

 (3)

It can be proved, however, that () is impossible. It remains open how to explore this information to obtain a proper factor of in !

Back to the main index for Future directions in algorithmic number theory.