Source code

001/*
002 * $Id: FactorAlgebraic.java 4028 2012-07-24 18:42:16Z kredel $
003 */
004
005package edu.jas.ufd;
006
007
008import java.util.ArrayList;
009import java.util.List;
010
011import org.apache.log4j.Logger;
012
013import edu.jas.poly.AlgebraicNumber;
014import edu.jas.poly.AlgebraicNumberRing;
015import edu.jas.poly.GenPolynomial;
016import edu.jas.poly.GenPolynomialRing;
017import edu.jas.poly.PolyUtil;
018import edu.jas.poly.TermOrder;
019import edu.jas.structure.GcdRingElem;
020
021
022/**
023 * Algebraic number coefficients factorization algorithms. This class implements
024 * factorization methods for polynomials over algebraic numbers over rational
025 * numbers or over (prime) modular integers.
026 * @author Heinz Kredel
027 * @param <C> coefficient type
028 */
029
030public class FactorAlgebraic<C extends GcdRingElem<C>> extends FactorAbsolute<AlgebraicNumber<C>> {
031
032
033    private static final Logger logger = Logger.getLogger(FactorAlgebraic.class);
034
035
036    private final boolean debug = logger.isDebugEnabled();
037
038
039    /**
040     * Factorization engine for base coefficients.
041     */
042    public final FactorAbstract<C> factorCoeff;
043
044
045    /**
046     * No argument constructor. <b>Note:</b> can't use this constructor.
047     */
048    protected FactorAlgebraic() {
049        throw new IllegalArgumentException("don't use this constructor");
050    }
051
052
053    /**
054     * Constructor.
055     * @param fac algebraic number factory.
056     */
057    public FactorAlgebraic(AlgebraicNumberRing<C> fac) {
058        this(fac, FactorFactory.<C> getImplementation(fac.ring.coFac) );
059    }
060
061
062    /**
063     * Constructor.
064     * @param fac algebraic number factory.
065     * @param factorCoeff factorization engine for polynomials over base coefficients.
066     */
067    public FactorAlgebraic(AlgebraicNumberRing<C> fac, FactorAbstract<C> factorCoeff) {
068        super(fac);
069        this.factorCoeff = factorCoeff;
070    }
071
072
073    /**
074     * GenPolynomial base factorization of a squarefree polynomial.
075     * @param P squarefree GenPolynomial&lt;AlgebraicNumber&lt;C&gt;&gt;.
076     * @return [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i.
077     */
078    @Override
079    public List<GenPolynomial<AlgebraicNumber<C>>> baseFactorsSquarefree(GenPolynomial<AlgebraicNumber<C>> P) {
080        if (P == null) {
081            throw new IllegalArgumentException(this.getClass().getName() + " P == null");
082        }
083        List<GenPolynomial<AlgebraicNumber<C>>> factors = new ArrayList<GenPolynomial<AlgebraicNumber<C>>>();
084        if (P.isZERO()) {
085            return factors;
086        }
087        if (P.isONE()) {
088            factors.add(P);
089            return factors;
090        }
091        GenPolynomialRing<AlgebraicNumber<C>> pfac = P.ring; // Q(alpha)[x]
092        if (pfac.nvar > 1) {
093            throw new IllegalArgumentException("only for univariate polynomials");
094        }
095        AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) pfac.coFac;
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 (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");
112           //GreatestCommonDivisor<AlgebraicNumber<C>> aengine //= GCDFactory.<AlgebraicNumber<C>> getProxy(afac);
113           //  = new GreatestCommonDivisorSimple<AlgebraicNumber<C>>( /*cfac.coFac*/ );
114        }
115
116        // search squarefree norm
117        long k = 0L;
118        long ks = k;
119        GenPolynomial<C> res = null;
120        boolean sqf = false;
121        //int[] klist = new int[]{ 0, 1, 2, 3, -1, -2, -3 , 5, -5, 7, -7, 101, -101, 1001, -1001 };
122        //int[] klist = new int[]{ 0, 1, 2, 3, -1, -2, -3 , 5, -5, 7, -7, 23, -23, 167, -167 };
123        //int[] klist = new int[] { 0, -1, -2, 1, 2, -3, 3 };
124        int[] klist = new int[] { 0, -1, -2, 1, 2 };
125        int ki = 0;
126        while (!sqf) {
127            // k = 0,1,2,-1,-2
128            if (ki >= klist.length) {
129                break;
130            }
131            k = klist[ki];
132            ki++;
133            // compute norm with x -> ( y - k x )
134            ks = k;
135            res = PolyUfdUtil.<C> norm(P, ks);
136            //System.out.println("res = " + res);
137            if (res.isZERO() || res.isConstant()) {
138                continue;
139            }
140            sqf = factorCoeff.isSquarefree(res);
141            //System.out.println("sqf("+ks+") = " + res.degree());
142            //System.out.println("resfact = " + factorCoeff.baseFactors(res) + "\n");
143        }
144        // if Res is now squarefree, else must take radical factorization
145        List<GenPolynomial<C>> nfacs;
146        if (!sqf) {
147            //System.out.println("\nres = " + res); 
148            System.out.println("sqf(" + ks + ") = " + res.degree());
149            //res = factorCoeff.squarefreePart(res); // better use obtained factors
150            //res = factorCoeff.baseFactors(res).lastKey();
151        }
152        //res = res.monic();
153        if (logger.isInfoEnabled()) {
154            logger.info("res = " + res);
155            //System.out.println("\nres = " + res); 
156        }
157        nfacs = factorCoeff.baseFactorsRadical(res);
158        if (logger.isInfoEnabled()) {
159            logger.info("res facs = " + nfacs); // Q[X]
160            //System.out.println("\nnfacs = " + nfacs); // Q[X]
161        }
162        if (nfacs.size() == 1) {
163            factors.add(P);
164            return factors;
165        }
166
167        // compute gcds of factors with polynomial in Q(alpha)[X]
168        GenPolynomial<AlgebraicNumber<C>> Pp = P;
169        //System.out.println("Pp = " + Pp);
170        GenPolynomial<AlgebraicNumber<C>> Ni;
171        for (GenPolynomial<C> nfi : nfacs) {
172            //System.out.println("nfi = " + nfi);
173            Ni = PolyUfdUtil.<C> substituteConvertToAlgebraicCoefficients(pfac, nfi, ks);
174            if (logger.isInfoEnabled()) {
175                logger.info("Ni = " + Ni);
176                //System.out.println("Pp = " + Pp);
177                //System.out.println("Ni = " + Ni);
178            }
179            // compute gcds of factors with polynomial
180            GenPolynomial<AlgebraicNumber<C>> pni = engine.gcd(Ni, Pp);
181            if (!pni.leadingBaseCoefficient().isONE()) {
182                //System.out.println("gcd(Ni,Pp) not monic " + pni);
183                pni = pni.monic();
184            }
185            if (logger.isInfoEnabled()) {
186                logger.info("gcd(Ni,Pp) = " + pni);
187                //System.out.println("gcd(Ni,Pp) = " + pni);
188            }
189            if (!pni.isONE()) {
190                factors.add(pni);
191                Pp = Pp.divide(pni);
192                //             } else {
193                //                 GenPolynomial<AlgebraicNumber<C>> qni = Pp.divide(Ni);
194                //                 GenPolynomial<AlgebraicNumber<C>> rni = Pp.remainder(Ni);
195                //                 System.out.println("div qni = " + qni);
196                //                 System.out.println("div rni = " + rni);
197                //                 continue;
198                //                 //throw new RuntimeException("gcd(Ni,Pp) == 1");
199            }
200        }
201        if (!Pp.isZERO() && !Pp.isONE()) { // irreducible rest
202            factors.add(Pp);
203        }
204        //System.out.println("afactors = " + factors);
205        return factors;
206    }
207
208}