001 /*
002 * $Id: ResidueRing.java 3211 2010-07-05 12:54:22Z kredel $
003 */
004
005 package edu.jas.application;
006
007 import java.util.Random;
008 import java.util.List;
009 import java.util.ArrayList;
010 import java.io.Reader;
011
012 import org.apache.log4j.Logger;
013
014 import edu.jas.structure.GcdRingElem;
015 import edu.jas.structure.RingFactory;
016
017 import edu.jas.poly.GenPolynomial;
018 import edu.jas.poly.GenPolynomialRing;
019
020 import edu.jas.ufd.GreatestCommonDivisor;
021 import 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 */
029 public 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 ≤ v ≤ (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 ≤ v ≤ (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 }