Source code

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