Source code

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