[FOM] Definable sets of primes

[joeshipman@aol.com]

Answering my own question below: Berlekamp's algorithm factoring 
polynomials mod p runs in time polynomial in n and log p. (I had 
originally thought it was polynomial in p but that can be improved to 
polynomial in log p.)

This makes Langlands's remark

**
verifying numerically the validity of the regularity suggested is a 
task that requires great skill and ingenuity and is by no means assured 
of success.
**

even more puzzling; what kind of achievement is it to detect a 
"regularity" concerning membership in a polynmial-time-computable set, 
if the equivalence is to a set that cannot be computed easily? It would 
make much more sense to me to regard the description "primes modulo 
which the polynomial f(x) has a root" as the PRIMARY definition of the 
set, and say that the OTHER set (involving representations of 
automorphic forms or some such) is the thing in which a "regularity" 
was discovered!

-- JS


-----Original Message-----
From: joeshipman at aol.com

Does there exist an algorithm to determine whether a given polynomial 
has a root modulo a given prime, which runs in polynomial time? (The 
prime and the coefficients of the polynomial are assumed to be written 
in ordinary decimal notation, including 0 coefficients [no sparse 
polynomials]). 
 
-- JS