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

- If
, then can be defined properly and can be computed in deterministic polynomial time for any elementary algebra .
- 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 .
- 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 .)
- 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

Now let be separable, so that

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

Let

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
*

To further factor over , we compute in 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

It can be proved, however, that () is impossible.

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