Source code

001/*
002 * $Id: SquarefreeFiniteFieldCharP.java 5871 2018-07-20 15:58:45Z 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.arith.BigInteger;
016import edu.jas.poly.ExpVector;
017import edu.jas.poly.GenPolynomial;
018import edu.jas.poly.GenPolynomialRing;
019import edu.jas.poly.Monomial;
020import edu.jas.structure.GcdRingElem;
021import edu.jas.structure.Power;
022import edu.jas.structure.RingFactory;
023
024
025/**
026 * Squarefree decomposition for finite coefficient fields of characteristic p.
027 * @author Heinz Kredel
028 */
029
030public class SquarefreeFiniteFieldCharP<C extends GcdRingElem<C>> extends SquarefreeFieldCharP<C> {
031
032
033    private static final Logger logger = LogManager.getLogger(SquarefreeFiniteFieldCharP.class);
034
035
036    //private static final boolean debug = logger.isDebugEnabled();
037
038
039    /**
040     * Constructor.
041     */
042    public SquarefreeFiniteFieldCharP(RingFactory<C> fac) {
043        super(fac);
044        // isFinite() predicate now present
045        if (!fac.isFinite()) {
046            throw new IllegalArgumentException("fac must be finite");
047        }
048    }
049
050
051    /* --------- char-th roots --------------------- */
052
053    /**
054     * Characteristics root of a coefficient. <b>Note:</b> not needed at the
055     * moment.
056     * @param p coefficient.
057     * @return [p -&gt; k] if exists k with e=k*charactristic(c) and c = p**e,
058     *         else null.
059     */
060    public SortedMap<C, Long> rootCharacteristic(C p) {
061        if (p == null) {
062            throw new IllegalArgumentException(this.getClass().getName() + " p == null");
063        }
064        // already checked in constructor:
065        //java.math.BigInteger c = p.factory().characteristic();
066        //if ( c.signum() == 0 ) {
067        //    return null;
068        //}
069        SortedMap<C, Long> root = new TreeMap<C, Long>();
070        if (p.isZERO()) {
071            return root;
072        }
073        // true for finite fields:
074        root.put(p, 1L);
075        return root;
076    }
077
078
079    /**
080     * Characteristics root of a coefficient.
081     * @param c coefficient.
082     * @return r with r**p == c, if such an r exists, else null.
083     */
084    public C coeffRootCharacteristic(C c) {
085        if (c == null || c.isZERO()) {
086            return c;
087        }
088        C r = c;
089        if (aCoFac == null && qCoFac == null) {
090            // case ModInteger: c**p == c
091            return r;
092        }
093        if (aCoFac != null) {
094            // case AlgebraicNumber<ModInteger>: r = c**(p**(d-1)), r**p == c
095            long d = aCoFac.totalExtensionDegree();
096            //System.out.println("d = " + d);
097            if (d <= 1) {
098                return r;
099            }
100            BigInteger p = new BigInteger(aCoFac.characteristic());
101            BigInteger q = p.power(d - 1);
102            //System.out.println("p**(d-1) = " + q);
103            r = Power.<C> positivePower(r, q.getVal()); // r = r.power(q.getVal());
104            //System.out.println("r**q = " + r);
105            return r;
106        }
107        if (qCoFac != null) {
108            throw new UnsupportedOperationException("case QuotientRing not yet implemented");
109        }
110        return r;
111    }
112
113
114    /**
115     * Characteristics root of a polynomial. <b>Note:</b> call only in
116     * recursion.
117     * @param P polynomial.
118     * @return [p -&gt; k] if exists k with e=k*charactristic(P) and P = p**e,
119     *         else null.
120     */
121    public SortedMap<GenPolynomial<C>, Long> rootCharacteristic(GenPolynomial<C> P) {
122        if (P == null) {
123            throw new IllegalArgumentException(this.getClass().getName() + " P == null");
124        }
125        java.math.BigInteger c = P.ring.characteristic();
126        if (c.signum() == 0) {
127            return null;
128        }
129        SortedMap<GenPolynomial<C>, Long> root = new TreeMap<GenPolynomial<C>, Long>();
130        if (P.isZERO()) {
131            return root;
132        }
133        if (P.isONE()) {
134            root.put(P, 1L);
135            return root;
136        }
137        SortedMap<GenPolynomial<C>, Long> sf = squarefreeFactors(P);
138        if (logger.isInfoEnabled()) {
139            logger.info("sf = " + sf);
140        }
141        // better: test if sf.size() == 1 // not ok
142        Long k = null;
143        for (Map.Entry<GenPolynomial<C>, Long> me : sf.entrySet()) {
144            GenPolynomial<C> p = me.getKey();
145            if (p.isConstant()) {
146                //System.out.println("p,const = " + p);
147                continue;
148            }
149            Long e = me.getValue(); //sf.get(p);
150            java.math.BigInteger E = new java.math.BigInteger(e.toString());
151            java.math.BigInteger r = E.remainder(c);
152            if (!r.equals(java.math.BigInteger.ZERO)) {
153                //System.out.println("r = " + r);
154                return null;
155            }
156            if (k == null) {
157                k = e;
158            } else if (k.compareTo(e) >= 0) {
159                k = e;
160            }
161        }
162        // now c divides all exponents
163        Long cl = c.longValue();
164        GenPolynomial<C> rp = P.ring.getONE();
165        for (Map.Entry<GenPolynomial<C>, Long> me : sf.entrySet()) {
166            GenPolynomial<C> q = me.getKey();
167            Long e = me.getValue(); // sf.get(q);
168            if (q.isConstant()) { // ensure p-th root
169                C qc = q.leadingBaseCoefficient();
170                //System.out.println("qc,const = " + qc + ", e = " + e);
171                if (e > 1L) {
172                    qc = qc.power(e); //Power.<C> positivePower(qc, e);
173                    //e = 1L;
174                }
175                C qr = coeffRootCharacteristic(qc);
176                //System.out.println("qr,const = " + qr);
177                q = P.ring.getONE().multiply(qr);
178                root.put(q, 1L);
179                continue;
180            }
181            if (e > k) {
182                long ep = e / cl;
183                q = q.power(ep); //Power.<GenPolynomial<C>> positivePower(q, ep);
184            }
185            rp = rp.multiply(q);
186        }
187        if (k != null) {
188            k = k / cl;
189            root.put(rp, k);
190        }
191        //System.out.println("sf,root = " + root);
192        return root;
193    }
194
195
196    /**
197     * GenPolynomial char-th root univariate polynomial. Base coefficient type
198     * must be finite field, that is ModInteger or
199     * AlgebraicNumber&lt;ModInteger&gt; etc.
200     * @param P GenPolynomial.
201     * @return char-th_rootOf(P), or null if no char-th root.
202     */
203    @Override
204    public GenPolynomial<C> baseRootCharacteristic(GenPolynomial<C> P) {
205        if (P == null || P.isZERO()) {
206            return P;
207        }
208        GenPolynomialRing<C> pfac = P.ring;
209        if (pfac.nvar > 1) {
210            // basePthRoot not possible by return type
211            throw new IllegalArgumentException(P.getClass().getName() + " only for univariate polynomials");
212        }
213        RingFactory<C> rf = pfac.coFac;
214        if (rf.characteristic().signum() != 1) {
215            // basePthRoot not possible
216            throw new IllegalArgumentException(P.getClass().getName() + " only for char p > 0 " + rf);
217        }
218        long mp = rf.characteristic().longValue();
219        GenPolynomial<C> d = pfac.getZERO().copy();
220        for (Monomial<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            ExpVector e = ExpVector.create(1, 0, fl);
228            // for m.c exists a char-th root, since finite field
229            C r = coeffRootCharacteristic(m.c);
230            d.doPutToMap(e, r);
231        }
232        return d;
233    }
234
235
236    /**
237     * GenPolynomial char-th root univariate polynomial with polynomial
238     * coefficients.
239     * @param P recursive univariate GenPolynomial.
240     * @return char-th_rootOf(P), or null if P is no char-th root.
241     */
242    @Override
243    public GenPolynomial<GenPolynomial<C>> recursiveUnivariateRootCharacteristic(
244                    GenPolynomial<GenPolynomial<C>> P) {
245        if (P == null || P.isZERO()) {
246            return P;
247        }
248        GenPolynomialRing<GenPolynomial<C>> pfac = P.ring;
249        if (pfac.nvar > 1) {
250            // basePthRoot not possible by return type
251            throw new IllegalArgumentException(P.getClass().getName() + " only for univariate polynomials");
252        }
253        RingFactory<GenPolynomial<C>> rf = pfac.coFac;
254        if (rf.characteristic().signum() != 1) {
255            // basePthRoot not possible
256            throw new IllegalArgumentException(P.getClass().getName() + " only for char p > 0 " + rf);
257        }
258        long mp = rf.characteristic().longValue();
259        GenPolynomial<GenPolynomial<C>> d = pfac.getZERO().copy();
260        for (Monomial<GenPolynomial<C>> m : P) {
261            ExpVector f = m.e;
262            long fl = f.getVal(0);
263            if (fl % mp != 0) {
264                return null;
265            }
266            fl = fl / mp;
267            SortedMap<GenPolynomial<C>, Long> sm = rootCharacteristic(m.c);
268            if (sm == null) {
269                return null;
270            }
271            if (logger.isInfoEnabled()) {
272                logger.info("sm,rec = " + sm);
273            }
274            GenPolynomial<C> r = rf.getONE();
275            for (Map.Entry<GenPolynomial<C>, Long> me : sm.entrySet()) {
276                GenPolynomial<C> rp = me.getKey();
277                long gl = me.getValue(); //sm.get(rp);
278                if (gl > 1) {
279                    rp = rp.power(gl); //Power.<GenPolynomial<C>> positivePower(rp, gl);
280                }
281                r = r.multiply(rp);
282            }
283            ExpVector e = ExpVector.create(1, 0, fl);
284            //System.out.println("put-root r = " + r + ", e = " + e);
285            d.doPutToMap(e, r);
286        }
287        return d;
288    }
289
290}