001 /*
002 * $Id: FactorAlgebraicPrim.java 3753 2011-08-27 20:34:30Z kredel $
003 */
004
005 package edu.jas.application;
006
007
008 import java.util.ArrayList;
009 import java.util.List;
010
011 import org.apache.log4j.Logger;
012
013 import edu.jas.poly.AlgebraicNumber;
014 import edu.jas.poly.AlgebraicNumberRing;
015 import edu.jas.poly.GenPolynomial;
016 import edu.jas.poly.GenPolynomialRing;
017 import edu.jas.poly.PolyUtil;
018 import edu.jas.poly.TermOrder;
019 import edu.jas.structure.GcdRingElem;
020 import edu.jas.ufd.FactorAbstract;
021 import edu.jas.ufd.FactorAbsolute;
022 //import edu.jas.ufd.FactorFactory;
023 import edu.jas.ufd.Squarefree;
024 import edu.jas.ufd.SquarefreeFactory;
025 import edu.jas.ufd.PolyUfdUtil;
026
027
028 /**
029 * Algebraic number coefficients factorization algorithms. This class implements
030 * factorization methods for polynomials over algebraic numbers over rational
031 * numbers or over (prime) modular integers.
032 * @author Heinz Kredel
033 * @param <C> coefficient type
034 */
035
036 public class FactorAlgebraicPrim<C extends GcdRingElem<C>> extends FactorAbsolute<AlgebraicNumber<C>> {
037
038
039 //FactorAbstract<AlgebraicNumber<C>>
040
041
042 private static final Logger logger = Logger.getLogger(FactorAlgebraicPrim.class);
043
044
045 private final boolean debug = true || logger.isInfoEnabled();
046
047
048 /**
049 * Factorization engine for base coefficients.
050 */
051 public final FactorAbstract<C> factorCoeff;
052
053
054 /**
055 * No argument constructor. <b>Note:</b> can't use this constructor.
056 */
057 protected FactorAlgebraicPrim() {
058 throw new IllegalArgumentException("don't use this constructor");
059 }
060
061
062 /**
063 * Constructor.
064 * @param fac algebraic number factory.
065 */
066 public FactorAlgebraicPrim(AlgebraicNumberRing<C> fac) {
067 super(fac);
068 this.factorCoeff = FactorFactory.<C> getImplementation(fac.ring.coFac);
069 }
070
071
072 /**
073 * GenPolynomial base factorization of a squarefree polynomial.
074 * @param P squarefree GenPolynomial<AlgebraicNumber<C>>.
075 * @return [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i.
076 */
077 @Override
078 public List<GenPolynomial<AlgebraicNumber<C>>> baseFactorsSquarefree(GenPolynomial<AlgebraicNumber<C>> P) {
079 if (P == null) {
080 throw new IllegalArgumentException(this.getClass().getName() + " P == null");
081 }
082 List<GenPolynomial<AlgebraicNumber<C>>> factors = new ArrayList<GenPolynomial<AlgebraicNumber<C>>>();
083 if (P.isZERO()) {
084 return factors;
085 }
086 if (P.isONE()) {
087 factors.add(P);
088 return factors;
089 }
090 GenPolynomialRing<AlgebraicNumber<C>> pfac = P.ring; // Q(alpha)[x]
091 if (pfac.nvar > 1) {
092 throw new IllegalArgumentException("only for univariate polynomials");
093 }
094 AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) pfac.coFac;
095
096 AlgebraicNumber<C> ldcf = P.leadingBaseCoefficient();
097 if (!ldcf.isONE()) {
098 P = P.monic();
099 factors.add(pfac.getONE().multiply(ldcf));
100 }
101 //System.out.println("\nP = " + P);
102 if (false && debug) {
103 Squarefree<AlgebraicNumber<C>> sqengine = SquarefreeFactory.<AlgebraicNumber<C>> getImplementation(afac);
104 if ( !sqengine.isSquarefree(P) ) {
105 throw new RuntimeException("P not squarefree: " + sqengine.squarefreeFactors(P));
106 }
107 GenPolynomial<C> modu = afac.modul;
108 if ( !factorCoeff.isIrreducible(modu) ) {
109 throw new RuntimeException("modul not irreducible: " + factorCoeff.factors(modu));
110 }
111 System.out.println("P squarefree and modul irreducible via ideal decomposition");
112 //GreatestCommonDivisor<AlgebraicNumber<C>> aengine //= GCDFactory.<AlgebraicNumber<C>> getProxy(afac);
113 // = new GreatestCommonDivisorSimple<AlgebraicNumber<C>>( /*cfac.coFac*/ );
114 }
115 GenPolynomial<C> agen = afac.modul;
116 GenPolynomialRing<C> cfac = afac.ring;
117 GenPolynomialRing<GenPolynomial<C>> rfac = new GenPolynomialRing<GenPolynomial<C>>(cfac, pfac);
118 // transform minimal polynomial to bi-variate polynomial
119 GenPolynomial<GenPolynomial<C>> Ac = PolyUfdUtil.<C> introduceLowerVariable(rfac, agen);
120 //System.out.println("Ac = " + Ac.toScript());
121 // transform to bi-variate polynomial,
122 // switching varaible sequence from Q[alpha][x] to Q[X][alpha]
123 GenPolynomial<GenPolynomial<C>> Pc = PolyUfdUtil.<C> substituteFromAlgebraicCoefficients(rfac, P, 0);
124 Pc = PolyUtil.<C> monic(Pc);
125 //System.out.println("Pc = " + Pc.toScript());
126 // distribute
127 TermOrder to = new TermOrder(TermOrder.INVLEX);
128 String[] vars = new String[2];
129 vars[0] = cfac.getVars()[0];
130 vars[1] = rfac.getVars()[0];
131 GenPolynomialRing<C> dfac = new GenPolynomialRing<C>(cfac.coFac, to, vars);
132 GenPolynomial<C> Ad = agen.extend(dfac,0,0L);
133 Pc = PolyUtil.<C> fromAlgebraicCoefficients(rfac,P);
134 GenPolynomial<C> Pd = PolyUtil.<C> distribute(dfac,Pc);
135 //System.out.println("Ad = " + Ad.toScript());
136 //System.out.println("Pd = " + Pd.toScript());
137
138 List<GenPolynomial<C>> id = new ArrayList<GenPolynomial<C>>(2);
139 id.add(Ad);
140 id.add(Pd);
141 Ideal<C> I = new Ideal<C>(dfac,id);
142 List<IdealWithUniv<C>> Iul = I.zeroDimPrimeDecomposition();
143 //System.out.println("prime decomp = " + Iul);
144 if ( Iul.size() == 1 ) {
145 factors.add(P);
146 return factors;
147 }
148 GenPolynomial<AlgebraicNumber<C>> f = pfac.getONE();
149 for (IdealWithUniv<C> Iu : Iul ) {
150 GenPolynomial<C> ag = PolyUtil.<C> selectWithVariable(Iu.ideal.getList(),1);
151 GenPolynomial<C> pg = PolyUtil.<C> selectWithVariable(Iu.ideal.getList(),0);
152 //System.out.println("ag = " + ag.toScript());
153 //System.out.println("pg = " + pg.toScript());
154 if ( ag.equals(Ad) ) {
155 //System.out.println("found factor --------------------");
156 GenPolynomial<GenPolynomial<C>> pgr = PolyUtil.<C> recursive(rfac,pg);
157 GenPolynomial<AlgebraicNumber<C>> pga = PolyUtil.<C> convertRecursiveToAlgebraicCoefficients(pfac, pgr);
158 //System.out.println("pga = " + pga.toScript());
159 f = f.multiply(pga);
160 factors.add(pga);
161 }
162 }
163 f = f.subtract(P);
164 //System.out.println("f = " + f.toScript());
165 if ( !f.isZERO() ) {
166 throw new RuntimeException("no factorization: " + f + ", factors = " + factors);
167 }
168 return factors;
169 //return new edu.jas.ufd.FactorAlgebraic<C>(afac).baseFactorsSquarefree(P);
170 }
171
172 }