aboutsummaryrefslogtreecommitdiff
path: root/src/algebra/ffx.spad.pamphlet
diff options
context:
space:
mode:
authordos-reis <gdr@axiomatics.org>2007-08-14 05:14:52 +0000
committerdos-reis <gdr@axiomatics.org>2007-08-14 05:14:52 +0000
commitab8cc85adde879fb963c94d15675783f2cf4b183 (patch)
treec202482327f474583b750b2c45dedfc4e4312b1d /src/algebra/ffx.spad.pamphlet
downloadopen-axiom-ab8cc85adde879fb963c94d15675783f2cf4b183.tar.gz
Initial population.
Diffstat (limited to 'src/algebra/ffx.spad.pamphlet')
-rw-r--r--src/algebra/ffx.spad.pamphlet120
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}