Source code

001/*
002 * $Id: FactorAlgebraic.java 5980 2019-04-17 19:45:07Z kredel $
003 */
004
005package edu.jas.ufd;
006
007
008import java.util.ArrayList;
009import java.util.List;
010
011import org.apache.logging.log4j.Logger;
012import org.apache.logging.log4j.LogManager; 
013
014import edu.jas.poly.AlgebraicNumber;
015import edu.jas.poly.AlgebraicNumberRing;
016import edu.jas.poly.GenPolynomial;
017import edu.jas.poly.GenPolynomialRing;
018import edu.jas.poly.PolyUtil;
019import edu.jas.poly.TermOrder;
020import edu.jas.structure.GcdRingElem;
021
022
023/**
024 * Algebraic number coefficients factorization algorithms. This class implements
025 * factorization methods for polynomials over algebraic numbers over rational
026 * numbers or over (prime) modular integers.
027 * @author Heinz Kredel
028 * @param <C> coefficient type
029 */
030
031public class FactorAlgebraic<C extends GcdRingElem<C>> extends FactorAbsolute<AlgebraicNumber<C>> {
032
033
034    private static final Logger logger = LogManager.getLogger(FactorAlgebraic.class);
035
036
037    private static final boolean debug = logger.isDebugEnabled();
038
039
040    /**
041     * Factorization engine for base coefficients.
042     */
043    public final FactorAbstract<C> factorCoeff;
044
045
046    /**
047     * No argument constructor. <b>Note:</b> can't use this constructor.
048     */
049    protected FactorAlgebraic() {
050        throw new IllegalArgumentException("don't use this constructor");
051    }
052
053
054    /**
055     * Constructor.
056     * @param fac algebraic number factory.
057     */
058    public FactorAlgebraic(AlgebraicNumberRing<C> fac) {
059        this(fac, FactorFactory.<C> getImplementation(fac.ring.coFac) );
060    }
061
062
063    /**
064     * Constructor.
065     * @param fac algebraic number factory.
066     * @param factorCoeff factorization engine for polynomials over base coefficients.
067     */
068    public FactorAlgebraic(AlgebraicNumberRing<C> fac, FactorAbstract<C> factorCoeff) {
069        super(fac);
070        this.factorCoeff = factorCoeff;
071    }
072
073
074    /**
075     * GenPolynomial base factorization of a squarefree polynomial.
076     * @param P squarefree GenPolynomial&lt;AlgebraicNumber&lt;C&gt;&gt;.
077     * @return [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i.
078     */
079    @Override
080    public List<GenPolynomial<AlgebraicNumber<C>>> baseFactorsSquarefree(GenPolynomial<AlgebraicNumber<C>> P) {
081        if (P == null) {
082            throw new IllegalArgumentException(this.getClass().getName() + " P == null");
083        }
084        List<GenPolynomial<AlgebraicNumber<C>>> factors = new ArrayList<GenPolynomial<AlgebraicNumber<C>>>();
085        if (P.isZERO()) {
086            return factors;
087        }
088        if (P.isONE()) {
089            factors.add(P);
090            return factors;
091        }
092        GenPolynomialRing<AlgebraicNumber<C>> pfac = P.ring; // Q(alpha)[x]
093        if (pfac.nvar > 1) {
094            throw new IllegalArgumentException("only for univariate polynomials");
095        }
096        AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) pfac.coFac;
097        AlgebraicNumber<C> ldcf = P.leadingBaseCoefficient();
098        if (!ldcf.isONE()) {
099            P = P.monic();
100            factors.add(pfac.getONE().multiply(ldcf));
101        }
102        //System.out.println("\nP = " + P);
103        if (debug) {
104           Squarefree<AlgebraicNumber<C>> sqengine = SquarefreeFactory.<AlgebraicNumber<C>> getImplementation(afac);
105           if ( !sqengine.isSquarefree(P) ) {
106               throw new RuntimeException("P not squarefree: " + sqengine.squarefreeFactors(P));
107           }
108           GenPolynomial<C> modu = afac.modul;
109           if ( !factorCoeff.isIrreducible(modu) ) {
110               throw new RuntimeException("modul not irreducible: " + factorCoeff.factors(modu));
111           }
112           System.out.println("P squarefree and modul irreducible");
113           //GreatestCommonDivisor<AlgebraicNumber<C>> aengine //= GCDFactory.<AlgebraicNumber<C>> getProxy(afac);
114           //  = new GreatestCommonDivisorSimple<AlgebraicNumber<C>>( /*cfac.coFac*/ );
115        }
116
117        // search squarefree norm
118        long k = 0L;
119        long ks = k;
120        GenPolynomial<C> res = null;
121        boolean sqf = false;
122        //int[] klist = new int[]{ 0, 1, 2, 3, -1, -2, -3 , 5, -5, 7, -7, 101, -101, 1001, -1001 };
123        //int[] klist = new int[]{ 0, 1, 2, 3, -1, -2, -3 , 5, -5, 7, -7, 23, -23, 167, -167 };
124        //int[] klist = new int[] { 0, -1, -2, 1, 2, -3, 3 };
125        int[] klist = new int[] { 0, -1, -2, 1, 2 };
126        int ki = 0;
127        while (!sqf) {
128            // k = 0,1,2,-1,-2
129            if (ki >= klist.length) {
130                break;
131            }
132            k = klist[ki];
133            ki++;
134            // compute norm with x -> ( y - k x )
135            ks = k;
136            res = PolyUfdUtil.<C> norm(P, ks);
137            //System.out.println("res = " + res);
138            if (res.isZERO() || res.isConstant()) {
139                continue;
140            }
141            sqf = factorCoeff.isSquarefree(res);
142            //System.out.println("sqf("+ks+") = " + res.degree());
143            //System.out.println("resfact = " + factorCoeff.baseFactors(res) + "\n");
144        }
145        // if Res is now squarefree, else must take radical factorization
146        List<GenPolynomial<C>> nfacs;
147        if (!sqf) {
148            //System.out.println("\nres = " + res); 
149            System.out.println("sqf(" + ks + ") = " + res.degree());
150            //res = factorCoeff.squarefreePart(res); // better use obtained factors
151            //res = factorCoeff.baseFactors(res).lastKey();
152        }
153        //res = res.monic();
154        if (logger.isInfoEnabled()) {
155            logger.info("res = " + res);
156            //System.out.println("\nres = " + res); 
157        }
158        nfacs = factorCoeff.baseFactorsRadical(res);
159        if (logger.isInfoEnabled()) {
160            logger.info("res facs = " + nfacs); // Q[X]
161            //System.out.println("\nnfacs = " + nfacs); // Q[X]
162        }
163        if (nfacs.size() == 1) {
164            factors.add(P);
165            return factors;
166        }
167
168        // compute gcds of factors with polynomial in Q(alpha)[X]
169        GenPolynomial<AlgebraicNumber<C>> Pp = P;
170        //System.out.println("Pp = " + Pp);
171        GenPolynomial<AlgebraicNumber<C>> Ni;
172        for (GenPolynomial<C> nfi : nfacs) {
173            //System.out.println("nfi = " + nfi);
174            Ni = PolyUfdUtil.<C> substituteConvertToAlgebraicCoefficients(pfac, nfi, ks);
175            if (logger.isInfoEnabled()) {
176                logger.info("Ni = " + Ni);
177                //System.out.println("Pp = " + Pp);
178                //System.out.println("Ni = " + Ni);
179            }
180            // compute gcds of factors with polynomial
181            GenPolynomial<AlgebraicNumber<C>> pni = engine.gcd(Ni, Pp);
182            if (!pni.leadingBaseCoefficient().isONE()) {
183                //System.out.println("gcd(Ni,Pp) not monic " + pni);
184                pni = pni.monic();
185            }
186            if (logger.isInfoEnabled()) {
187                logger.info("gcd(Ni,Pp) = " + pni);
188                //System.out.println("gcd(Ni,Pp) = " + pni);
189            }
190            if (!pni.isONE()) {
191                factors.add(pni);
192                Pp = Pp.divide(pni);
193            }
194        }
195        if (!Pp.isZERO() && !Pp.isONE()) { // irreducible rest
196            factors.add(Pp);
197        }
198        //System.out.println("afactors = " + factors);
199        return factors;
200    }
201
202
203    /**
204     * GenPolynomial factorization of a squarefree polynomial.
205     * @param P squarefree and primitive! (respectively monic) GenPolynomial&lt;AlgebraicNumber&lt;C&gt;&gt;.
206     * @return [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i.
207     */
208    @Override
209    public List<GenPolynomial<AlgebraicNumber<C>>> factorsSquarefree(GenPolynomial<AlgebraicNumber<C>> P) {
210        if (P == null) {
211            throw new IllegalArgumentException(this.getClass().getName() + " P == null");
212        }
213        List<GenPolynomial<AlgebraicNumber<C>>> factors = new ArrayList<GenPolynomial<AlgebraicNumber<C>>>();
214        if (P.isZERO()) {
215            return factors;
216        }
217        if (P.isONE()) {
218            factors.add(P);
219            return factors;
220        }
221        GenPolynomialRing<AlgebraicNumber<C>> pfac = P.ring; // Q(alpha)[x1,...,xn]
222        if (pfac.nvar <= 1) {
223            throw new IllegalArgumentException("only for multivariate polynomials");
224        }
225        AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) pfac.coFac;
226        AlgebraicNumber<C> ldcf = P.leadingBaseCoefficient();
227        if (!ldcf.isONE()) {
228            P = P.monic();
229            factors.add(pfac.getONE().multiply(ldcf));
230        }
231        if (P.degreeVector().totalDeg() <= 1L) {
232            factors.add(P);
233            return factors;
234        }
235        //System.out.println("\nP = " + P);
236
237        // search squarefree norm
238        long k = 0L;
239        long ks = k;
240        GenPolynomial<C> res = null;
241        boolean sqf = false;
242        //int[] klist = new int[]{ 0, 1, 2, 3, -1, -2, -3 , 5, -5, 7, -7, 101, -101, 1001, -1001 };
243        //int[] klist = new int[]{ 0, 1, 2, 3, -1, -2, -3 , 5, -5, 7, -7, 23, -23, 167, -167 };
244        //int[] klist = new int[] { 0, -1, -2, 1, 2, -3, 3 };
245        int[] klist = new int[] { 0, -1, -2, 1, 2 };
246        int ki = 0;
247        while (!sqf) {
248            // k = 0,1,2,-1,-2
249            if (ki >= klist.length) {
250                System.out.println("sqf("+ks+") = " + res.degree() + ", sqf = " + sqf);
251                break;
252            }
253            k = klist[ki];
254            ki++;
255            // compute norm with x -> ( y - k x )
256            ks = k;
257            res = PolyUfdUtil.<C> norm(P, ks);
258            //System.out.println("res = " + res);
259            if (res.isZERO() || res.isConstant()) {
260                continue;
261            }
262            sqf = factorCoeff.isSquarefree(res);
263            //System.out.println("resfact = " + factorCoeff.factors(res) + "\n");
264        }
265        // if Res is now squarefree, else must take radical factorization
266        List<GenPolynomial<C>> nfacs;
267        //if (!sqf) {
268            //System.out.println("\nnot squarefree???"); 
269            //System.out.println("\nres = " + res); 
270            //System.out.println("sqf(" + ks + ") = " + res.degree());
271            //res = factorCoeff.squarefreePart(res); // better use obtained factors
272            //res = factorCoeff.baseFactors(res).lastKey();
273        //}
274        //res = res.monic();
275        if (logger.isInfoEnabled()) {
276            logger.info("res = " + res);
277            //System.out.println("\nres = " + res); 
278            logger.info("factorCoeff = " + factorCoeff);
279        }
280        nfacs = factorCoeff.factorsRadical(res);
281        //System.out.println("\nnfacs = " + nfacs); // Q[X]
282        if (logger.isInfoEnabled()) {
283            logger.info("res facs = " + nfacs); // Q[X]
284        }
285        if (nfacs.size() == 1) {
286            factors.add(P);
287            return factors;
288        }
289        
290        // compute gcds of factors with polynomial in Q(alpha)[X]
291        GenPolynomial<AlgebraicNumber<C>> Pp = P;
292        //System.out.println("Pp = " + Pp);
293        GenPolynomial<AlgebraicNumber<C>> Ni;
294        for (GenPolynomial<C> nfi : nfacs) {
295            //System.out.println("nfi = " + nfi);
296            Ni = PolyUfdUtil.<C> substituteConvertToAlgebraicCoefficients(pfac, nfi, ks);
297            if (logger.isInfoEnabled()) {
298                logger.info("Ni = " + Ni);
299                //System.out.println("Pp = " + Pp);
300            }
301            //System.out.println("Ni = " + Ni);
302            // compute gcds of factors with polynomial
303            GenPolynomial<AlgebraicNumber<C>> pni = engine.gcd(Ni, Pp);
304            if (!pni.leadingBaseCoefficient().isONE()) {
305                //System.out.println("gcd(Ni,Pp) not monic " + pni);
306                pni = pni.monic();
307            }
308            if (logger.isInfoEnabled()) {
309                logger.info("gcd(Ni,Pp) = " + pni);
310            }
311            //System.out.println("gcd(Ni,Pp) = " + pni);
312            if (!pni.isONE()) {
313                factors.add(pni);
314                Pp = Pp.divide(pni);
315            }
316        }
317        if (!Pp.isZERO() && !Pp.isONE()) { // irreducible rest
318            factors.add(Pp);
319        }
320        //factors.add(P);
321        return factors;
322    }
323
324}