Source code

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