diff options
| author | dos-reis <gdr@axiomatics.org> | 2007-08-14 05:14:52 +0000 |
|---|---|---|
| committer | dos-reis <gdr@axiomatics.org> | 2007-08-14 05:14:52 +0000 |
| commit | ab8cc85adde879fb963c94d15675783f2cf4b183 (patch) | |
| tree | c202482327f474583b750b2c45dedfc4e4312b1d /src/algebra/modring.spad.pamphlet | |
| download | open-axiom-ab8cc85adde879fb963c94d15675783f2cf4b183.tar.gz | |
Initial population.
Diffstat (limited to 'src/algebra/modring.spad.pamphlet')
| -rw-r--r-- | src/algebra/modring.spad.pamphlet | 280 |
1 files changed, 280 insertions, 0 deletions
diff --git a/src/algebra/modring.spad.pamphlet b/src/algebra/modring.spad.pamphlet new file mode 100644 index 00000000..015a5c84 --- /dev/null +++ b/src/algebra/modring.spad.pamphlet @@ -0,0 +1,280 @@ +\documentclass{article} +\usepackage{axiom} +\begin{document} +\title{\$SPAD/src/algebra modring.spad} +\author{Patrizia Gianni, Barry Trager} +\maketitle +\begin{abstract} +\end{abstract} +\eject +\tableofcontents +\eject +\section{domain MODRING ModularRing} +<<domain MODRING ModularRing>>= +)abbrev domain MODRING ModularRing +++ Author: P.Gianni, B.Trager +++ Date Created: +++ Date Last Updated: +++ Basic Functions: +++ Related Constructors: +++ Also See: +++ AMS Classifications: +++ Keywords: +++ References: +++ Description: +++ These domains are used for the factorization and gcds +++ of univariate polynomials over the integers in order to work modulo +++ different primes. +++ See \spadtype{EuclideanModularRing} ,\spadtype{ModularField} + +ModularRing(R,Mod,reduction:(R,Mod) -> R, + merge:(Mod,Mod) -> Union(Mod,"failed"), + exactQuo : (R,R,Mod) -> Union(R,"failed")) : C == T + where + R : CommutativeRing + Mod : AbelianMonoid + + C == Ring with + modulus : % -> Mod + ++ modulus(x) \undocumented + coerce : % -> R + ++ coerce(x) \undocumented + reduce : (R,Mod) -> % + ++ reduce(r,m) \undocumented + exQuo : (%,%) -> Union(%,"failed") + ++ exQuo(x,y) \undocumented + recip : % -> Union(%,"failed") + ++ recip(x) \undocumented + inv : % -> % + ++ inv(x) \undocumented + + T == add + --representation + Rep:= Record(val:R,modulo:Mod) + --declarations + x,y: % + + --define + modulus(x) == x.modulo + coerce(x) == x.val + coerce(i:Integer):% == [i::R,0]$Rep + i:Integer * x:% == (i::%)*x + coerce(x):OutputForm == (x.val)::OutputForm + reduce (a:R,m:Mod) == [reduction(a,m),m]$Rep + + characteristic():NonNegativeInteger == characteristic()$R + 0 == [0$R,0$Mod]$Rep + 1 == [1$R,0$Mod]$Rep + zero? x == zero? x.val +-- one? x == one? x.val + one? x == (x.val = 1) + + newmodulo(m1:Mod,m2:Mod) : Mod == + r:=merge(m1,m2) + r case "failed" => error "incompatible moduli" + r::Mod + + x=y == + x.val = y.val => true + x.modulo = y.modulo => false + (x-y).val = 0 + x+y == reduce((x.val +$R y.val),newmodulo(x.modulo,y.modulo)) + x-y == reduce((x.val -$R y.val),newmodulo(x.modulo,y.modulo)) + -x == reduce ((-$R x.val),x.modulo) + x*y == reduce((x.val *$R y.val),newmodulo(x.modulo,y.modulo)) + + exQuo(x,y) == + xm:=x.modulo + if xm ^=$Mod y.modulo then xm:=newmodulo(xm,y.modulo) + r:=exactQuo(x.val,y.val,xm) + r case "failed"=> "failed" + [r::R,xm]$Rep + + --if R has EuclideanDomain then + recip x == + r:=exactQuo(1$R,x.val,x.modulo) + r case "failed" => "failed" + [r,x.modulo]$Rep + + inv x == + if (u:=recip x) case "failed" then error("not invertible") + else u::% + +@ +\section{domain EMR EuclideanModularRing} +<<domain EMR EuclideanModularRing>>= +)abbrev domain EMR EuclideanModularRing +++ Description: +++ These domains are used for the factorization and gcds +++ of univariate polynomials over the integers in order to work modulo +++ different primes. +++ See \spadtype{ModularRing}, \spadtype{ModularField} +EuclideanModularRing(S,R,Mod,reduction:(R,Mod) -> R, + merge:(Mod,Mod) -> Union(Mod,"failed"), + exactQuo : (R,R,Mod) -> Union(R,"failed")) : C == T + where + S : CommutativeRing + R : UnivariatePolynomialCategory S + Mod : AbelianMonoid + + C == EuclideanDomain with + modulus : % -> Mod + ++ modulus(x) \undocumented + coerce : % -> R + ++ coerce(x) \undocumented + reduce : (R,Mod) -> % + ++ reduce(r,m) \undocumented + exQuo : (%,%) -> Union(%,"failed") + ++ exQuo(x,y) \undocumented + recip : % -> Union(%,"failed") + ++ recip(x) \undocumented + inv : % -> % + ++ inv(x) \undocumented + elt : (%, R) -> R + ++ elt(x,r) or x.r \undocumented + + T == ModularRing(R,Mod,reduction,merge,exactQuo) add + + --representation + Rep:= Record(val:R,modulo:Mod) + --declarations + x,y,z: % + + divide(x,y) == + t:=merge(x.modulo,y.modulo) + t case "failed" => error "incompatible moduli" + xm:=t::Mod + yv:=y.val + invlcy:R +-- if one? leadingCoefficient yv then invlcy:=1 + if (leadingCoefficient yv = 1) then invlcy:=1 + else + invlcy:=(inv reduce((leadingCoefficient yv)::R,xm)).val + yv:=reduction(invlcy*yv,xm) + r:=monicDivide(x.val,yv) + [reduce(invlcy*r.quotient,xm),reduce(r.remainder,xm)] + + if R has fmecg:(R,NonNegativeInteger,S,R)->R + then x rem y == + t:=merge(x.modulo,y.modulo) + t case "failed" => error "incompatible moduli" + xm:=t::Mod + yv:=y.val + invlcy:R +-- if not one? leadingCoefficient yv then + if not (leadingCoefficient yv = 1) then + invlcy:=(inv reduce((leadingCoefficient yv)::R,xm)).val + yv:=reduction(invlcy*yv,xm) + dy:=degree yv + xv:=x.val + while (d:=degree xv - dy)>=0 repeat + xv:=reduction(fmecg(xv,d::NonNegativeInteger, + leadingCoefficient xv,yv),xm) + xv = 0 => return [xv,xm]$Rep + [xv,xm]$Rep + else x rem y == + t:=merge(x.modulo,y.modulo) + t case "failed" => error "incompatible moduli" + xm:=t::Mod + yv:=y.val + invlcy:R +-- if not one? leadingCoefficient yv then + if not (leadingCoefficient yv = 1) then + invlcy:=(inv reduce((leadingCoefficient yv)::R,xm)).val + yv:=reduction(invlcy*yv,xm) + r:=monicDivide(x.val,yv) + reduce(r.remainder,xm) + + euclideanSize x == degree x.val + + unitCanonical x == + zero? x => x + degree(x.val) = 0 => 1 +-- one? leadingCoefficient(x.val) => x + (leadingCoefficient(x.val) = 1) => x + invlcx:%:=inv reduce((leadingCoefficient(x.val))::R,x.modulo) + invlcx * x + + unitNormal x == +-- zero?(x) or one?(leadingCoefficient(x.val)) => [1, x, 1] + zero?(x) or ((leadingCoefficient(x.val)) = 1) => [1, x, 1] + lcx := reduce((leadingCoefficient(x.val))::R,x.modulo) + invlcx:=inv lcx + degree(x.val) = 0 => [lcx, 1, invlcx] + [lcx, invlcx * x, invlcx] + + elt(x : %,s : R) : R == reduction(elt(x.val,s),x.modulo) + +@ +\section{domain MODFIELD ModularField} +<<domain MODFIELD ModularField>>= +)abbrev domain MODFIELD ModularField +++ These domains are used for the factorization and gcds +++ of univariate polynomials over the integers in order to work modulo +++ different primes. +++ See \spadtype{ModularRing}, \spadtype{EuclideanModularRing} +ModularField(R,Mod,reduction:(R,Mod) -> R, + merge:(Mod,Mod) -> Union(Mod,"failed"), + exactQuo : (R,R,Mod) -> Union(R,"failed")) : C == T + where + R : CommutativeRing + Mod : AbelianMonoid + + C == Field with + modulus : % -> Mod + ++ modulus(x) \undocumented + coerce : % -> R + ++ coerce(x) \undocumented + reduce : (R,Mod) -> % + ++ reduce(r,m) \undocumented + exQuo : (%,%) -> Union(%,"failed") + ++ exQuo(x,y) \undocumented + + T == ModularRing(R,Mod,reduction,merge,exactQuo) + +@ +\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>> + +<<domain MODRING ModularRing>> +<<domain EMR EuclideanModularRing>> +<<domain MODFIELD ModularField>> +@ +\eject +\begin{thebibliography}{99} +\bibitem{1} nothing +\end{thebibliography} +\end{document} |