\def\nn{\noindent}
\def\mm{\medskip}
\magnification=\magstep3
\hfuzz=4pt
\pageno17
\baselineskip.5truein
\centerline{\bf Frobenius Pseudoprimes}
Let $f(x)\in{\bf Z}[x]$ be a monic polynomial of degree $d$
with discriminant $\Delta$.   
An odd integer $n>1$ is said to pass the {\bf Frobenius
probable prime test} with respect to $f(x)$ if we have $\gcd(n,f(0)\Delta)=1$,
and $n$ is declared to be a probable prime by the following algorithm.
(Such an integer will be called a {\bf Frobenius probable prime} with
respect to $f(x)$.)
All computations are done in $({\bf Z}/n{\bf Z})[x]$.


{\bf Factorization Step} Let $f_0(x)=f(x) \bmod n$.
For $1\le i\le d$, let $F_i(x)=\gcd(x^{n^i}-x,f_{i-1}(x))$, and let
$f_i(x)=f_{i-1}(x)/F_i(x)$.
If any of the $\gcd$s fail to exist, declare $n$ to be composite and stop.
If $f_d(x)\not=1$, declare $n$ to be composite and stop.

{\bf Frobenius Step}  For $2\le i\le d$, compute $F_i(x^n) \bmod F_i(x)$.  If it is nonzero for some $i$, 
declare $n$ to be composite and stop.

{\bf Jacobi Step} Let $S=\sum_{2|i}\deg(F_i(x))/i$.

If $(-1)^S\not=\left(\Delta\over n\right)$,
declare $n$ to be composite and stop.
\vfill\eject
\pageno23
\centerline{\bf A Theorem in Analytic Number Theory}
\vskip.5truein
Let $f(t)\in{\bf Z}[t]$ be a monic polynomial with splitting field
$K$, $[K:{\bf Q}]=n$.
Then we have real numbers $x_{1/3},\eta_{1/3}>0$
and an integer $q_{1/3}(x)>\log
x$, depending on $K$, such that the
following statement holds.
If $q\le x^{\eta_{1/3}}$, $\gcd(a,q)=1$, $q_{1/3}(x)\not| q$, $x\ge
x_{1/3}$ and $x^{1/2}<y<x$, then the number of primes $p<y$
that are $a \bmod q$ and such that  $f(t)$ splits into linear factors
mod $p$
(equivalently, $p$ splits completely in $K$)
is at least ${1}\over{2\phi(q)n}\pi(x)$.  
\end