Source code

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