Source code

001/*
002 * $Id: SquarefreeFiniteFieldCharP.java 4125 2012-08-19 19:05:22Z 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.log4j.Logger;
013
014import edu.jas.arith.BigInteger;
015import edu.jas.poly.ExpVector;
016import edu.jas.poly.GenPolynomial;
017import edu.jas.poly.GenPolynomialRing;
018import edu.jas.poly.Monomial;
019import edu.jas.structure.GcdRingElem;
020import edu.jas.structure.Power;
021import edu.jas.structure.RingFactory;
022
023
024/**
025 * Squarefree decomposition for finite coefficient fields of characteristic p.
026 * @author Heinz Kredel
027 */
028
029public class SquarefreeFiniteFieldCharP<C extends GcdRingElem<C>> extends SquarefreeFieldCharP<C> {
030
031
032    private static final Logger logger = Logger.getLogger(SquarefreeFiniteFieldCharP.class);
033
034
035    //private final boolean debug = logger.isDebugEnabled();
036
037
038    /**
039     * Constructor.
040     */
041    public SquarefreeFiniteFieldCharP(RingFactory<C> fac) {
042        super(fac);
043        // isFinite() predicate now present
044        if (!fac.isFinite()) {
045            throw new IllegalArgumentException("fac must be finite");
046        }
047    }
048
049
050    /* --------- char-th roots --------------------- */
051
052    /**
053     * Characteristics root of a coefficient. <b>Note:</b> not needed at the
054     * moment.
055     * @param p coefficient.
056     * @return [p -&gt; k] if exists k with e=k*charactristic(c) and c = p**e,
057     *         else null.
058     */
059    public SortedMap<C, Long> rootCharacteristic(C p) {
060        if (p == null) {
061            throw new IllegalArgumentException(this.getClass().getName() + " p == null");
062        }
063        // already checked in constructor:
064        //java.math.BigInteger c = p.factory().characteristic();
065        //if ( c.signum() == 0 ) {
066        //    return null;
067        //}
068        SortedMap<C, Long> root = new TreeMap<C, Long>();
069        if (p.isZERO()) {
070            return root;
071        }
072        // true for finite fields:
073        root.put(p, 1L);
074        return root;
075    }
076
077
078    /**
079     * Characteristics root of a coefficient.
080     * @param c coefficient.
081     * @return r with r**p == c, if such an r exists, else null.
082     */
083    public C coeffRootCharacteristic(C c) {
084        if (c == null || c.isZERO()) {
085            return c;
086        }
087        C r = c;
088        if (aCoFac == null && qCoFac == null) {
089            // case ModInteger: c**p == c
090            return r;
091        }
092        if (aCoFac != null) {
093            // case AlgebraicNumber<ModInteger>: r = c**(p**(d-1)), r**p == c
094            long d = aCoFac.totalExtensionDegree();
095            //System.out.println("d = " + d);
096            if (d <= 1) {
097                return r;
098            }
099            BigInteger p = new BigInteger(aCoFac.characteristic());
100            BigInteger q = Power.<BigInteger> positivePower(p, d - 1);
101            //System.out.println("p**(d-1) = " + q);
102            r = Power.<C> positivePower(r, q.getVal());
103            //System.out.println("r**q = " + r);
104            return r;
105        }
106        if (qCoFac != null) {
107            throw new UnsupportedOperationException("case QuotientRing not yet implemented");
108        }
109        return r;
110    }
111
112
113    /**
114     * Characteristics root of a polynomial. <b>Note:</b> call only in
115     * recursion.
116     * @param P polynomial.
117     * @return [p -&gt; k] if exists k with e=k*charactristic(P) and P = p**e,
118     *         else null.
119     */
120    public SortedMap<GenPolynomial<C>, Long> rootCharacteristic(GenPolynomial<C> P) {
121        if (P == null) {
122            throw new IllegalArgumentException(this.getClass().getName() + " P == null");
123        }
124        java.math.BigInteger c = P.ring.characteristic();
125        if (c.signum() == 0) {
126            return null;
127        }
128        SortedMap<GenPolynomial<C>, Long> root = new TreeMap<GenPolynomial<C>, Long>();
129        if (P.isZERO()) {
130            return root;
131        }
132        if (P.isONE()) {
133            root.put(P, 1L);
134            return root;
135        }
136        SortedMap<GenPolynomial<C>, Long> sf = squarefreeFactors(P);
137        if (logger.isInfoEnabled()) {
138            logger.info("sf = " + sf);
139        }
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.longValue();
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 = 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 = 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().longValue();
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().longValue();
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            if (logger.isInfoEnabled()) {
271                logger.info("sm,rec = " + sm);
272            }
273            GenPolynomial<C> r = rf.getONE();
274            for (Map.Entry<GenPolynomial<C>, Long> me : sm.entrySet()) {
275                GenPolynomial<C> rp = me.getKey();
276                long gl = me.getValue(); //sm.get(rp);
277                if (gl > 1) {
278                    rp = Power.<GenPolynomial<C>> positivePower(rp, gl);
279                }
280                r = r.multiply(rp);
281            }
282            ExpVector e = ExpVector.create(1, 0, fl);
283            //System.out.println("put-root r = " + r + ", e = " + e);
284            d.doPutToMap(e, r);
285        }
286        return d;
287    }
288
289}