\documentclass{article}
\usepackage{open-axiom}
\begin{document}
\title{\$SPAD/src/algebra ffx.spad}
\author{Robert Sutor}
\maketitle
\begin{abstract}
\end{abstract}
\eject
\tableofcontents
\eject
\section{package IRREDFFX IrredPolyOverFiniteField}
<<package IRREDFFX IrredPolyOverFiniteField>>=
)abbrev package IRREDFFX IrredPolyOverFiniteField
++ Author: Robert S. Sutor (original)
++ Date Created: ???
++ Date Last Updated: 29 May 1990
++ Description:
++ This package exports the function generateIrredPoly that computes
++ a monic irreducible polynomial of degree n over a finite field.

IrredPolyOverFiniteField(GF:FiniteFieldCategory): Exports == Impl where
  N    ==> PositiveInteger
  Z    ==> Integer
  SUP  ==> SparseUnivariatePolynomial GF
  QR   ==> Record(quotient: Z, remainder: Z)

  Exports ==> with
    generateIrredPoly: N -> SUP
      ++ generateIrredPoly(n) generates an irreducible univariate
      ++ polynomial of the given degree n over the finite field.

  Impl ==> add
    import DistinctDegreeFactorize(GF, SUP)

    getIrredPoly  : (Z, N) -> SUP
    qAdicExpansion: Z -> SUP

    p := characteristic$GF :: N
    q := size()$GF :: N

    qAdicExpansion(z : Z): SUP ==
      -- expands z as a sum of powers of q, with coefficients in GF
      -- z = HornerEval(qAdicExpansion z,q)
      qr := divide(z, q)
      zero?(qr.remainder) => monomial(1, 1) * qAdicExpansion(qr.quotient)
      r := index(qr.remainder pretend N)$GF :: SUP
      zero?(qr.quotient) => r
      r + monomial(1, 1) * qAdicExpansion(qr.quotient)

    getIrredPoly(start : Z, n : N) : SUP ==
      -- idea is to iterate over possibly irreducible monic polynomials
      -- until we find an irreducible one. The obviously reducible ones
      -- are avoided.
      mon := monomial(1, n)$SUP
      pol: SUP := 0
      found: Boolean := false
      end: Z := q**n - 1
      while not ((end < start) or found) repeat
        if gcd(start, p) = 1 then
          if irreducible?(pol := mon + qAdicExpansion(start)) then
            found := true
        start := start + 1
      zero? pol => error "no irreducible poly found"
      pol

    generateIrredPoly(n : N) : SUP ==
      -- want same poly every time
      one?(n) => monomial(1, 1)$SUP
      one?(gcd(p, n)) or (n < q) =>
        odd?(n) => getIrredPoly(2, n)
        getIrredPoly(1, n)
      getIrredPoly(q + 1, n)

@
\section{License}
<<license>>=
--Copyright (c) 1991-2002, The Numerical ALgorithms Group Ltd.
--All rights reserved.
--
--Redistribution and use in source and binary forms, with or without
--modification, are permitted provided that the following conditions are
--met:
--
--    - Redistributions of source code must retain the above copyright
--      notice, this list of conditions and the following disclaimer.
--
--    - Redistributions in binary form must reproduce the above copyright
--      notice, this list of conditions and the following disclaimer in
--      the documentation and/or other materials provided with the
--      distribution.
--
--    - Neither the name of The Numerical ALgorithms Group Ltd. nor the
--      names of its contributors may be used to endorse or promote products
--      derived from this software without specific prior written permission.
--
--THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS "AS
--IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED
--TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A
--PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER
--OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL,
--EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT LIMITED TO,
--PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, DATA, OR
--PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY THEORY OF
--LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT (INCLUDING
--NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF THIS
--SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
@
<<*>>=
<<license>>

<<package IRREDFFX IrredPolyOverFiniteField>>
@
\eject
\begin{thebibliography}{99}
\bibitem{1} nothing
\end{thebibliography}
\end{document}