Source code

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