Source code

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