Source code

001/*
002 * $Id: Residue.java 5934 2018-09-30 11:23:44Z kredel $
003 */
004
005package edu.jas.poly;
006
007
008import org.apache.logging.log4j.Logger;
009import org.apache.logging.log4j.LogManager; 
010
011import edu.jas.structure.GcdRingElem;
012import edu.jas.structure.NotInvertibleException;
013import edu.jas.structure.RingElem;
014
015
016/**
017 * Residue element based on RingElem residue. Objects of this class are (nearly)
018 * immutable.
019 * @author Heinz Kredel
020 */
021public class Residue<C extends RingElem<C>> implements RingElem<Residue<C>> {
022
023
024    private static final Logger logger = LogManager.getLogger(Residue.class);
025
026
027    private static final boolean debug = logger.isDebugEnabled();
028
029
030    /**
031     * Residue class factory data structure.
032     */
033    protected final ResidueRing<C> ring;
034
035
036    /**
037     * Value part of the element data structure.
038     */
039    protected final C val;
040
041
042    /**
043     * Flag to remember if this residue element is a unit. -1 is unknown, 1 is
044     * unit, 0 not a unit.
045     */
046    protected int isunit = -1; // initially unknown
047
048
049    /**
050     * The constructor creates a Residue object from a ring factory.
051     * @param r ring factory.
052     */
053    public Residue(ResidueRing<C> r) {
054        this(r, r.ring.getZERO(), 0);
055    }
056
057
058    /**
059     * The constructor creates a Residue object from a ring factory and a ring
060     * element.
061     * @param r ring factory.
062     * @param a ring element.
063     */
064    public Residue(ResidueRing<C> r, C a) {
065        this(r, a, -1);
066    }
067
068
069    /**
070     * The constructor creates a Residue object from a ring factory, a ring
071     * element and an indicator if a is a unit.
072     * @param r ring factory.
073     * @param a ring element.
074     * @param u isunit indicator, -1, 0, 1.
075     */
076    public Residue(ResidueRing<C> r, C a, int u) {
077        ring = r;
078        C v = a.remainder(ring.modul);
079        if (v.signum() < 0) {
080            v = v.sum(ring.modul);
081        }
082        val = v;
083        if (u == 0 || u == 1) {
084            isunit = u;
085            return;
086        }
087        if (val.isZERO()) {
088            isunit = 0;
089            return;
090        }
091        if (val.isUnit()) {
092            isunit = 1;
093            //} else { // not possible
094            //isunit = 0;
095        }
096        isunit = -1;
097    }
098
099
100    /**
101     * Get the corresponding element factory.
102     * @return factory for this Element.
103     * @see edu.jas.structure.Element#factory()
104     */
105    public ResidueRing<C> factory() {
106        return ring;
107    }
108
109
110    /**
111     * Copy this.
112     * @see edu.jas.structure.Element#copy()
113     */
114    @Override
115    public Residue<C> copy() {
116        return new Residue<C>(ring, val);
117    }
118
119
120    /**
121     * Is Residue zero.
122     * @return If this is 0 then true is returned, else false.
123     * @see edu.jas.structure.RingElem#isZERO()
124     */
125    public boolean isZERO() {
126        return val.equals(ring.ring.getZERO());
127    }
128
129
130    /**
131     * Is Residue one.
132     * @return If this is 1 then true is returned, else false.
133     * @see edu.jas.structure.RingElem#isONE()
134     */
135    public boolean isONE() {
136        return val.equals(ring.ring.getONE());
137    }
138
139
140    /**
141     * Is Residue unit.
142     * @return If this is a unit then true is returned, else false.
143     * @see edu.jas.structure.RingElem#isUnit()
144     */
145    @SuppressWarnings("unchecked")
146    public boolean isUnit() {
147        if (isunit == 1) {
148            return true;
149        }
150        if (isunit == 0) {
151            return false;
152        }
153        // val.isUnit() already tested
154        // not jet known
155        if (val instanceof GcdRingElem && ring.modul instanceof GcdRingElem) {
156            GcdRingElem v = (GcdRingElem) val;
157            GcdRingElem m = (GcdRingElem) ring.modul;
158            C gcd = (C) v.gcd(m);
159            if (debug) {
160                logger.info("gcd = " + gcd);
161            }
162            boolean u = gcd.isONE();
163            if (u) {
164                isunit = 1;
165            } else {
166                isunit = 0;
167            }
168            return u;
169        }
170        // still unknown
171        return false;
172    }
173
174
175    /**
176     * Get the String representation as RingElem.
177     * @see java.lang.Object#toString()
178     */
179    @Override
180    public String toString() {
181        return "Residue[ " + val.toString() + " mod " + ring.toString() + " ]";
182    }
183
184
185    /**
186     * Get a scripting compatible string representation.
187     * @return script compatible representation for this Element.
188     * @see edu.jas.structure.Element#toScript()
189     */
190    @Override
191    public String toScript() {
192        // Python case
193        return "Residue( " + val.toScript() + " , " + ring.toScript() + " )";
194    }
195
196
197    /**
198     * Get a scripting compatible string representation of the factory.
199     * @return script compatible representation for this ElemFactory.
200     * @see edu.jas.structure.Element#toScriptFactory()
201     */
202    @Override
203    public String toScriptFactory() {
204        // Python case
205        return factory().toScript();
206    }
207
208
209    /**
210     * Residue comparison.
211     * @param b Residue.
212     * @return sign(this-b), 0 means that this and b are equivalent in this
213     *         residue class ring.
214     */
215    @Override
216    public int compareTo(Residue<C> b) {
217        C v = b.val;
218        if (!ring.equals(b.ring)) {
219            v = v.remainder(ring.modul);
220        }
221        return val.compareTo(v);
222    }
223
224
225    /**
226     * Comparison with any other object.
227     * @see java.lang.Object#equals(java.lang.Object)
228     * @return true means that this and b are equivalent in this residue class
229     *         ring.
230     */
231    @Override
232    @SuppressWarnings("unchecked")
233    public boolean equals(Object b) {
234        if (b == null) {
235            return false;
236        }
237        if (!(b instanceof Residue)) {
238            return false;
239        }
240        Residue<C> a = (Residue<C>) b;
241        return (0 == compareTo(a));
242    }
243
244
245    /**
246     * Hash code for this local.
247     * @see java.lang.Object#hashCode()
248     */
249    @Override
250    public int hashCode() {
251        int h;
252        h = ring.hashCode();
253        h = 37 * h + val.hashCode();
254        return h;
255    }
256
257
258    /**
259     * Residue absolute value.
260     * @return the absolute value of this.
261     * @see edu.jas.structure.RingElem#abs()
262     */
263    public Residue<C> abs() {
264        return new Residue<C>(ring, val.abs());
265    }
266
267
268    /**
269     * Residue summation.
270     * @param S Residue.
271     * @return this+S.
272     */
273    public Residue<C> sum(Residue<C> S) {
274        return new Residue<C>(ring, val.sum(S.val));
275    }
276
277
278    /**
279     * Residue negate.
280     * @return -this.
281     * @see edu.jas.structure.RingElem#negate()
282     */
283    public Residue<C> negate() {
284        return new Residue<C>(ring, val.negate());
285    }
286
287
288    /**
289     * Residue signum.
290     * @see edu.jas.structure.RingElem#signum()
291     * @return signum(this).
292     */
293    public int signum() {
294        return val.signum();
295    }
296
297
298    /**
299     * Residue subtraction.
300     * @param S Residue.
301     * @return this-S.
302     */
303    public Residue<C> subtract(Residue<C> S) {
304        return new Residue<C>(ring, val.subtract(S.val));
305    }
306
307
308    /**
309     * Residue division.
310     * @param S Residue.
311     * @return this/S.
312     */
313    public Residue<C> divide(Residue<C> S) {
314        return multiply(S.inverse());
315    }
316
317
318    /**
319     * Residue inverse.
320     * @see edu.jas.structure.RingElem#inverse()
321     * @return S with S = 1/this if defined.
322     */
323    @SuppressWarnings("unchecked")
324    public Residue<C> inverse() {
325        if (isunit == 0) {
326            throw new NotInvertibleException("element not invertible (0) " + this);
327        }
328        if (val instanceof GcdRingElem && ring.modul instanceof GcdRingElem) {
329            GcdRingElem v = (GcdRingElem) val;
330            GcdRingElem m = (GcdRingElem) ring.modul;
331            C[] egcd = (C[]) v.egcd(m);
332            if (debug) {
333                logger.info("egcd = " + egcd[0] + ", f = " + egcd[1]);
334            }
335            if (!egcd[0].isONE()) {
336                isunit = 0;
337                throw new NotInvertibleException("element not invertible (gcd)" + this);
338            }
339            isunit = 1;
340            C x = egcd[1];
341            return new Residue<C>(ring, x);
342        }
343        if (val.isUnit()) {
344            C x = val.inverse();
345            return new Residue<C>(ring, x);
346        }
347        System.out.println("isunit = " + isunit + ", isUnit() = " + this.isUnit());
348        throw new NotInvertibleException("element not invertible (!gcd)" + this);
349    }
350
351
352    /**
353     * Residue remainder.
354     * @param S Residue.
355     * @return this - (this/S)*S.
356     */
357    public Residue<C> remainder(Residue<C> S) {
358        C x = val.remainder(S.val);
359        return new Residue<C>(ring, x);
360    }
361
362
363    /**
364     * Quotient and remainder by division of this by S.
365     * @param S a Residue
366     * @return [this/S, this - (this/S)*S].
367     */
368    @SuppressWarnings("unchecked")
369    public Residue<C>[] quotientRemainder(Residue<C> S) {
370        return new Residue[] { divide(S), remainder(S) };
371    }
372
373
374    /**
375     * Residue multiplication.
376     * @param S Residue.
377     * @return this*S.
378     */
379    public Residue<C> multiply(Residue<C> S) {
380        return new Residue<C>(ring, val.multiply(S.val));
381    }
382
383
384    /**
385     * Greatest common divisor. <b>Note: </b>Not implemented, throws
386     * UnsupportedOperationException.
387     * @param b other element.
388     * @return gcd(this,b).
389     */
390    public Residue<C> gcd(Residue<C> b) {
391        throw new UnsupportedOperationException("gcd not implemented " + this.getClass().getName());
392    }
393
394
395    /**
396     * Extended greatest common divisor. <b>Note: </b>Not implemented, throws
397     * UnsupportedOperationException.
398     * @param b other element.
399     * @return [ gcd(this,b), c1, c2 ] with c1*this + c2*b = gcd(this,b).
400     */
401    public Residue<C>[] egcd(Residue<C> b) {
402        throw new UnsupportedOperationException("egcd not implemented " + this.getClass().getName());
403    }
404
405}