Source code

001/*
002 * $Id: FactorModular.java 5997 2020-03-17 15:34:31Z kredel $
003 */
004
005package edu.jas.ufd;
006
007
008import java.util.ArrayList;
009import java.util.List;
010import java.util.Map;
011import java.util.SortedMap;
012import java.util.SortedSet;
013import java.util.TreeMap;
014import java.util.TreeSet;
015
016import org.apache.logging.log4j.LogManager;
017import org.apache.logging.log4j.Logger;
018
019import edu.jas.arith.BigInteger;
020import edu.jas.arith.ModLongRing;
021import edu.jas.arith.Modular;
022import edu.jas.arith.ModularRingFactory;
023import edu.jas.poly.GenPolynomial;
024import edu.jas.poly.GenPolynomialRing;
025import edu.jas.poly.PolyUtil;
026import edu.jas.structure.GcdRingElem;
027import edu.jas.structure.Power;
028import edu.jas.structure.RingFactory;
029
030
031/**
032 * Modular coefficients factorization algorithms. This class implements
033 * factorization methods for polynomials over (prime) modular integers.
034 * @author Heinz Kredel
035 */
036
037public class FactorModular<MOD extends GcdRingElem<MOD> & Modular> extends FactorAbsolute<MOD> {
038
039
040    private static final Logger logger = LogManager.getLogger(FactorModular.class);
041
042
043    private static final boolean debug = logger.isDebugEnabled();
044
045
046    /**
047     * No argument constructor, do not use.
048     */
049    @SuppressWarnings({ "unchecked", "unused" })
050    private FactorModular() {
051        this((RingFactory<MOD>) (Object) new ModLongRing(13, true)); // hack, 13 unimportant
052    }
053
054
055    /**
056     * Constructor.
057     * @param cfac coefficient ring factory.
058     */
059    public FactorModular(RingFactory<MOD> cfac) {
060        super(cfac);
061    }
062
063
064    /**
065     * GenPolynomial base distinct degree factorization.
066     * @param P squarefree and monic GenPolynomial.
067     * @return [e_1 -&gt; p_1, ..., e_k -&gt; p_k] with P = prod_{i=1,...,k} p_i
068     *         and p_i has only irreducible factors of degree e_i.
069     */
070    public SortedMap<Long, GenPolynomial<MOD>> baseDistinctDegreeFactors(GenPolynomial<MOD> P) {
071        if (P == null) {
072            throw new IllegalArgumentException(this.getClass().getName() + " P != null");
073        }
074        SortedMap<Long, GenPolynomial<MOD>> facs = new TreeMap<Long, GenPolynomial<MOD>>();
075        if (P.isZERO()) {
076            return facs;
077        }
078        GenPolynomialRing<MOD> pfac = P.ring;
079        if (pfac.nvar > 1) {
080            throw new IllegalArgumentException(
081                            this.getClass().getName() + " only for univariate polynomials");
082        }
083        ModularRingFactory<MOD> mr = (ModularRingFactory<MOD>) pfac.coFac;
084        java.math.BigInteger m = mr.getIntegerModul().getVal();
085        //if (m.longValue() == 2L) {
086        //    logger.warn(this.getClass().getName() + " case p = 2 not implemented");
087        //}
088        GenPolynomial<MOD> x = pfac.univariate(0);
089        GenPolynomial<MOD> h = x;
090        GenPolynomial<MOD> f = P;
091        GenPolynomial<MOD> g;
092        Power<GenPolynomial<MOD>> pow = new Power<GenPolynomial<MOD>>(pfac);
093        long d = 0;
094        while (d + 1 <= f.degree(0) / 2) {
095            d++;
096            h = pow.modPower(h, m, f);
097            g = engine.gcd(h.subtract(x), f);
098            if (!g.isONE()) {
099                facs.put(d, g);
100                f = f.divide(g);
101            }
102        }
103        if (!f.isONE()) {
104            d = f.degree(0);
105            facs.put(d, f);
106        }
107        return facs;
108    }
109
110
111    /**
112     * GenPolynomial base equal degree factorization.
113     * @param P squarefree and monic GenPolynomial.
114     * @param deg such that P has only irreducible factors of degree deg.
115     * @return [p_1,...,p_k] with P = prod_{i=1,...,r} p_i.
116     */
117    public List<GenPolynomial<MOD>> baseEqualDegreeFactors(GenPolynomial<MOD> P, long deg) {
118        if (P == null) {
119            throw new IllegalArgumentException(this.getClass().getName() + " P != null");
120        }
121        List<GenPolynomial<MOD>> facs = new ArrayList<GenPolynomial<MOD>>();
122        if (P.isZERO()) {
123            return facs;
124        }
125        GenPolynomialRing<MOD> pfac = P.ring;
126        if (pfac.nvar > 1) {
127            throw new IllegalArgumentException(
128                            this.getClass().getName() + " only for univariate polynomials");
129        }
130        if (P.degree(0) == deg) {
131            facs.add(P);
132            return facs;
133        }
134        ModularRingFactory<MOD> mr = (ModularRingFactory<MOD>) pfac.coFac;
135        java.math.BigInteger m = mr.getIntegerModul().getVal();
136        //System.out.println("m = " + m);
137        boolean p2 = false;
138        if (m.equals(java.math.BigInteger.valueOf(2L))) {
139            p2 = true;
140            //throw new RuntimeException(this.getClass().getName() + " case p = 2 not implemented");
141        }
142        GenPolynomial<MOD> one = pfac.getONE();
143        GenPolynomial<MOD> t = pfac.univariate(0, 1L);
144        GenPolynomial<MOD> r;
145        GenPolynomial<MOD> h;
146        GenPolynomial<MOD> f = P;
147        //GreatestCommonDivisor<MOD> engine = GCDFactory.<MOD> getImplementation(pfac.coFac);
148        Power<GenPolynomial<MOD>> pow = new Power<GenPolynomial<MOD>>(pfac);
149        GenPolynomial<MOD> g = null;
150        int degi = (int) deg; //f.degree(0);
151        //System.out.println("deg = " + deg);
152        BigInteger di = (new BigInteger(m)).power(deg);
153        //System.out.println("di = " + di);
154        java.math.BigInteger d = di.getVal(); //.longValue()-1;
155        //System.out.println("d = " + d);
156        d = d.shiftRight(1); // divide by 2
157        do {
158            if (p2) {
159                h = t;
160                for (int i = 1; i < degi; i++) {
161                    h = t.sum(h.multiply(h));
162                    h = h.remainder(f);
163                }
164                t = t.multiply(pfac.univariate(0, 2L));
165                //System.out.println("h = " + h);
166            } else {
167                r = pfac.random(17, degi, 2 * degi, 1.0f);
168                if (r.degree(0) >= f.degree(0)) {
169                    r = r.remainder(f);
170                }
171                r = r.monic();
172                //System.out.println("r = " + r);
173                h = pow.modPower(r, d, f).subtract(one);
174                degi++;
175            }
176            g = engine.gcd(h, f);
177            //System.out.println("g = " + g);
178        } while (g.degree(0) == 0 || g.degree(0) == f.degree(0));
179        f = f.divide(g);
180        facs.addAll(baseEqualDegreeFactors(f, deg));
181        facs.addAll(baseEqualDegreeFactors(g, deg));
182        return facs;
183    }
184
185
186    /**
187     * GenPolynomial base factorization of a squarefree polynomial.
188     * @param P squarefree and monic! GenPolynomial.
189     * @return [p_1,...,p_k] with P = prod_{i=1,...,r} p_i.
190     */
191    @Override
192    public List<GenPolynomial<MOD>> baseFactorsSquarefree(GenPolynomial<MOD> P) {
193        if (P == null) {
194            throw new IllegalArgumentException(this.getClass().getName() + " P == null");
195        }
196        List<GenPolynomial<MOD>> factors = new ArrayList<GenPolynomial<MOD>>();
197        if (P.isZERO()) {
198            return factors;
199        }
200        if (P.isONE()) {
201            factors.add(P);
202            return factors;
203        }
204        GenPolynomialRing<MOD> pfac = P.ring;
205        if (pfac.nvar > 1) {
206            throw new IllegalArgumentException(
207                            this.getClass().getName() + " only for univariate polynomials");
208        }
209        if (!P.leadingBaseCoefficient().isONE()) {
210            throw new IllegalArgumentException("ldcf(P) != 1: " + P);
211        }
212        SortedMap<Long, GenPolynomial<MOD>> dfacs = baseDistinctDegreeFactors(P);
213        if (debug) {
214            logger.info("dfacs    = " + dfacs);
215            //System.out.println("dfacs    = " + dfacs);
216        }
217        for (Map.Entry<Long, GenPolynomial<MOD>> me : dfacs.entrySet()) {
218            Long e = me.getKey();
219            GenPolynomial<MOD> f = me.getValue(); // dfacs.get(e);
220            List<GenPolynomial<MOD>> efacs = baseEqualDegreeFactors(f, e);
221            if (debug) {
222                logger.info("efacs " + e + "   = " + efacs);
223                //System.out.println("efacs " + e + "   = " + efacs);
224            }
225            factors.addAll(efacs);
226        }
227        //System.out.println("factors  = " + factors);
228        factors = PolyUtil.<MOD> monic(factors);
229        SortedSet<GenPolynomial<MOD>> ss = new TreeSet<GenPolynomial<MOD>>(factors);
230        //System.out.println("sorted   = " + ss);
231        factors.clear();
232        factors.addAll(ss);
233        return factors;
234    }
235
236}