001 /*
002 * $Id: QuotientRing.java 3670 2011-06-25 19:04:28Z kredel $
003 */
004
005 package edu.jas.ufd;
006
007
008 import java.io.Reader;
009 import java.util.ArrayList;
010 import java.util.List;
011 import java.util.Random;
012
013 import org.apache.log4j.Logger;
014
015 import edu.jas.kern.StringUtil;
016 import edu.jas.poly.GenPolynomial;
017 import edu.jas.poly.GenPolynomialRing;
018 import edu.jas.poly.PolyUtil;
019 import edu.jas.structure.GcdRingElem;
020 import edu.jas.structure.RingFactory;
021
022
023 /**
024 * Quotient ring factory based on GenPolynomial with RingElem interface. Objects
025 * of this class are immutable.
026 * @author Heinz Kredel
027 */
028 public class QuotientRing<C extends GcdRingElem<C>> implements RingFactory<Quotient<C>> {
029
030
031 private static final Logger logger = Logger.getLogger(QuotientRing.class);
032
033
034 //private boolean debug = logger.isDebugEnabled();
035
036
037 /**
038 * Polynomial ring of the factory.
039 */
040 public final GenPolynomialRing<C> ring;
041
042
043 /**
044 * GCD engine of the factory.
045 */
046 public final GreatestCommonDivisor<C> engine;
047
048
049 /**
050 * Use GCD of package edu.jas.ufd.
051 */
052 public final boolean ufdGCD;
053
054
055 /**
056 * The constructor creates a QuotientRing object from a GenPolynomialRing.
057 * @param r polynomial ring.
058 */
059 public QuotientRing(GenPolynomialRing<C> r) {
060 this(r, true);
061 }
062
063
064 /**
065 * The constructor creates a QuotientRing object from a GenPolynomialRing.
066 * @param r polynomial ring.
067 * @param ufdGCD flag, if syzygy or gcd based algorithm used for engine.
068 */
069 public QuotientRing(GenPolynomialRing<C> r, boolean ufdGCD) {
070 ring = r;
071 this.ufdGCD = ufdGCD;
072 // if (!ufdGCD) {
073 // engine = null;
074 // return;
075 // }
076 engine = GCDFactory.<C> getProxy(ring.coFac);
077 }
078
079
080 /**
081 * Divide.
082 * @param n first polynomial.
083 * @param d second polynomial.
084 * @return divide(n,d)
085 */
086 protected GenPolynomial<C> divide(GenPolynomial<C> n, GenPolynomial<C> d) {
087 return PolyUtil.<C> basePseudoDivide(n, d);
088 }
089
090
091 /**
092 * Greatest common divisor.
093 * @param n first polynomial.
094 * @param d second polynomial.
095 * @return gcd(n,d)
096 */
097 protected GenPolynomial<C> gcd(GenPolynomial<C> n, GenPolynomial<C> d) {
098 if (ufdGCD) {
099 return engine.gcd(n, d);
100 }
101 return engine.gcd(n, d);
102 //return syzGcd(n, d);
103 }
104
105
106 /*
107 * Least common multiple. Just for fun, is not efficient.
108 * @param n first polynomial.
109 * @param d second polynomial.
110 * @return lcm(n,d)
111 */
112 // protected GenPolynomial<C> syzLcm(GenPolynomial<C> n, GenPolynomial<C> d) {
113 // List<GenPolynomial<C>> list = new ArrayList<GenPolynomial<C>>(1);
114 // list.add(n);
115 // Ideal<C> N = new Ideal<C>(n.ring, list, true);
116 // list = new ArrayList<GenPolynomial<C>>(1);
117 // list.add(d);
118 // Ideal<C> D = new Ideal<C>(n.ring, list, true);
119 // Ideal<C> L = N.intersect(D);
120 // if (L.getList().size() != 1) {
121 // throw new RuntimeException("lcm not uniqe");
122 // }
123 // GenPolynomial<C> lcm = L.getList().get(0);
124 // return lcm;
125 // }
126
127
128 /*
129 * Greatest common divisor. Just for fun, is not efficient.
130 * @param n first polynomial.
131 * @param d second polynomial.
132 * @return gcd(n,d)
133 */
134 // protected GenPolynomial<C> syzGcd(GenPolynomial<C> n, GenPolynomial<C> d) {
135 // if (n.isZERO()) {
136 // return d;
137 // }
138 // if (d.isZERO()) {
139 // return n;
140 // }
141 // if (n.isONE()) {
142 // return n;
143 // }
144 // if (d.isONE()) {
145 // return d;
146 // }
147 // GenPolynomial<C> p = n.multiply(d);
148 // GenPolynomial<C> lcm = syzLcm(n, d);
149 // GenPolynomial<C> gcd = divide(p, lcm);
150 // return gcd;
151 // }
152
153
154 /**
155 * Is this structure finite or infinite.
156 * @return true if this structure is finite, else false.
157 * @see edu.jas.structure.ElemFactory#isFinite()
158 */
159 public boolean isFinite() {
160 return false;
161 }
162
163
164 /**
165 * Copy Quotient element c.
166 * @param c
167 * @return a copy of c.
168 */
169 public Quotient<C> copy(Quotient<C> c) {
170 return new Quotient<C>(c.ring, c.num, c.den, true);
171 }
172
173
174 /**
175 * Get the zero element.
176 * @return 0 as Quotient.
177 */
178 public Quotient<C> getZERO() {
179 return new Quotient<C>(this, ring.getZERO());
180 }
181
182
183 /**
184 * Get the one element.
185 * @return 1 as Quotient.
186 */
187 public Quotient<C> getONE() {
188 return new Quotient<C>(this, ring.getONE());
189 }
190
191
192 /**
193 * Get a list of the generating elements.
194 * @return list of generators for the algebraic structure.
195 * @see edu.jas.structure.ElemFactory#generators()
196 */
197 public List<Quotient<C>> generators() {
198 List<GenPolynomial<C>> pgens = ring.generators();
199 List<Quotient<C>> gens = new ArrayList<Quotient<C>>(pgens.size());
200 for (GenPolynomial<C> p : pgens) {
201 Quotient<C> q = new Quotient<C>(this, p);
202 gens.add(q);
203 }
204 return gens;
205 }
206
207
208 /**
209 * Query if this ring is commutative.
210 * @return true if this ring is commutative, else false.
211 */
212 public boolean isCommutative() {
213 return ring.isCommutative();
214 }
215
216
217 /**
218 * Query if this ring is associative.
219 * @return true if this ring is associative, else false.
220 */
221 public boolean isAssociative() {
222 return ring.isAssociative();
223 }
224
225
226 /**
227 * Query if this ring is a field.
228 * @return true.
229 */
230 public boolean isField() {
231 return true;
232 }
233
234
235 /**
236 * Characteristic of this ring.
237 * @return characteristic of this ring.
238 */
239 public java.math.BigInteger characteristic() {
240 return ring.characteristic();
241 }
242
243
244 /**
245 * Get a Quotient element from a BigInteger value.
246 * @param a BigInteger.
247 * @return a Quotient.
248 */
249 public Quotient<C> fromInteger(java.math.BigInteger a) {
250 return new Quotient<C>(this, ring.fromInteger(a));
251 }
252
253
254 /**
255 * Get a Quotient element from a long value.
256 * @param a long.
257 * @return a Quotient.
258 */
259 public Quotient<C> fromInteger(long a) {
260 return new Quotient<C>(this, ring.fromInteger(a));
261 }
262
263
264 /**
265 * Get the String representation as RingFactory.
266 * @see java.lang.Object#toString()
267 */
268 @Override
269 public String toString() {
270 String s = null;
271 if ( ring.coFac.characteristic().signum() == 0 ) {
272 s = "RatFunc";
273 } else {
274 s = "ModFunc";
275 }
276 return s + "( " + ring.toString() + " )";
277 }
278
279
280 /**
281 * Get a scripting compatible string representation.
282 * @return script compatible representation for this ElemFactory.
283 * @see edu.jas.structure.ElemFactory#toScript()
284 */
285 //JAVA6only: @Override
286 public String toScript() {
287 // Python case
288 return "RF(" + ring.toScript() + ")";
289 }
290
291
292 /**
293 * Comparison with any other object.
294 * @see java.lang.Object#equals(java.lang.Object)
295 */
296 @Override
297 @SuppressWarnings("unchecked")
298 // not jet working
299 public boolean equals(Object b) {
300 if (!(b instanceof QuotientRing)) {
301 return false;
302 }
303 QuotientRing<C> a = null;
304 try {
305 a = (QuotientRing<C>) b;
306 } catch (ClassCastException e) {
307 }
308 if (a == null) {
309 return false;
310 }
311 return ring.equals(a.ring);
312 }
313
314
315 /**
316 * Hash code for this quotient ring.
317 * @see java.lang.Object#hashCode()
318 */
319 @Override
320 public int hashCode() {
321 int h;
322 h = ring.hashCode();
323 return h;
324 }
325
326
327 /**
328 * Quotient random.
329 * @param n such that 0 ≤ v ≤ (2<sup>n</sup>-1).
330 * @return a random residue element.
331 */
332 public Quotient<C> random(int n) {
333 GenPolynomial<C> r = ring.random(n).monic();
334 GenPolynomial<C> s = ring.random(n).monic();
335 while (s.isZERO()) {
336 s = ring.random(n).monic();
337 }
338 return new Quotient<C>(this, r, s, false);
339 }
340
341
342 /**
343 * Generate a random residum polynomial.
344 * @param k bitsize of random coefficients.
345 * @param l number of terms.
346 * @param d maximal degree in each variable.
347 * @param q density of nozero exponents.
348 * @return a random residue polynomial.
349 */
350 public Quotient<C> random(int k, int l, int d, float q) {
351 GenPolynomial<C> r = ring.random(k, l, d, q).monic();
352 GenPolynomial<C> s = ring.random(k, l, d, q).monic();
353 while (s.isZERO()) {
354 s = ring.random(k, l, d, q).monic();
355 }
356 return new Quotient<C>(this, r, s, false);
357 }
358
359
360 /**
361 * Quotient random.
362 * @param n such that 0 ≤ v ≤ (2<sup>n</sup>-1).
363 * @param rnd is a source for random bits.
364 * @return a random residue element.
365 */
366 public Quotient<C> random(int n, Random rnd) {
367 GenPolynomial<C> r = ring.random(n, rnd).monic();
368 GenPolynomial<C> s = ring.random(n, rnd).monic();
369 while (s.isZERO()) {
370 s = ring.random(n, rnd).monic();
371 }
372 return new Quotient<C>(this, r, s, false);
373 }
374
375
376 /**
377 * Parse Quotient from String. Syntax: "{ polynomial | polynomial }" or
378 * "{ polynomial }" or " polynomial | polynomial " or " polynomial "
379 * @param s String.
380 * @return Quotient from s.
381 */
382 public Quotient<C> parse(String s) {
383 int i = s.indexOf("{");
384 if (i >= 0) {
385 s = s.substring(i + 1);
386 }
387 i = s.lastIndexOf("}");
388 if (i >= 0) {
389 s = s.substring(0, i);
390 }
391 i = s.indexOf("|");
392 if (i < 0) {
393 GenPolynomial<C> n = ring.parse(s);
394 return new Quotient<C>(this, n);
395 }
396 String s1 = s.substring(0, i);
397 String s2 = s.substring(i + 1);
398 GenPolynomial<C> n = ring.parse(s1);
399 GenPolynomial<C> d = ring.parse(s2);
400 return new Quotient<C>(this, n, d);
401 }
402
403
404 /**
405 * Parse Quotient from Reader.
406 * @param r Reader.
407 * @return next Quotient from r.
408 */
409 public Quotient<C> parse(Reader r) {
410 String s = StringUtil.nextPairedString(r, '{', '}');
411 return parse(s);
412 }
413
414
415 /**
416 * Degree of extension field.
417 * @return degree of this extension field, -1 for transcendental extension.
418 */
419 public long extensionDegree() {
420 long degree = -1L;
421 if (ring.nvar <= 0) {
422 degree = 0L;
423 }
424 return degree;
425 }
426
427 }