/usr/share/axiom-20170501/src/algebra/PRIMELT.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 | )abbrev package PRIMELT PrimitiveElement
++ Author: Manuel Bronstein
++ Date Created: 6 Jun 1990
++ Date Last Updated: 25 April 1991
++ Description:
++ PrimitiveElement provides functions to compute primitive elements
++ in algebraic extensions;
PrimitiveElement(F) : SIG == CODE where
F : Join(Field, CharacteristicZero)
SY ==> Symbol
P ==> Polynomial F
UP ==> SparseUnivariatePolynomial F
RC ==> Record(coef1: Integer, coef2: Integer, prim:UP)
REC ==> Record(coef: List Integer, poly:List UP, prim: UP)
SIG ==> with
primitiveElement : (P, SY, P, SY) -> RC
++ primitiveElement(p1, a1, p2, a2) returns \spad{[c1, c2, q]}
++ such that \spad{k(a1, a2) = k(a)}
++ where \spad{a = c1 a1 + c2 a2, and q(a) = 0}.
++ The pi's are the defining polynomials for the ai's.
++ The p2 may involve a1, but p1 must not involve a2.
++ This operation uses \spadfun{resultant}.
primitiveElement : (List P, List SY) -> REC
++ primitiveElement([p1,...,pn], [a1,...,an]) returns
++ \spad{[[c1,...,cn], [q1,...,qn], q]}
++ such that then \spad{k(a1,...,an) = k(a)},
++ where \spad{a = a1 c1 + ... + an cn},
++ \spad{ai = qi(a)}, and \spad{q(a) = 0}.
++ The pi's are the defining polynomials for the ai's.
++ This operation uses the technique of
++ \spadglossSee{groebner bases}{Groebner basis}.
primitiveElement : (List P, List SY, SY) -> REC
++ primitiveElement([p1,...,pn], [a1,...,an], a) returns
++ \spad{[[c1,...,cn], [q1,...,qn], q]}
++ such that then \spad{k(a1,...,an) = k(a)},
++ where \spad{a = a1 c1 + ... + an cn},
++ \spad{ai = qi(a)}, and \spad{q(a) = 0}.
++ The pi's are the defining polynomials for the ai's.
++ This operation uses the technique of
++ \spadglossSee{groebner bases}{Groebner basis}.
CODE ==> add
import PolyGroebner(F)
multi : (UP, SY) -> P
randomInts: (NonNegativeInteger, NonNegativeInteger) -> List Integer
findUniv : (List P, SY, SY) -> Union(P, "failed")
incl? : (List SY, List SY) -> Boolean
triangularLinearIfCan:(List P,List SY,SY) -> Union(List UP,"failed")
innerPrimitiveElement: (List P, List SY, SY) -> REC
multi(p, v) == multivariate(map((f1:F):F +-> f1, p), v)
randomInts(n, m) == [symmetricRemainder(random()$Integer, m) for i in 1..n]
incl?(a, b) == every?((s1:SY):Boolean +-> member?(s1, b), a)
primitiveElement(l, v) == primitiveElement(l, v, new()$SY)
primitiveElement(p1, a1, p2, a2) ==
(degree(p2, a1) = 1) => [0, 1, univariate resultant(p1, p2, a1)]
u := (new()$SY)::P
b := a2::P
for i in 10.. repeat
c := symmetricRemainder(random()$Integer, i)
w := u - c * b
r := univariate resultant(eval(p1, a1, w), eval(p2, a1, w), a2)
not zero? r and r = squareFreePart r => return [1, c, r]
findUniv(l, v, opt) ==
for p in l repeat
degree(p, v) > 0 and incl?(variables p, [v, opt]) => return p
"failed"
triangularLinearIfCan(l, lv, w) ==
(u := findUniv(l, w, w)) case "failed" => "failed"
pw := univariate(u::P)
ll := nil()$List(UP)
for v in lv repeat
((u := findUniv(l, v, w)) case "failed") or
(degree(p := univariate(u::P, v)) ^= 1) => return "failed"
(bc := extendedEuclidean(univariate leadingCoefficient p, pw,1))
case "failed" => error "Should not happen"
ll := concat(map((z1:F):F +-> z1,
(- univariate(coefficient(p,0)) * bc.coef1) rem pw), ll)
concat(map((f1:F):F +-> f1, pw), reverse_! ll)
primitiveElement(l, vars, uu) ==
u := uu::P
vv := [v::P for v in vars]
elim := concat(vars, uu)
w := uu::P
n := #l
for i in 10.. repeat
cf := randomInts(n, i)
(tt := triangularLinearIfCan(lexGroebner(
concat(w - +/[c * t for c in cf for t in vv], l), elim),
vars, uu)) case List(UP) =>
ltt := tt::List(UP)
return([cf, rest ltt, first ltt])
|