Which problems have good algorithms?

[Raman]

Just I can't be simply focused upon only integer factorization,
primality testing, and discrete logarithms. It is time to increase
my knowledge to other problems as well. Let us start with problems
that are derived from integer factorization. Number Theory is not
the only thing in mathematics.

The next obvious problem is Polynomial Factorization. Unlike integer
factorization, polynomial factorization is not a single problem, it can
be done over integers, Gaussian integers, real numbers, complex numbers,
or over finite fields (finite fields = modulo prime). You may refer to that
"Factoris" calculator at wims.unice.fr website for more information about
that.

I know that any polynomial (let us consider one variable only) can be
factorized completely into linear factors over complex numbers, and
that complex roots always exist in conjugate pairs if coefficients of
that original polynomial are all real. The Newton-Raphson iteration will
give away with all real roots, I don't know any such algorithm for complex
numbers as well. Over integers, for every factor - that constant term
should be a divisor of that constant term of the original polynomial.

1) Given a degree 100 polynomial, is it compatible to factor that (over integers) with the time taken to factor a GNFS number of 100 digits?
2) Similar to primality tests for integers, is there any algorithm to test for the irreducibility of any given polynomial (over integers)
3) Over a finite field (mod p), is there any algorithm to count the number of irreducible polynomials of a certain degree? For example, number of irreducible degree 23 polynomials over Z₂

Consider finite field (Galois field) GF(pⁿ)
with some irreducible polynomial of degree n (mod p), note that this field has got a generator element with order equal to pⁿ-1.
I assume that finding out order of an element, inverse, power (modular exponentiation) over that finite field, GF(pⁿ) can be done similar to that over Z_p
4) Given an element over that GF(pⁿ), that is a polynomial of degree n-1, with those coefficients being elements from that set {0, 1, ..., p-1}. What is the most efficient way to find out the square root of that element over GF(pⁿ)? I know about that algorithm to calculate square roots for elements (mod p), in order to solve that congruence x² = a (mod p).
5) Does there exist any good algorithm in order to do that computations with that discrete logarithms over that field GF(pⁿ)? Rather, it is that power of an element that equals to some other element, when that finite field size is being sufficiently large enough.

[fivemack]

Most of the problems you mention have interesting and quick algorithms; factoring a polynomial of degree 1000 over Z takes nine seconds with gp, and counting irreducible polynomials over GF(2) of a given degree is almost immediate by a variety of inclusion-exclusion arguments.

On the other hand, factoring polynomials tends to be very boring; you can do factor(x^100+x^t+1) with gp for t=1..99 and you don't get a single split as a product of polynomials of similar degree, whilst looking at 2^100+2^n+1 gives you splits like 2^100+2^69+1=P15*P16.

As an observation, over GF(p), x^(p-1)-1 is the product of (x-1)(x-2)..(x-p-1), and x^((p-1)/2)-1 is the product of (x-a) for all a that happen to be quadratic residues, x^((p-1)/2)+1 is the product of (x-a) for all a that are not quadratic residues. So if you compute gcd(F, x^((p-1)/2)-1) then you get the product of the roots of F which are quadratic residues ... and if you compute gcd(F(x+1), x^((p-1)/2)-1) then you get the product of the roots of F which are one more than quadratic residues ... and the quadratic residues are in practice random enough that if you keep doing this for a while and take a tree of GCDs of your GCDs, you split F.

[fivemack]

http://mathworld.wolfram.com/IrreduciblePolynomial.html answers the counting-irreducible-polynomials question. It's a nice application of http://en.wikipedia.org/wiki/M%C3%B6...ersion_formula