Source code

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