Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.application;
006
007
008import java.util.ArrayList;
009import java.util.List;
010
011import edu.jas.kern.PrettyPrint;
012import edu.jas.poly.ExpVector;
013import edu.jas.poly.GenPolynomial;
014import edu.jas.poly.GenSolvablePolynomial;
015import edu.jas.structure.GcdRingElem;
016import edu.jas.structure.NotInvertibleException;
017import edu.jas.structure.QuotPair;
018import edu.jas.structure.QuotPairFactory;
019import edu.jas.structure.Value;
020import edu.jas.structure.ValueFactory;
021
022
023/**
024 * SolvableResidue ring element based on GenSolvablePolynomial with GcdRingElem
025 * interface. Objects of this class are immutable.
026 * @author Heinz Kredel
027 */
028public class SolvableResidue<C extends GcdRingElem<C>> 
029    implements GcdRingElem<SolvableResidue<C>>, QuotPair<GenPolynomial<C>>, Value<GenPolynomial<C>> {
030
031
032    /**
033     * SolvableResidue class factory data structure.
034     */
035    public final SolvableResidueRing<C> ring;
036
037
038    /**
039     * Value part of the element data structure.
040     */
041    public final GenSolvablePolynomial<C> val;
042
043
044    /**
045     * Flag to remember if this residue element is a unit. -1 is unknown, 1 is
046     * unit, 0 not a unit.
047     */
048    protected int isunit = -1; // initially unknown
049
050
051    /**
052     * The constructor creates a SolvableResidue object from a ring factory.
053     * @param r solvable residue ring factory.
054     */
055    public SolvableResidue(SolvableResidueRing<C> r) {
056        this(r, r.ring.getZERO(), 0);
057    }
058
059
060    /**
061     * The constructor creates a SolvableResidue object from a ring factory and
062     * a polynomial.
063     * @param r solvable residue ring factory.
064     * @param a solvable polynomial.
065     */
066    public SolvableResidue(SolvableResidueRing<C> r, GenSolvablePolynomial<C> a) {
067        this(r, a, -1);
068    }
069
070
071    /**
072     * The constructor creates a SolvableResidue object from a ring factory, a
073     * polynomial and an indicator if a is a unit.
074     * @param r solvable residue ring factory.
075     * @param a solvable polynomial.
076     * @param u isunit indicator, -1, 0, 1.
077     */
078    public SolvableResidue(SolvableResidueRing<C> r, GenSolvablePolynomial<C> a, int u) {
079        ring = r;
080        val = ring.ideal.normalform(a); //.monic() no go
081        if (u == 0 || u == 1) {
082            isunit = u;
083            return;
084        }
085        if (val.isZERO()) {
086            isunit = 0;
087            return;
088        }
089        if (ring.isField()) {
090            isunit = 1;
091            return;
092        }
093        if (val.isUnit()) {
094            isunit = 1;
095            //} else { // not possible
096            //isunit = 0;
097        }
098        isunit = -1;
099    }
100
101
102    /**
103     * Get the corresponding element factory.
104     * @return factory for this Element.
105     * @see edu.jas.structure.Element#factory()
106     */
107    public SolvableResidueRing<C> factory() {
108        return ring;
109    }
110
111
112    /**
113     * Value. Returns the value.
114     * @see edu.jas.structure.Value#value()
115     */
116    public GenSolvablePolynomial<C> value() {
117        return val;
118    }
119
120
121    /**
122     * Numerator. Returns the value.
123     * @see edu.jas.structure.QuotPair#numerator()
124     */
125    public GenSolvablePolynomial<C> numerator() {
126        return val;
127    }
128
129
130    /**
131     * Denominator. Returns 1.
132     * @see edu.jas.structure.QuotPair#denominator()
133     */
134    public GenSolvablePolynomial<C> denominator() {
135        return ring.ring.getONE();
136    }
137
138
139    /**
140     * Clone this.
141     * @see java.lang.Object#clone()
142     */
143    @Override
144    public SolvableResidue<C> copy() {
145        return new SolvableResidue<C>(ring, val, isunit);
146    }
147
148
149    /**
150     * Is SolvableResidue zero.
151     * @return If this is 0 then true is returned, else false.
152     * @see edu.jas.structure.RingElem#isZERO()
153     */
154    public boolean isZERO() {
155        return val.isZERO();
156    }
157
158
159    /**
160     * Is SolvableResidue one.
161     * @return If this is 1 then true is returned, else false.
162     * @see edu.jas.structure.RingElem#isONE()
163     */
164    public boolean isONE() {
165        return val.isONE();
166    }
167
168
169    /**
170     * Is SolvableResidue unit.
171     * @return If this is a unit then true is returned, else false.
172     * @see edu.jas.structure.RingElem#isUnit()
173     */
174    public boolean isUnit() {
175        if (isunit > 0) {
176            return true;
177        }
178        if (isunit == 0) {
179            return false;
180        }
181        // not jet known
182        boolean u = ring.ideal.isUnit(val);
183        if (u) {
184            isunit = 1; // seems to be wrong for solvable polynomial rings
185        } else {
186            isunit = 0;
187        }
188        return isunit > 0;
189    }
190
191
192    /**
193     * Is SolvableResidue a constant.
194     * @return true if this.val is a constant polynomial, else false.
195     */
196    public boolean isConstant() {
197        return val.isConstant();
198    }
199
200
201    /**
202     * Get the String representation as RingElem.
203     * @see java.lang.Object#toString()
204     */
205    @Override
206    public String toString() {
207        if (PrettyPrint.isTrue()) {
208            return val.toString(ring.ring.getVars());
209        }
210        return "SolvableResidue[ " + val.toString() + " mod " + ring.toString() + " ]";
211    }
212
213
214    /**
215     * Get a scripting compatible string representation.
216     * @return script compatible representation for this Element.
217     * @see edu.jas.structure.Element#toScript()
218     */
219    @Override
220    public String toScript() {
221        // Python case
222        return val.toScript();
223        //         return "PolySolvableResidue( " + val.toScript() 
224        //                         + ", " + ring.toScript() + " )";
225    }
226
227
228    /**
229     * Get a scripting compatible string representation of the factory.
230     * @return script compatible representation for this ElemFactory.
231     * @see edu.jas.structure.Element#toScriptFactory()
232     */
233    @Override
234    public String toScriptFactory() {
235        // Python case
236        return factory().toScript();
237    }
238
239
240    /**
241     * SolvableResidue comparison.
242     * @param b SolvableResidue.
243     * @return sign(this-b), 0 means that this and b are equivalent in this
244     *         residue class ring.
245     */
246    @Override
247    public int compareTo(SolvableResidue<C> b) {
248        GenSolvablePolynomial<C> v = b.val;
249        if (!ring.equals(b.ring)) {
250            v = ring.ideal.normalform(v);
251        }
252        return val.compareTo(v);
253    }
254
255
256    /**
257     * Comparison with any other object.
258     * @see java.lang.Object#equals(java.lang.Object)
259     * @return true means that this and b are equivalent in this residue class
260     *         ring.
261     */
262    @Override
263    @SuppressWarnings("unchecked")
264    public boolean equals(Object b) {
265        if (!(b instanceof SolvableResidue)) {
266            return false;
267        }
268        SolvableResidue<C> a = null;
269        try {
270            a = (SolvableResidue<C>) b;
271        } catch (ClassCastException e) {
272        }
273        if (a == null) {
274            return false;
275        }
276        return compareTo(a) == 0;
277    }
278
279
280    /**
281     * Hash code for this residue.
282     * @see java.lang.Object#hashCode()
283     */
284    @Override
285    public int hashCode() {
286        int h;
287        h = ring.hashCode();
288        h = 37 * h + val.hashCode();
289        return h;
290    }
291
292
293    /**
294     * SolvableResidue absolute value.
295     * @return the absolute value of this.
296     * @see edu.jas.structure.RingElem#abs()
297     */
298    public SolvableResidue<C> abs() {
299        return new SolvableResidue<C>(ring, (GenSolvablePolynomial<C>) val.abs(), isunit);
300    }
301
302
303    /**
304     * SolvableResidue summation.
305     * @param S SolvableResidue.
306     * @return this+S.
307     */
308    public SolvableResidue<C> sum(SolvableResidue<C> S) {
309        return new SolvableResidue<C>(ring, (GenSolvablePolynomial<C>) val.sum(S.val));
310    }
311
312
313    /**
314     * SolvableResidue negate.
315     * @return -this.
316     * @see edu.jas.structure.RingElem#negate()
317     */
318    public SolvableResidue<C> negate() {
319        return new SolvableResidue<C>(ring, (GenSolvablePolynomial<C>) val.negate(), isunit);
320    }
321
322
323    /**
324     * SolvableResidue signum.
325     * @see edu.jas.structure.RingElem#signum()
326     * @return signum(this).
327     */
328    public int signum() {
329        return val.signum();
330    }
331
332
333    /**
334     * SolvableResidue subtraction.
335     * @param S SolvableResidue.
336     * @return this-S.
337     */
338    public SolvableResidue<C> subtract(SolvableResidue<C> S) {
339        return new SolvableResidue<C>(ring, (GenSolvablePolynomial<C>) val.subtract(S.val));
340    }
341
342
343    /**
344     * SolvableResidue division.
345     * @param S SolvableResidue.
346     * @return this/S.
347     */
348    public SolvableResidue<C> divide(SolvableResidue<C> S) {
349        if (ring.isField()) {
350            return multiply(S.inverse());
351        }
352        try {
353            return multiply(S.inverse());
354        } catch (NotInvertibleException ignored) {
355            System.out.println("catch: " + ignored);
356            //ignored.printStackTrace();
357            // ignored
358        }
359        List<GenSolvablePolynomial<C>> Q = new ArrayList<GenSolvablePolynomial<C>>(1);
360        Q.add(ring.ring.getZERO());
361        List<GenSolvablePolynomial<C>> V = new ArrayList<GenSolvablePolynomial<C>>(1);
362        V.add(S.val);
363        GenSolvablePolynomial<C> x = ring.bb.sred.leftNormalform(Q, V, val);
364        GenSolvablePolynomial<C> y = Q.get(0);
365        System.out.println("SolvableResidue val = " + val + ", div = " + S.val + ", quotient = " + y
366                        + ", remainder = " + x);
367        return new SolvableResidue<C>(ring, y);
368    }
369
370
371    /**
372     * SolvableResidue inverse.
373     * @see edu.jas.structure.RingElem#inverse()
374     * @return S with S = 1/this if defined.
375     */
376    public SolvableResidue<C> inverse() {
377        GenSolvablePolynomial<C> x = ring.ideal.inverse(val);
378        SolvableResidue<C> xp = new SolvableResidue<C>(ring, x, 1);
379        if (xp.isZERO()) {
380            throw new NotInvertibleException("(" + x + ") * (" + val + ") = " + x.multiply(val) + " = 0 mod "
381                            + ring.ideal);
382        }
383        if (!xp.multiply(this).isONE()) {
384            throw new NotInvertibleException("(" + x + ") * (" + val + ") = " + x.multiply(val)
385                            + " != 1 mod " + ring.ideal);
386        }
387        return xp;
388    }
389
390
391    /**
392     * SolvableResidue remainder.
393     * @param S SolvableResidue.
394     * @return this - (this/S)*S.
395     */
396    public SolvableResidue<C> remainder(SolvableResidue<C> S) {
397        List<GenSolvablePolynomial<C>> V = new ArrayList<GenSolvablePolynomial<C>>(1);
398        V.add(S.val);
399        GenSolvablePolynomial<C> x = ring.bb.sred.leftNormalform(V, val);
400        return new SolvableResidue<C>(ring, x);
401    }
402
403
404    /**
405     * SolvableResidue multiplication.
406     * @param S SolvableResidue.
407     * @return this*S.
408     */
409    public SolvableResidue<C> multiply(SolvableResidue<C> S) {
410        GenSolvablePolynomial<C> x = val.multiply(S.val);
411        int i = -1;
412        if (isunit == 1 && S.isunit == 1) {
413            i = 1;
414        } else if (isunit == 0 || S.isunit == 0) {
415            i = 0;
416        }
417        return new SolvableResidue<C>(ring, x, i);
418    }
419
420
421    /**
422     * SolvableResidue multiplication.
423     * @param S GenSolvablePolynomial.
424     * @return this*S.
425     */
426    public SolvableResidue<C> multiply(GenSolvablePolynomial<C> S) {
427        GenSolvablePolynomial<C> x = val.multiply(S);
428        int i = -1;
429        if (isunit == 1 && S.isUnit()) {
430            i = 1;
431        } else if (isunit == 0 || !S.isUnit()) {
432            i = 0;
433        }
434        return new SolvableResidue<C>(ring, x, i);
435    }
436
437
438    /*
439     * SolvableResidue multiplication.
440     * @param s coefficient.
441     * @return this*s.
442     */
443    public SolvableResidue<C> multiply(C s) {
444        GenSolvablePolynomial<C> x = val.multiply(s);
445        int i = -1;
446        if (isunit == 1 && s.isUnit()) {
447            i = 1;
448        } else if (isunit == 0 || !s.isUnit()) {
449            i = 0;
450        }
451        return new SolvableResidue<C>(ring, x, i);
452    }
453
454
455    /**
456     * SolvableResidue multiplication.
457     * @param e exponent.
458     * @return this*X<sup>e</sup>.
459     */
460    public SolvableResidue<C> multiply(ExpVector e) {
461        GenSolvablePolynomial<C> x = val.multiply(e);
462        int i = -1;
463        if (isunit == 1 && e.isZERO()) {
464            i = 1;
465        } else if (isunit == 0 || !e.isZERO()) {
466            i = 0;
467        }
468        return new SolvableResidue<C>(ring, x, i);
469    }
470
471
472    /**
473     * SolvableResidue monic.
474     * @return this with monic value part.
475     */
476    public SolvableResidue<C> monic() {
477        return new SolvableResidue<C>(ring, val.monic(), isunit);
478    }
479
480
481    /**
482     * Greatest common divisor.
483     * @param b other element.
484     * @return gcd(this,b).
485     */
486    public SolvableResidue<C> gcd(SolvableResidue<C> b) {
487        throw new UnsupportedOperationException("gcd not implemented");
488        // GenSolvablePolynomial<C> x = ring.engine.gcd(val, b.val);
489        // int i = -1; // gcd might become a unit
490        // if (x.isONE()) {
491        //     i = 1;
492        // } else {
493        //     System.out.println("SolvableResidue gcd = " + x);
494        // }
495        // if (isunit == 1 && b.isunit == 1) {
496        //     i = 1;
497        // }
498        // return new SolvableResidue<C>(ring, x, i);
499    }
500
501
502    /**
503     * Extended greatest common divisor. <b>Note: </b>Not implemented, throws
504     * UnsupportedOperationException.
505     * @param b other element.
506     * @return [ gcd(this,b), c1, c2 ] with c1*this + c2*b = gcd(this,b).
507     */
508    public SolvableResidue<C>[] egcd(SolvableResidue<C> b) {
509        throw new UnsupportedOperationException("egcd not implemented");
510    }
511}