src/algebra/galfact.spad

34     if R has FloatingPointSystem then
53     if R has FloatingPointSystem then
57         if (shift := order(x)-precision()$R+safetymargin) >= 0 then
62         if (shift := order(x)-precision()$R+safetymargin) >= 0 then
96       if n<ncomputed then
97         if n<3 then
139       ++ monic?(p) tests if p is monic (i.e. leading coefficient equal to 1).
153       ++ factorOfDegree(d, f) returns a factor of degree d of the factored
154       ++ polynomial f. Such a factor shall exist.
165       for fr in factorList r | degree(fr.factor)=(d::N) repeat
167           lfact := cons(fr.factor, lfact)
171       factor : UP := 0
173         factor := i.factor
174         if degree(factor)=(d::N) then return factor
178       multiset([ degree(i.factor) for i in factorList r ])
249       ++ factor of p.
259       ++ the factor of p with smallest Bombieri's norm. r is a lower bound
264       ++ the factor of p with smallest Bombieri's norm. p shall be of degree
308       if F has Gamma : F -> F then
347       if zero? d then return b
354       if even? d then
365 ++ Basic Operations: factor
380 ++ to factor resolvents.
397   DDRecord ==> Record(factor : UP, degree : Z) -- a Distinct-Degree factor
445       ++ useSingleFactorBound?() returns \spad{true} if algorithm with single
446       ++ factor bound is used for factorization, \spad{false} for algorithm
451       ++ factor bound, \spad{false} for algorithm with overall bound.
454       ++ useEisensteinCriterion?() returns \spad{true} if factorizers
461       ++ eisensteinIrreducible?(p) returns \spad{true} if p can be
465       ++ tryFunctionalDecomposition?() returns \spad{true} if
472     factor : UP -> Factored UP
473       ++ factor(p) returns the factorization of p over the integers.
474     factor : (UP, N) -> Factored UP
475       ++ factor(p, r) factorizes the polynomial p using the single factor bound
477     factor : (UP, List N) -> Factored UP
478       ++ factor(p, listOfDegrees) factorizes the polynomial p using the single
479       ++ factor bound algorithm and knowing that p has for possible
481     factor : (UP, List N, N) -> Factored UP
482       ++ factor(p, listOfDegrees, r) factorizes the polynomial p using the single
483       ++ factor bound algorithm, knowing that p has for possible
486     factor : (UP, N, N) -> Factored UP
487       ++ factor(p, d, r) factorizes the polynomial p using the single
488       ++ factor bound algorithm, knowing that d divides the degree of all
492       ++ not having any repeated factor (this is not checked).
495       ++ factor bound algorithm and knowing that p has at least r factors.
496       ++ p is supposed not having any repeated factor (this is not checked).
499       ++ the single factor bound algorithm and knowing that p has for possible
501       ++ p is supposed not having any repeated factor (this is not checked).
504       ++ the single factor bound algorithm, knowing that p has for possible
507       ++ p is supposed not having any repeated factor (this is not checked).
510       ++ factor bound algorithm, knowing that d divides the degree of all
512       ++ p is supposed not having any repeated factor (this is not checked).
514       ++ factorOfDegree(d, p) returns a factor of p of degree d.
516       ++ factorOfDegree(d, p, r) returns a factor of p of degree
519       ++ factorOfDegree(d, p, listOfDegrees) returns a factor
523       ++ factorOfDegree(d, p, listOfDegrees, r) returns a factor
528       ++ factor of p of degree d knowing that p has for possible splitting of
551     FFE ==> Record(flag : fUnion, factor : UP, exponent : N)
607       for p in factorList(factor c)$Factored(Z) repeat
608         if (p.exponent = 1) and (not zero? (lc rem p.factor)) and
609          (not zero? (tc rem ((p.factor)^2))) then return true
617           zero? (d := degree(dd.factor)::Z) => 1
631     -- factor reconciliation of a given level (which is the number of
632     -- extraneaous factors involved) or "End of level" if not any
634       if (l := length n)<levels then return(n+shift(1, l-1))
645     is_mod_coprime?(pol1 : UP, pol2 : UP, p : Integer, small : Boolean
647         small =>
670     do_ddfact(pol : UP, p : Integer, small : Boolean) : DDres ==
672         small =>
676             if c ~= 1 then
687             degs := add_degs(degree(rl.factor), rl.degree::N, degs)
710       small : Boolean := true
712         if small and not(degp*cprime*cprime < 18446744073709551616) then
713             small := false
717           (not is_mod_coprime?(p, diffp, cprime, small)) repeat
719         dd_res1 := do_ddfact(p, cprime, small)
728         if nf1 < nf or (nf1 = nf) and (cprime > res_prime) then
741         zero? (d := degree(f.factor)) => dp := insert!(0, dp)
762       if brillhartIrreducible? f or
766       if pdecomp and tryfunctionaldecomposition then
786     -- using the single-factor bound technique
814             if bit?(i, j-1) then
818           if member?(degg, d) and (((lc*f0) exquo g0) case Z) then
820             g := lc::UP -- build the possible factor -- LC algorithm
821             for j in 1..levels repeat if bit?(i, j-1) then g := g*lf.j
824             if f1 case UP then -- g is a true factor
829                 if bit?(i, j-1) then
840               if not(dg = set [0, degg]) then -- implies degg >= 2
843                 if b>pk and (not brillhartIrreducible?(g)) and
852                   if gpk<b then
862               if degf<=1 then -- lf exhausted
863                 if (degf = 1) then
868                 if b>pk then -- unlucky : no we can't
876                   if pk<b then return append(lf, ltrue) -- 2nd exit
879         if found? then
882         if not (ic case Z) then level := level+1
883       cons(f,ltrue) -- 3rd exit, the last factor was irreducible but not "true"
889         if (ee := (e exquo n)$N) case N then l := cons(ee::N, l)
904       if abs(coefficient(f, 0))<abs(leadingCoefficient(f)) then
909         if reverse? then [ reverse f ] else [ f ]
910       if leadingCoefficient(f)<0 then
914       if pdecomp and tryfunctionaldecomposition then
918       if cf case "failed" then
921           if reverse? then
922             if negativelc? then return [ -reverse f ]
924           else if negativelc? then return [ -f ]
926         if noLinearFactor? f then d := remove(1, d)
932         if ground? first lf then lf := rest lf
935         if not pk < b then lf := completeFactor(f, lf, cprime, pk, r, d)
950       if reverse? then lf := [ reverse(fact) for fact in lf ]
952         if leadingCoefficient(lf.i)<0 then lf.i := -lf.i
957       ctp := factor flist.contp
962         fflist := cons([fc.flag, fc.factor::UP, fc.exponent]$FFE, fflist)
977       if not (d = 1) then
1001       if leadingCoefficient f < 0 then
1005       -- is x^d factor of f
1006       if (d := minimumDegree f) > 0 then
1021       -lcPol = reductum(f) =>    -- if true, both will = 1
1031            if leadingCoefficient fac < 0 then fac := -fac
1036       -- if so, then irreducible
1051         sqff := sqfr.factor
1071       if leadingCoefficient f < 0 then
1075       -- is x^d factor of f
1076       if (maxd := minimumDegree f) > 0 then
1092       -lcPol = reductum(f) =>    -- if true, both will = 1
1102            if leadingCoefficient fac < 0 then fac := -fac
1107       -- if so, then irreducible
1120       if ((#(sqfflist)) = 1) then -- indeed f was a power of a square-free
1126         sqff := sqfr.factor
1143     factor(f : UP) : Factored UP ==
1148     -- local function, returns true if the sum of the elements of the list
1158     factor(f : UP, ld : List N, r : N) : Factored UP ==
1159       errorsum?(degree f,ld) => error "factor: Bad arguments"
1162     factor(f : UP, r : N) : Factored UP == makeFR btwFact(f, false, fullSet(degree f), r)
1164     factor(f : UP, ld : List N) : Factored UP == factor(f, ld, 2)
1166     factor(f : UP, d : N, r : N) : Factored UP ==
1168       n case "failed" => error "factor: Bad arguments"
1169       factor(f, new(n::N, d)$List(N), r)