Source code

001/*
002 * $Id: WordResidueRing.java 5868 2018-07-20 15:44:13Z kredel $
003 */
004
005package edu.jas.application;
006
007
008import java.io.Reader;
009import java.util.ArrayList;
010import java.util.List;
011import java.util.Random;
012import java.util.SortedSet;
013import java.util.TreeSet;
014
015import org.apache.logging.log4j.Logger;
016import org.apache.logging.log4j.LogManager; 
017
018import edu.jas.gb.WordGroebnerBaseAbstract;
019import edu.jas.gb.WordGroebnerBaseSeq;
020import edu.jas.poly.GenWordPolynomial;
021import edu.jas.poly.GenWordPolynomialRing;
022import edu.jas.structure.GcdRingElem;
023import edu.jas.structure.QuotPairFactory;
024import edu.jas.structure.RingFactory;
025import edu.jas.structure.ValueFactory;
026
027
028/**
029 * WordResidue ring factory based on GenWordPolynomialRing with GcdRingFactory
030 * interface. Objects of this class are immutable.
031 * @author Heinz Kredel
032 */
033public class WordResidueRing<C extends GcdRingElem<C>> implements RingFactory<WordResidue<C>>,
034                QuotPairFactory<GenWordPolynomial<C>, WordResidue<C>>,
035                ValueFactory<GenWordPolynomial<C>, WordResidue<C>> {
036
037
038    private static final Logger logger = LogManager.getLogger(WordResidueRing.class);
039
040
041    //private static final boolean debug = logger.isDebugEnabled();
042
043
044    /**
045     * Groebner base engine.
046     */
047    protected final WordGroebnerBaseAbstract<C> bb;
048
049
050    /**
051     * Word polynomial ideal for the reduction.
052     */
053    public final WordIdeal<C> ideal;
054
055
056    /**
057     * Polynomial ring of the factory. Shortcut to ideal.list.ring.
058     */
059    public final GenWordPolynomialRing<C> ring;
060
061
062    /**
063     * Indicator if this ring is a field.
064     */
065    protected int isField = -1; // initially unknown
066
067
068    /**
069     * The constructor creates a WordResidueRing object from an Ideal.
070     * @param i polynomial ideal.
071     */
072    public WordResidueRing(WordIdeal<C> i) {
073        this(i, false);
074    }
075
076
077    /**
078     * The constructor creates a WordResidueRing object from an WordIdeal.
079     * @param i solvable polynomial ideal.
080     * @param isMaximal true, if ideal is maxmal.
081     */
082    public WordResidueRing(WordIdeal<C> i, boolean isMaximal) {
083        ideal = i.GB(); // cheap if isGB
084        ring = ideal.getRing();
085        bb = new WordGroebnerBaseSeq<C>();
086        if (isMaximal) {
087            isField = 1;
088            return;
089        }
090        if (ideal.isONE()) {
091            logger.warn("ideal is one, so all residues are 0");
092        }
093        //System.out.println("rr ring   = " + ring.getClass().getName());
094        //System.out.println("rr cofac  = " + ring.coFac.getClass().getName());
095    }
096
097
098    /**
099     * Factory for base elements.
100     */
101    public GenWordPolynomialRing<C> pairFactory() {
102        return ring;
103    }
104
105
106    /**
107     * Factory for base elements.
108     */
109    public GenWordPolynomialRing<C> valueFactory() {
110        return ring;
111    }
112
113
114    /**
115     * Create from numerator.
116     */
117    public WordResidue<C> create(GenWordPolynomial<C> n) {
118        return new WordResidue<C>(this, n);
119    }
120
121
122    /**
123     * Create from numerator, denominator pair.
124     */
125    public WordResidue<C> create(GenWordPolynomial<C> n, GenWordPolynomial<C> d) {
126        if (d != null && !d.isONE()) {
127            throw new UnsupportedOperationException("d must be 1, but d = " + d);
128        }
129        return new WordResidue<C>(this, n);
130    }
131
132
133    /**
134     * Is this structure finite or infinite.
135     * @return true if this structure is finite, else false.
136     * @see edu.jas.structure.ElemFactory#isFinite()
137     */
138    public boolean isFinite() {
139        return ideal.commonZeroTest() <= 0 && ring.coFac.isFinite();
140    }
141
142
143    /**
144     * Copy WordResidue element c.
145     * @param c
146     * @return a copy of c.
147     */
148    public WordResidue<C> copy(WordResidue<C> c) {
149        //System.out.println("rr copy in    = " + c.val);
150        if (c == null) { // where does this happen?
151            return getZERO(); // or null?
152        }
153        WordResidue<C> r = new WordResidue<C>(this, c.val);
154        //System.out.println("rr copy out   = " + r.val);
155        //System.out.println("rr copy ideal = " + ideal.list.list);
156        return r; //new WordResidue<C>( c.ring, c.val );
157    }
158
159
160    /**
161     * Get the zero element.
162     * @return 0 as WordResidue.
163     */
164    public WordResidue<C> getZERO() {
165        return new WordResidue<C>(this, ring.getZERO());
166    }
167
168
169    /**
170     * Get the one element.
171     * @return 1 as WordResidue.
172     */
173    public WordResidue<C> getONE() {
174        WordResidue<C> one = new WordResidue<C>(this, ring.getONE());
175        if (one.isZERO()) {
176            logger.warn("ideal is one, so all residues are 0");
177        }
178        return one;
179    }
180
181
182    /**
183     * Get a list of the generating elements.
184     * @return list of generators for the algebraic structure.
185     * @see edu.jas.structure.ElemFactory#generators()
186     */
187    public List<WordResidue<C>> generators() {
188        List<GenWordPolynomial<C>> pgens = ring.generators();
189        List<WordResidue<C>> gens = new ArrayList<WordResidue<C>>(pgens.size());
190        SortedSet<WordResidue<C>> sgens = new TreeSet<WordResidue<C>>();
191        List<GenWordPolynomial<C>> rgens = new ArrayList<GenWordPolynomial<C>>(pgens.size());
192        WordIdeal<C> gi = new WordIdeal<C>(ring, rgens);
193        WordResidueRing<C> gr = new WordResidueRing<C>(gi);
194        for (GenWordPolynomial<C> s : pgens) {
195            WordResidue<C> r = new WordResidue<C>(this, s);
196            if (r.isZERO()) {
197                continue;
198            }
199            if (!r.isONE() && r.val.isConstant()) {
200                continue;
201            }
202            // avoid duplicate generators
203            WordResidue<C> x = new WordResidue<C>(gr, r.val);
204            if (x.isZERO()) {
205                continue;
206            }
207            if (!x.isONE() && x.val.isConstant()) {
208                continue;
209            }
210            r = new WordResidue<C>(this, x.val);
211            if (r.isZERO()) {
212                continue;
213            }
214            r = r.monic();
215            if (!r.isONE() && !r.val.isConstant()) {
216                rgens.add(r.val);
217                //System.out.println("rgens = " + rgens);
218                gi = new WordIdeal<C>(ring, rgens);
219                gr = new WordResidueRing<C>(gi);
220            }
221            //gens.add(r);
222            sgens.add(r);
223        }
224        gens.addAll(sgens);
225        return gens;
226    }
227
228
229    /**
230     * Query if this ring is commutative.
231     * @return true if this ring is commutative, else false.
232     */
233    public boolean isCommutative() {
234        return ring.isCommutative(); // check also vector space structure
235    }
236
237
238    /**
239     * Query if this ring is associative.
240     * @return true if this ring is associative, else false.
241     */
242    public boolean isAssociative() {
243        return ring.isAssociative(); // sufficient ??
244    }
245
246
247    /**
248     * Query if this ring is a field.
249     * @return false.
250     */
251    public boolean isField() {
252        if (isField > 0) {
253            return true;
254        }
255        if (isField == 0) {
256            return false;
257        }
258        if (ideal.isMaximal()) {
259            isField = 1;
260            return true;
261        }
262        return false;
263    }
264
265
266    /**
267     * Characteristic of this ring.
268     * @return characteristic of this ring.
269     */
270    public java.math.BigInteger characteristic() {
271        return ring.characteristic();
272    }
273
274
275    /**
276     * Get a WordResidue element from a BigInteger value.
277     * @param a BigInteger.
278     * @return a WordResidue.
279     */
280    public WordResidue<C> fromInteger(java.math.BigInteger a) {
281        return new WordResidue<C>(this, ring.fromInteger(a));
282    }
283
284
285    /**
286     * Get a WordResidue element from a long value.
287     * @param a long.
288     * @return a WordResidue.
289     */
290    public WordResidue<C> fromInteger(long a) {
291        return new WordResidue<C>(this, ring.fromInteger(a));
292    }
293
294
295    /**
296     * Get the String representation as RingFactory.
297     * @see java.lang.Object#toString()
298     */
299    @Override
300    public String toString() {
301        return "WordResidueRing[ " + ideal.toString() + " ]";
302    }
303
304
305    /**
306     * Get a scripting compatible string representation.
307     * @return script compatible representation for this ElemFactory.
308     * @see edu.jas.structure.ElemFactory#toScript()
309     */
310    @Override
311    public String toScript() {
312        // Python case
313        return "WRC(" + ideal.toScript() + ")";
314        //return "WRC(" + ideal.toScript() + "," + ring.toScript()  + ")";
315    }
316
317
318    /**
319     * Comparison with any other object.
320     * @see java.lang.Object#equals(java.lang.Object)
321     */
322    @Override
323    @SuppressWarnings("unchecked")
324    public boolean equals(Object b) {
325        if (!(b instanceof WordResidueRing)) {
326            return false;
327        }
328        WordResidueRing<C> a = null;
329        try {
330            a = (WordResidueRing<C>) b;
331        } catch (ClassCastException e) {
332        }
333        if (a == null) {
334            return false;
335        }
336        if (!ring.equals(a.ring)) {
337            return false;
338        }
339        return ideal.equals(a.ideal);
340    }
341
342
343    /**
344     * Hash code for this residue ring.
345     * @see java.lang.Object#hashCode()
346     */
347    @Override
348    public int hashCode() {
349        int h;
350        h = ideal.hashCode();
351        return h;
352    }
353
354
355    /**
356     * WordResidue random.
357     * @param n such that 0 &le; v &le; (2<sup>n</sup>-1).
358     * @return a random residue element.
359     */
360    public WordResidue<C> random(int n) {
361        GenWordPolynomial<C> x = ring.random(n).monic();
362        return new WordResidue<C>(this, x);
363    }
364
365
366    /**
367     * Generate a random residum polynomial.
368     * @param k bitsize of random coefficients.
369     * @param l number of terms.
370     * @param d maximal degree in each variable.
371     * @return a random residue polynomial.
372     */
373    public WordResidue<C> random(int k, int l, int d) {
374        GenWordPolynomial<C> x = ring.random(k, l, d).monic();
375        return new WordResidue<C>(this, x);
376    }
377
378
379    /**
380     * WordResidue random.
381     * @param n such that 0 &le; v &le; (2<sup>n</sup>-1).
382     * @param rnd is a source for random bits.
383     * @return a random residue element.
384     */
385    public WordResidue<C> random(int n, Random rnd) {
386        GenWordPolynomial<C> x = ring.random(n, rnd).monic();
387        return new WordResidue<C>(this, x);
388    }
389
390
391    /**
392     * Parse WordResidue from String.
393     * @param s String.
394     * @return WordResidue from s.
395     */
396    public WordResidue<C> parse(String s) {
397        GenWordPolynomial<C> x = ring.parse(s);
398        return new WordResidue<C>(this, x);
399    }
400
401
402    /**
403     * Parse WordResidue from Reader.
404     * @param r Reader.
405     * @return next WordResidue from r.
406     */
407    public WordResidue<C> parse(Reader r) {
408        GenWordPolynomial<C> x = ring.parse(r);
409        return new WordResidue<C>(this, x);
410    }
411
412}