Source code

001/*
002 * $Id: QuotientRing.java 4067 2012-07-27 16:17:35Z kredel $
003 */
004
005package edu.jas.ufd;
006
007
008import java.io.Reader;
009import java.util.ArrayList;
010import java.util.List;
011import java.util.Random;
012
013import org.apache.log4j.Logger;
014
015import edu.jas.kern.StringUtil;
016import edu.jas.poly.GenPolynomial;
017import edu.jas.poly.GenPolynomialRing;
018import edu.jas.poly.PolyUtil;
019import edu.jas.structure.GcdRingElem;
020import edu.jas.structure.RingFactory;
021
022
023/**
024 * Quotient ring factory based on GenPolynomial with RingElem interface. Objects
025 * of this class are immutable.
026 * @author Heinz Kredel
027 */
028public class QuotientRing<C extends GcdRingElem<C>> implements RingFactory<Quotient<C>> {
029
030
031    private static final Logger logger = Logger.getLogger(QuotientRing.class);
032
033
034    //private boolean debug = logger.isDebugEnabled();
035
036
037    /**
038     * Polynomial ring of the factory.
039     */
040    public final GenPolynomialRing<C> ring;
041
042
043    /**
044     * GCD engine of the factory.
045     */
046    public final GreatestCommonDivisor<C> engine;
047
048
049    /**
050     * Use GCD of package edu.jas.ufd.
051     */
052    public final boolean ufdGCD;
053
054
055    /**
056     * The constructor creates a QuotientRing object from a GenPolynomialRing.
057     * @param r polynomial ring.
058     */
059    public QuotientRing(GenPolynomialRing<C> r) {
060        this(r, true);
061    }
062
063
064    /**
065     * The constructor creates a QuotientRing object from a GenPolynomialRing.
066     * @param r polynomial ring.
067     * @param ufdGCD flag, if syzygy or gcd based algorithm used for engine.
068     */
069    public QuotientRing(GenPolynomialRing<C> r, boolean ufdGCD) {
070        ring = r;
071        this.ufdGCD = ufdGCD;
072        //         if (!ufdGCD) {
073        //             engine = null;
074        //             return;
075        //         }
076        engine = GCDFactory.<C> getProxy(ring.coFac);
077        logger.debug("quotient ring constructed");
078    }
079
080
081    /**
082     * Divide.
083     * @param n first polynomial.
084     * @param d second polynomial.
085     * @return divide(n,d)
086     */
087    protected GenPolynomial<C> divide(GenPolynomial<C> n, GenPolynomial<C> d) {
088        return PolyUtil.<C> basePseudoDivide(n, d);
089    }
090
091
092    /**
093     * Greatest common divisor.
094     * @param n first polynomial.
095     * @param d second polynomial.
096     * @return gcd(n,d)
097     */
098    protected GenPolynomial<C> gcd(GenPolynomial<C> n, GenPolynomial<C> d) {
099        if (ufdGCD) {
100            return engine.gcd(n, d);
101        }
102        return engine.gcd(n, d);
103        //return syzGcd(n, d);
104    }
105
106
107    /*
108     * Least common multiple. Just for fun, is not efficient.
109     * @param n first polynomial.
110     * @param d second polynomial.
111     * @return lcm(n,d)
112     */
113    //     protected GenPolynomial<C> syzLcm(GenPolynomial<C> n, GenPolynomial<C> d) {
114    //         List<GenPolynomial<C>> list = new ArrayList<GenPolynomial<C>>(1);
115    //         list.add(n);
116    //         Ideal<C> N = new Ideal<C>(n.ring, list, true);
117    //         list = new ArrayList<GenPolynomial<C>>(1);
118    //         list.add(d);
119    //         Ideal<C> D = new Ideal<C>(n.ring, list, true);
120    //         Ideal<C> L = N.intersect(D);
121    //         if (L.getList().size() != 1) {
122    //             throw new RuntimeException("lcm not uniqe");
123    //         }
124    //         GenPolynomial<C> lcm = L.getList().get(0);
125    //         return lcm;
126    //     }
127
128
129    /*
130     * Greatest common divisor. Just for fun, is not efficient.
131     * @param n first polynomial.
132     * @param d second polynomial.
133     * @return gcd(n,d)
134     */
135    //     protected GenPolynomial<C> syzGcd(GenPolynomial<C> n, GenPolynomial<C> d) {
136    //         if (n.isZERO()) {
137    //             return d;
138    //         }
139    //         if (d.isZERO()) {
140    //             return n;
141    //         }
142    //         if (n.isONE()) {
143    //             return n;
144    //         }
145    //         if (d.isONE()) {
146    //             return d;
147    //         }
148    //         GenPolynomial<C> p = n.multiply(d);
149    //         GenPolynomial<C> lcm = syzLcm(n, d);
150    //         GenPolynomial<C> gcd = divide(p, lcm);
151    //         return gcd;
152    //     }
153
154
155    /**
156     * Is this structure finite or infinite.
157     * @return true if this structure is finite, else false.
158     * @see edu.jas.structure.ElemFactory#isFinite()
159     */
160    public boolean isFinite() {
161        return false;
162    }
163
164
165    /**
166     * Copy Quotient element c.
167     * @param c
168     * @return a copy of c.
169     */
170    public Quotient<C> copy(Quotient<C> c) {
171        return new Quotient<C>(c.ring, c.num, c.den, true);
172    }
173
174
175    /**
176     * Get the zero element.
177     * @return 0 as Quotient.
178     */
179    public Quotient<C> getZERO() {
180        return new Quotient<C>(this, ring.getZERO());
181    }
182
183
184    /**
185     * Get the one element.
186     * @return 1 as Quotient.
187     */
188    public Quotient<C> getONE() {
189        return new Quotient<C>(this, ring.getONE());
190    }
191
192
193    /**
194     * Get a list of the generating elements.
195     * @return list of generators for the algebraic structure.
196     * @see edu.jas.structure.ElemFactory#generators()
197     */
198    public List<Quotient<C>> generators() {
199        List<GenPolynomial<C>> pgens = ring.generators();
200        List<Quotient<C>> gens = new ArrayList<Quotient<C>>(pgens.size());
201        for (GenPolynomial<C> p : pgens) {
202            Quotient<C> q = new Quotient<C>(this, p);
203            gens.add(q);
204        }
205        return gens;
206    }
207
208
209    /**
210     * Query if this ring is commutative.
211     * @return true if this ring is commutative, else false.
212     */
213    public boolean isCommutative() {
214        return ring.isCommutative();
215    }
216
217
218    /**
219     * Query if this ring is associative.
220     * @return true if this ring is associative, else false.
221     */
222    public boolean isAssociative() {
223        return ring.isAssociative();
224    }
225
226
227    /**
228     * Query if this ring is a field.
229     * @return true.
230     */
231    public boolean isField() {
232        return true;
233    }
234
235
236    /**
237     * Characteristic of this ring.
238     * @return characteristic of this ring.
239     */
240    public java.math.BigInteger characteristic() {
241        return ring.characteristic();
242    }
243
244
245    /**
246     * Get a Quotient element from a BigInteger value.
247     * @param a BigInteger.
248     * @return a Quotient.
249     */
250    public Quotient<C> fromInteger(java.math.BigInteger a) {
251        return new Quotient<C>(this, ring.fromInteger(a));
252    }
253
254
255    /**
256     * Get a Quotient element from a long value.
257     * @param a long.
258     * @return a Quotient.
259     */
260    public Quotient<C> fromInteger(long a) {
261        return new Quotient<C>(this, ring.fromInteger(a));
262    }
263
264
265    /**
266     * Get the String representation as RingFactory.
267     * @see java.lang.Object#toString()
268     */
269    @Override
270    public String toString() {
271        String s = null;
272        if (ring.coFac.characteristic().signum() == 0) {
273            s = "RatFunc";
274        } else {
275            s = "ModFunc";
276        }
277        return s + "( " + ring.toString() + " )";
278    }
279
280
281    /**
282     * Get a scripting compatible string representation.
283     * @return script compatible representation for this ElemFactory.
284     * @see edu.jas.structure.ElemFactory#toScript()
285     */
286    //JAVA6only: @Override
287    public String toScript() {
288        // Python case
289        return "RF(" + ring.toScript() + ")";
290    }
291
292
293    /**
294     * Comparison with any other object.
295     * @see java.lang.Object#equals(java.lang.Object)
296     */
297    @Override
298    @SuppressWarnings("unchecked")
299    // not jet working
300    public boolean equals(Object b) {
301        if (!(b instanceof QuotientRing)) {
302            return false;
303        }
304        QuotientRing<C> a = null;
305        try {
306            a = (QuotientRing<C>) b;
307        } catch (ClassCastException e) {
308        }
309        if (a == null) {
310            return false;
311        }
312        return ring.equals(a.ring);
313    }
314
315
316    /**
317     * Hash code for this quotient ring.
318     * @see java.lang.Object#hashCode()
319     */
320    @Override
321    public int hashCode() {
322        int h;
323        h = ring.hashCode();
324        return h;
325    }
326
327
328    /**
329     * Quotient random.
330     * @param n such that 0 &le; v &le; (2<sup>n</sup>-1).
331     * @return a random residue element.
332     */
333    public Quotient<C> random(int n) {
334        GenPolynomial<C> r = ring.random(n).monic();
335        GenPolynomial<C> s = ring.random(n).monic();
336        while (s.isZERO()) {
337            s = ring.random(n).monic();
338        }
339        return new Quotient<C>(this, r, s, false);
340    }
341
342
343    /**
344     * Generate a random residum polynomial.
345     * @param k bitsize of random coefficients.
346     * @param l number of terms.
347     * @param d maximal degree in each variable.
348     * @param q density of nozero exponents.
349     * @return a random residue polynomial.
350     */
351    public Quotient<C> random(int k, int l, int d, float q) {
352        GenPolynomial<C> r = ring.random(k, l, d, q).monic();
353        GenPolynomial<C> s = ring.random(k, l, d, q).monic();
354        while (s.isZERO()) {
355            s = ring.random(k, l, d, q).monic();
356        }
357        return new Quotient<C>(this, r, s, false);
358    }
359
360
361    /**
362     * Quotient random.
363     * @param n such that 0 &le; v &le; (2<sup>n</sup>-1).
364     * @param rnd is a source for random bits.
365     * @return a random residue element.
366     */
367    public Quotient<C> random(int n, Random rnd) {
368        GenPolynomial<C> r = ring.random(n, rnd).monic();
369        GenPolynomial<C> s = ring.random(n, rnd).monic();
370        while (s.isZERO()) {
371            s = ring.random(n, rnd).monic();
372        }
373        return new Quotient<C>(this, r, s, false);
374    }
375
376
377    /**
378     * Parse Quotient from String. Syntax: "{ polynomial | polynomial }" or
379     * "{ polynomial }" or " polynomial | polynomial " or " polynomial "
380     * @param s String.
381     * @return Quotient from s.
382     */
383    public Quotient<C> parse(String s) {
384        int i = s.indexOf("{");
385        if (i >= 0) {
386            s = s.substring(i + 1);
387        }
388        i = s.lastIndexOf("}");
389        if (i >= 0) {
390            s = s.substring(0, i);
391        }
392        i = s.indexOf("|");
393        if (i < 0) {
394            GenPolynomial<C> n = ring.parse(s);
395            return new Quotient<C>(this, n);
396        }
397        String s1 = s.substring(0, i);
398        String s2 = s.substring(i + 1);
399        GenPolynomial<C> n = ring.parse(s1);
400        GenPolynomial<C> d = ring.parse(s2);
401        return new Quotient<C>(this, n, d);
402    }
403
404
405    /**
406     * Parse Quotient from Reader.
407     * @param r Reader.
408     * @return next Quotient from r.
409     */
410    public Quotient<C> parse(Reader r) {
411        String s = StringUtil.nextPairedString(r, '{', '}');
412        return parse(s);
413    }
414
415
416    /**
417     * Degree of extension field.
418     * @return degree of this extension field, -1 for transcendental extension.
419     */
420    public long extensionDegree() {
421        long degree = -1L;
422        if (ring.nvar <= 0) {
423            degree = 0L;
424        }
425        return degree;
426    }
427
428}