Source code

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