Source code

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