diff options
Diffstat (limited to 'src/algebra/ffx.spad.pamphlet')
| -rw-r--r-- | src/algebra/ffx.spad.pamphlet | 120 |
1 files changed, 120 insertions, 0 deletions
diff --git a/src/algebra/ffx.spad.pamphlet b/src/algebra/ffx.spad.pamphlet new file mode 100644 index 00000000..66ccd76a --- /dev/null +++ b/src/algebra/ffx.spad.pamphlet @@ -0,0 +1,120 @@ +\documentclass{article} +\usepackage{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 + (n = 1) => monomial(1, 1)$SUP +-- one?(gcd(p, n)) or (n < q) => + (gcd(p, n) = 1) 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} |