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