Source code

001/*
002 * $Id: SquarefreeInfiniteFieldCharP.java 5936 2018-09-30 19:20:14Z kredel $
003 */
004
005package edu.jas.ufd;
006
007
008import java.util.Map;
009import java.util.SortedMap;
010import java.util.TreeMap;
011
012import org.apache.logging.log4j.Logger;
013import org.apache.logging.log4j.LogManager; 
014
015import edu.jas.poly.ExpVector;
016import edu.jas.poly.GenPolynomial;
017import edu.jas.poly.GenPolynomialRing;
018import edu.jas.poly.Monomial;
019import edu.jas.poly.PolyUtil;
020import edu.jas.structure.GcdRingElem;
021import edu.jas.structure.RingFactory;
022
023
024/**
025 * Squarefree decomposition for infinite coefficient fields of characteristic p.
026 * @author Heinz Kredel
027 */
028
029public class SquarefreeInfiniteFieldCharP<C extends GcdRingElem<C>>
030                extends SquarefreeFieldCharP<Quotient<C>> {
031
032
033    private static final Logger logger = LogManager.getLogger(SquarefreeInfiniteFieldCharP.class);
034
035
036    //private static final boolean debug = logger.isDebugEnabled();
037
038
039    /**
040     * Squarefree engine for infinite ring of characteristic p base
041     * coefficients.
042     */
043    protected final SquarefreeAbstract<C> qengine;
044
045
046    /**
047     * Constructor.
048     */
049    @SuppressWarnings("unchecked")
050    public SquarefreeInfiniteFieldCharP(RingFactory<Quotient<C>> fac) {
051        super(fac);
052        // isFinite() predicate now present
053        if (fac.isFinite()) {
054            throw new IllegalArgumentException("fac must be in-finite");
055        }
056        QuotientRing<C> qfac = (QuotientRing<C>) fac;
057        GenPolynomialRing<C> rfac = qfac.ring;
058        qengine = (SquarefreeAbstract) SquarefreeFactory.<C> getImplementation(rfac);
059        //qengine = new SquarefreeFiniteFieldCharP<C>(rfac.coFac);
060        //qengine = new SquarefreeInfiniteRingCharP<C>( rfac.coFac );
061    }
062
063
064    /* --------- quotient char-th roots --------------------- */
065
066
067    /**
068     * Squarefree factors of a Quotient.
069     * @param P Quotient.
070     * @return [p_1 -&gt; e_1,...,p_k - &gt; e_k] with P = prod_{i=1, ..., k}
071     *         p_i**e_k.
072     */
073    @Override
074    public SortedMap<Quotient<C>, Long> squarefreeFactors(Quotient<C> P) {
075        if (P == null) {
076            throw new IllegalArgumentException(this.getClass().getName() + " P == null");
077        }
078        SortedMap<Quotient<C>, Long> factors = new TreeMap<Quotient<C>, Long>();
079        if (P.isZERO()) {
080            return factors;
081        }
082        if (P.isONE()) {
083            factors.put(P, 1L);
084            return factors;
085        }
086        GenPolynomial<C> num = P.num;
087        GenPolynomial<C> den = P.den;
088        QuotientRing<C> pfac = P.ring;
089        GenPolynomial<C> one = pfac.ring.getONE();
090        if (!num.isONE()) {
091            SortedMap<GenPolynomial<C>, Long> nfac = qengine.squarefreeFactors(num);
092            //System.out.println("nfac = " + nfac);
093            for (Map.Entry<GenPolynomial<C>, Long> me : nfac.entrySet()) {
094                GenPolynomial<C> nfp = me.getKey();
095                Quotient<C> nf = new Quotient<C>(pfac, nfp);
096                factors.put(nf, me.getValue()); //nfac.get(nfp));
097            }
098        }
099        if (den.isONE()) {
100            if (factors.size() == 0) {
101                factors.put(P, 1L);
102            }
103            return factors;
104        }
105        SortedMap<GenPolynomial<C>, Long> dfac = qengine.squarefreeFactors(den);
106        //System.out.println("dfac = " + dfac);
107        for (Map.Entry<GenPolynomial<C>, Long> me : dfac.entrySet()) {
108            GenPolynomial<C> dfp = me.getKey();
109            Quotient<C> df = new Quotient<C>(pfac, one, dfp);
110            factors.put(df, me.getValue()); //dfac.get(dfp));
111        }
112        if (factors.size() == 0) {
113            factors.put(P, 1L);
114        }
115        return factors;
116    }
117
118
119    /**
120     * Characteristics root of a Quotient.
121     * @param P Quotient.
122     * @return [p -&gt; k] if exists k with e=charactristic(P)*k and P = p**e,
123     *         else null.
124     */
125    public SortedMap<Quotient<C>, Long> rootCharacteristic(Quotient<C> P) {
126        if (P == null) {
127            throw new IllegalArgumentException(this.getClass().getName() + " P == null");
128        }
129        java.math.BigInteger c = P.ring.characteristic();
130        if (c.signum() == 0) {
131            return null;
132        }
133        SortedMap<Quotient<C>, Long> root = new TreeMap<Quotient<C>, Long>();
134        if (P.isZERO()) {
135            return root;
136        }
137        if (P.isONE()) {
138            root.put(P, 1L);
139            return root;
140        }
141        SortedMap<Quotient<C>, Long> sf = squarefreeFactors(P);
142        if (sf.size() == 0) {
143            return null;
144        }
145        if (logger.isInfoEnabled()) {
146            logger.info("sf,quot = " + sf);
147        }
148        // better: test if sf.size() == 2 // no, since num and den factors 
149        Long k = null;
150        Long cl = c.longValue();
151        for (Map.Entry<Quotient<C>, Long> me : sf.entrySet()) {
152            Quotient<C> p = me.getKey();
153            //System.out.println("p = " + p);
154            if (p.isConstant()) { // todo: check for non-constants in coefficients
155                continue;
156            }
157            Long e = me.getValue(); //sf.get(p);
158            long E = e.longValue();
159            long r = E % cl;
160            if (r != 0) {
161                //System.out.println("r = " + r);
162                return null;
163            }
164            if (k == null) {
165                k = e;
166            } else if (k >= e) {
167                k = e;
168            }
169        }
170        if (k == null) {
171            k = 1L; //return null;
172        }
173        // now c divides all exponents of non constant elements
174        for (Map.Entry<Quotient<C>, Long> me : sf.entrySet()) {
175            Quotient<C> q = me.getKey();
176            Long e = me.getValue(); //sf.get(q);
177            //System.out.println("q = " + q + ", e = " + e);
178            if (e >= k) {
179                e = e / cl;
180                //q = q.power(e);
181                root.put(q, e);
182            } else { // constant case
183                root.put(q, e);
184            }
185        }
186        //System.out.println("root = " + root);
187        return root;
188    }
189
190
191    /**
192     * GenPolynomial char-th root main variable.
193     * @param P univariate GenPolynomial with Quotient coefficients.
194     * @return char-th_rootOf(P), or null, if P is no char-th root.
195     */
196    public GenPolynomial<Quotient<C>> rootCharacteristic(GenPolynomial<Quotient<C>> P) {
197        if (P == null || P.isZERO()) {
198            return P;
199        }
200        GenPolynomialRing<Quotient<C>> pfac = P.ring;
201        if (pfac.nvar > 1) {
202            // go to recursion
203            GenPolynomialRing<GenPolynomial<Quotient<C>>> rfac = pfac.recursive(1);
204            GenPolynomial<GenPolynomial<Quotient<C>>> Pr = PolyUtil.<Quotient<C>> recursive(rfac, P);
205            GenPolynomial<GenPolynomial<Quotient<C>>> Prc = recursiveUnivariateRootCharacteristic(Pr);
206            if (Prc == null) {
207                return null;
208            }
209            GenPolynomial<Quotient<C>> D = PolyUtil.<Quotient<C>> distribute(pfac, Prc);
210            return D;
211        }
212        RingFactory<Quotient<C>> rf = pfac.coFac;
213        if (rf.characteristic().signum() != 1) {
214            // basePthRoot not possible
215            throw new IllegalArgumentException(
216                            P.getClass().getName() + " only for ModInteger polynomials " + rf);
217        }
218        long mp = rf.characteristic().longValue();
219        GenPolynomial<Quotient<C>> d = pfac.getZERO().copy();
220        for (Monomial<Quotient<C>> m : P) {
221            ExpVector f = m.e;
222            long fl = f.getVal(0);
223            if (fl % mp != 0) {
224                return null;
225            }
226            fl = fl / mp;
227            SortedMap<Quotient<C>, Long> sm = rootCharacteristic(m.c);
228            if (sm == null) {
229                return null;
230            }
231            if (logger.isInfoEnabled()) {
232                logger.info("sm,root = " + sm);
233            }
234            Quotient<C> r = rf.getONE();
235            for (Map.Entry<Quotient<C>, Long> me : sm.entrySet()) {
236                Quotient<C> rp = me.getKey();
237                long gl = me.getValue(); // sm.get(rp);
238                if (gl > 1) {
239                    rp = rp.power(gl);
240                }
241                r = r.multiply(rp);
242            }
243            ExpVector e = ExpVector.create(1, 0, fl);
244            d.doPutToMap(e, r);
245        }
246        logger.info("sm,root,d = " + d);
247        return d;
248    }
249
250
251    /**
252     * GenPolynomial char-th root univariate polynomial.
253     * @param P GenPolynomial.
254     * @return char-th_rootOf(P).
255     */
256    @Override
257    public GenPolynomial<Quotient<C>> baseRootCharacteristic(GenPolynomial<Quotient<C>> P) {
258        if (P == null || P.isZERO()) {
259            return P;
260        }
261        GenPolynomialRing<Quotient<C>> pfac = P.ring;
262        if (pfac.nvar > 1) {
263            // basePthRoot not possible by return type
264            throw new IllegalArgumentException(P.getClass().getName() + " only for univariate polynomials");
265        }
266        RingFactory<Quotient<C>> rf = pfac.coFac;
267        if (rf.characteristic().signum() != 1) {
268            // basePthRoot not possible
269            throw new IllegalArgumentException(P.getClass().getName() + " only for char p > 0 " + rf);
270        }
271        long mp = rf.characteristic().longValue();
272        GenPolynomial<Quotient<C>> d = pfac.getZERO().copy();
273        for (Monomial<Quotient<C>> m : P) {
274            //System.out.println("m = " + m);
275            ExpVector f = m.e;
276            long fl = f.getVal(0);
277            if (fl % mp != 0) {
278                return null;
279            }
280            fl = fl / mp;
281            SortedMap<Quotient<C>, Long> sm = rootCharacteristic(m.c);
282            if (sm == null) {
283                return null;
284            }
285            if (logger.isInfoEnabled()) {
286                logger.info("sm,base,root = " + sm);
287            }
288            Quotient<C> r = rf.getONE();
289            for (Map.Entry<Quotient<C>, Long> me : sm.entrySet()) {
290                Quotient<C> rp = me.getKey();
291                //System.out.println("rp = " + rp);
292                long gl = me.getValue(); //sm.get(rp);
293                //System.out.println("gl = " + gl);
294                Quotient<C> re = rp;
295                if (gl > 1) {
296                    re = rp.power(gl);
297                }
298                //System.out.println("re = " + re);
299                r = r.multiply(re);
300            }
301            ExpVector e = ExpVector.create(1, 0, fl);
302            d.doPutToMap(e, r);
303        }
304        if (logger.isInfoEnabled()) {
305            logger.info("sm,base,d = " + d);
306        }
307        return d;
308    }
309
310
311    /**
312     * GenPolynomial char-th root univariate polynomial with polynomial
313     * coefficients.
314     * @param P recursive univariate GenPolynomial.
315     * @return char-th_rootOf(P), or null if P is no char-th root.
316     */
317    @Override
318    public GenPolynomial<GenPolynomial<Quotient<C>>> recursiveUnivariateRootCharacteristic(
319                    GenPolynomial<GenPolynomial<Quotient<C>>> P) {
320        if (P == null || P.isZERO()) {
321            return P;
322        }
323        GenPolynomialRing<GenPolynomial<Quotient<C>>> pfac = P.ring;
324        if (pfac.nvar > 1) {
325            // basePthRoot not possible by return type
326            throw new IllegalArgumentException(
327                            P.getClass().getName() + " only for univariate recursive polynomials");
328        }
329        RingFactory<GenPolynomial<Quotient<C>>> rf = pfac.coFac;
330        if (rf.characteristic().signum() != 1) {
331            // basePthRoot not possible
332            throw new IllegalArgumentException(P.getClass().getName() + " only for char p > 0 " + rf);
333        }
334        long mp = rf.characteristic().longValue();
335        GenPolynomial<GenPolynomial<Quotient<C>>> d = pfac.getZERO().copy();
336        for (Monomial<GenPolynomial<Quotient<C>>> m : P) {
337            ExpVector f = m.e;
338            long fl = f.getVal(0);
339            if (fl % mp != 0) {
340                return null;
341            }
342            fl = fl / mp;
343            GenPolynomial<Quotient<C>> r = rootCharacteristic(m.c);
344            if (r == null) {
345                return null;
346            }
347            ExpVector e = ExpVector.create(1, 0, fl);
348            d.doPutToMap(e, r);
349        }
350        return d;
351    }
352
353}