Source code

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