/usr/share/axiom-20170501/src/algebra/EMR.spad is in axiom-source 20170501-3.
This file is owned by root:root, with mode 0o644.
The actual contents of the file can be viewed below.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 | )abbrev domain EMR EuclideanModularRing
++ Author: Mark Botch
++ 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,merge,exactQuo) : SIG == CODE where
S : CommutativeRing
R : UnivariatePolynomialCategory S
Mod : AbelianMonoid
reduction : (R,Mod) -> R
merge : (Mod,Mod) -> Union(Mod,"failed")
exactQuo : (R,R,Mod) -> Union(R,"failed")
SIG ==> EuclideanDomain with
modulus : % -> Mod
++ modulus(x) is not documented
coerce : % -> R
++ coerce(x) is not documented
reduce : (R,Mod) -> %
++ reduce(r,m) is not documented
exQuo : (%,%) -> Union(%,"failed")
++ exQuo(x,y) is not documented
recip : % -> Union(%,"failed")
++ recip(x) is not documented
inv : % -> %
++ inv(x) is not documented
elt : (%, R) -> R
++ elt(x,r) or x.r is not documented
CODE ==> 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 (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 (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 (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
(leadingCoefficient(x.val) = 1) => x
invlcx:%:=inv reduce((leadingCoefficient(x.val))::R,x.modulo)
invlcx * x
unitNormal x ==
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)
|