Source code

001/*
002 * $Id$
003 */
004
005package edu.jas.arith;
006
007
008import edu.jas.structure.GcdRingElem;
009import edu.jas.structure.NotInvertibleException;
010
011
012/**
013 * ModLong class with RingElem interface. Objects of this class are immutable.
014 * @author Heinz Kredel
015 * @see ModInteger
016 */
017
018public final class ModLong implements GcdRingElem<ModLong>, Modular {
019
020
021    /**
022     * ModLongRing reference.
023     */
024    public final ModLongRing ring;
025
026
027    /**
028     * Value part of the element data structure.
029     */
030    public final long val;
031
032
033    /**
034     * The constructor creates a ModLong object from a ModLongRing and a value
035     * part.
036     * @param m ModLongRing.
037     * @param a math.BigInteger.
038     */
039    public ModLong(ModLongRing m, java.math.BigInteger a) {
040        this(m, a.mod(m.getModul()).longValue());
041    }
042
043
044    /**
045     * The constructor creates a ModLong object from a ModLongRing and a long
046     * value part.
047     * @param m ModLongRing.
048     * @param a long.
049     */
050    public ModLong(ModLongRing m, long a) {
051        ring = m;
052        long v = a % ring.modul;
053        val = (v >= 0L ? v : v + ring.modul);
054    }
055
056
057    /**
058     * The constructor creates a ModLong object from a ModLongRing and a Long
059     * value part.
060     * @param m ModLongRing.
061     * @param a Long.
062     */
063    public ModLong(ModLongRing m, Long a) {
064        this(m, a.longValue());
065    }
066
067
068    /**
069     * The constructor creates a ModLong object from a ModLongRing and a String
070     * value part.
071     * @param m ModLongRing.
072     * @param s String.
073     */
074    public ModLong(ModLongRing m, String s) {
075        this(m, Long.valueOf(s.trim()));
076    }
077
078
079    /**
080     * The constructor creates a 0 ModLong object from a given ModLongRing.
081     * @param m ModLongRing.
082     */
083    public ModLong(ModLongRing m) {
084        this(m, 0L);
085    }
086
087
088    /**
089     * Get the value part.
090     * @return val.
091     */
092    public long getVal() {
093        return val;
094    }
095
096
097    /**
098     * Get the module part.
099     * @return modul.
100     */
101    public long getModul() {
102        return ring.modul;
103    }
104
105
106    /**
107     * Get the corresponding element factory.
108     * @return factory for this Element.
109     * @see edu.jas.structure.Element#factory()
110     */
111    public ModLongRing factory() {
112        return ring;
113    }
114
115
116    /**
117     * Get the symmetric value part.
118     * @return val with -modul/2 &le; val &lt; modul/2.
119     */
120    public long getSymmetricVal() {
121        if ((val + val) > ring.modul) {
122            // val > m/2 as 2*val > m, make symmetric to 0
123            return val - ring.modul;
124        }
125        return val;
126    }
127
128
129    /**
130     * Return a BigInteger from this Element.
131     * @return a BigInteger of this.
132     */
133    public BigInteger getInteger() {
134        return new BigInteger(val);
135    }
136
137
138    /**
139     * Return a symmetric BigInteger from this Element.
140     * @return a symmetric BigInteger of this.
141     */
142    public BigInteger getSymmetricInteger() {
143        long v = val;
144        if ((val + val) > ring.modul) {
145            // val > m/2 as 2*val > m, make symmetric to 0
146            v = val - ring.modul;
147        }
148        return new BigInteger(v);
149    }
150
151
152    /**
153     * Clone this.
154     * @see java.lang.Object#clone()
155     */
156    @Override
157    public ModLong copy() {
158        return new ModLong(ring, val);
159    }
160
161
162    /**
163     * Is ModLong number zero.
164     * @return If this is 0 then true is returned, else false.
165     * @see edu.jas.structure.RingElem#isZERO()
166     */
167    public boolean isZERO() {
168        return val == 0L;
169    }
170
171
172    /**
173     * Is ModLong number one.
174     * @return If this is 1 then true is returned, else false.
175     * @see edu.jas.structure.RingElem#isONE()
176     */
177    public boolean isONE() {
178        return val == 1L;
179    }
180
181
182    /**
183     * Is ModLong number a unit.
184     * @return If this is a unit then true is returned, else false.
185     * @see edu.jas.structure.RingElem#isUnit()
186     */
187    public boolean isUnit() {
188        if (isZERO()) {
189            return false;
190        }
191        if (ring.isField()) {
192            return true;
193        }
194        long g = gcd(ring.modul, val);
195        return (g == 1L || g == -1L);
196    }
197
198
199    /**
200     * Get the String representation.
201     * @see java.lang.Object#toString()
202     */
203    @Override
204    public String toString() {
205        return Long.toString(val);
206    }
207
208
209    /**
210     * Get a scripting compatible string representation.
211     * @return script compatible representation for this Element.
212     * @see edu.jas.structure.Element#toScript()
213     */
214    @Override
215    public String toScript() {
216        // Python case
217        return toString();
218    }
219
220
221    /**
222     * Get a scripting compatible string representation of the factory.
223     * @return script compatible representation for this ElemFactory.
224     * @see edu.jas.structure.Element#toScriptFactory()
225     */
226    @Override
227    public String toScriptFactory() {
228        // Python case
229        return factory().toScript();
230    }
231
232
233    /**
234     * ModLong comparison.
235     * @param b ModLong.
236     * @return sign(this-b).
237     */
238    @Override
239    public int compareTo(ModLong b) {
240        long v = b.val;
241        if (ring != b.ring) {
242            v = v % ring.modul;
243        }
244        if (val > v) {
245            return 1;
246        }
247        return (val < v ? -1 : 0);
248    }
249
250
251    /**
252     * Comparison with any other object.
253     * @see java.lang.Object#equals(java.lang.Object)
254     */
255    @Override
256    public boolean equals(Object b) {
257        if (!(b instanceof ModLong)) {
258            return false;
259        }
260        return (0 == compareTo((ModLong) b));
261    }
262
263
264    /**
265     * Hash code for this ModLong.
266     * @see java.lang.Object#hashCode()
267     */
268    @Override
269    public int hashCode() {
270        return (int) val;
271    }
272
273
274    /**
275     * ModLong absolute value.
276     * @return the absolute value of this.
277     * @see edu.jas.structure.RingElem#abs()
278     */
279    public ModLong abs() {
280        return new ModLong(ring, (val < 0 ? -val : val));
281    }
282
283
284    /**
285     * ModLong negative.
286     * @see edu.jas.structure.RingElem#negate()
287     * @return -this.
288     */
289    public ModLong negate() {
290        return new ModLong(ring, -val);
291    }
292
293
294    /**
295     * ModLong signum.
296     * @see edu.jas.structure.RingElem#signum()
297     * @return signum(this).
298     */
299    public int signum() {
300        if (val > 0L) {
301            return 1;
302        }
303        return (val < 0L ? -1 : 0);
304    }
305
306
307    /**
308     * ModLong subtraction.
309     * @param S ModLong.
310     * @return this-S.
311     */
312    public ModLong subtract(ModLong S) {
313        return new ModLong(ring, val - S.val);
314    }
315
316
317    /**
318     * ModLong divide.
319     * @param S ModLong.
320     * @return this/S.
321     */
322    public ModLong divide(ModLong S) {
323        try {
324            return multiply(S.inverse());
325        } catch (NotInvertibleException e) {
326            try {
327                if ((val % S.val) == 0L) {
328                    return new ModLong(ring, val / S.val);
329                }
330                throw new NotInvertibleException(e.getCause());
331            } catch (ArithmeticException a) {
332                throw new NotInvertibleException(a.getCause());
333            }
334        }
335    }
336
337
338    /**
339     * ModLong inverse.
340     * @see edu.jas.structure.RingElem#inverse()
341     * @throws NotInvertibleException if the element is not invertible.
342     * @return S with S=1/this if defined.
343     */
344    public ModLong inverse() /*throws NotInvertibleException*/ {
345        try {
346            return new ModLong(ring, modInverse(val, ring.modul));
347        } catch (ArithmeticException e) {
348            long g = gcd(val, ring.modul);
349            long f = ring.modul / g;
350            throw new ModularNotInvertibleException(e, new BigInteger(ring.modul), new BigInteger(g),
351                            new BigInteger(f));
352        }
353    }
354
355
356    /**
357     * ModLong remainder.
358     * @param S ModLong.
359     * @return remainder(this,S).
360     */
361    public ModLong remainder(ModLong S) {
362        if (S == null || S.isZERO()) {
363            throw new ArithmeticException("division by zero");
364        }
365        if (S.isONE()) {
366            return ring.getZERO();
367        }
368        if (S.isUnit()) {
369            return ring.getZERO();
370        }
371        return new ModLong(ring, val % S.val);
372    }
373
374
375    /**
376     * ModLong multiply.
377     * @param S ModLong.
378     * @return this*S.
379     */
380    public ModLong multiply(ModLong S) {
381        return new ModLong(ring, val * S.val);
382    }
383
384
385    /**
386     * ModLong summation.
387     * @param S ModLong.
388     * @return this+S.
389     */
390    public ModLong sum(ModLong S) {
391        return new ModLong(ring, val + S.val);
392    }
393
394
395    /**
396     * ModInteger greatest common divisor.
397     * @param S ModInteger.
398     * @return [ gcd(this,S), a, b ] with a*this + b*S = gcd(this,S).
399     */
400    public ModLong gcd(ModLong S) {
401        if (S.isZERO()) {
402            return this;
403        }
404        if (isZERO()) {
405            return S;
406        }
407        if (isUnit() || S.isUnit()) {
408            return ring.getONE();
409        }
410        return new ModLong(ring, gcd(val, S.val));
411    }
412
413
414    /**
415     * ModInteger extended greatest common divisor.
416     * @param S ModInteger.
417     * @return [ gcd(this,S), a, b ] with a*this + b*S = gcd(this,S).
418     */
419    public ModLong[] egcd(ModLong S) {
420        ModLong[] ret = new ModLong[3];
421        ret[0] = null;
422        ret[1] = null;
423        ret[2] = null;
424        if (S == null || S.isZERO()) {
425            ret[0] = this;
426            return ret;
427        }
428        if (isZERO()) {
429            ret[0] = S;
430            return ret;
431        }
432        if (isUnit() || S.isUnit()) {
433            ret[0] = ring.getONE();
434            if (isUnit() && S.isUnit()) {
435                //ModLong half = (new ModLong(ring, 2L)).inverse();
436                //ret[1] = this.inverse().multiply(half);
437                //ret[2] = S.inverse().multiply(half);
438                // (1-1*this)/S
439                ret[1] = ring.getONE();
440                ModLong x = ret[0].subtract(ret[1].multiply(this));
441                ret[2] = x.divide(S);
442                return ret;
443            }
444            if (isUnit()) {
445                // oder inverse(S-1)?
446                ret[1] = this.inverse();
447                ret[2] = ring.getZERO();
448                return ret;
449            }
450            // if ( s.isUnit() ) {
451            // oder inverse(this-1)?
452            ret[1] = ring.getZERO();
453            ret[2] = S.inverse();
454            return ret;
455            //}
456        }
457        //System.out.println("this = " + this + ", S = " + S);
458        long q = this.val;
459        long r = S.val;
460        long c1 = 1L; // BigInteger.ONE.val;
461        long d1 = 0L; // BigInteger.ZERO.val;
462        long c2 = 0L; // BigInteger.ZERO.val;
463        long d2 = 1L; // BigInteger.ONE.val;
464        long x1;
465        long x2;
466        while (r != 0L) {
467            //qr = q.divideAndRemainder(r);
468            long a = q / r;
469            long b = q % r;
470            q = a;
471            x1 = c1 - q * d1;
472            x2 = c2 - q * d2;
473            c1 = d1;
474            c2 = d2;
475            d1 = x1;
476            d2 = x2;
477            q = r;
478            r = b;
479        }
480        //System.out.println("q = " + q + "\n c1 = " + c1 + "\n c2 = " + c2);
481        ret[0] = new ModLong(ring, q);
482        ret[1] = new ModLong(ring, c1);
483        ret[2] = new ModLong(ring, c2);
484        return ret;
485    }
486
487
488    /**
489     * Long greatest common divisor.
490     * @param T long.
491     * @param S long.
492     * @return gcd(T,S).
493     */
494    public long gcd(long T, long S) {
495        if (S == 0L) {
496            return T;
497        }
498        if (T == 0L) {
499            return S;
500        }
501        long a = T;
502        long b = S;
503        while (b != 0L) {
504            long r = a % b;
505            a = b;
506            b = r;
507        }
508        return a;
509    }
510
511
512    /**
513     * Long half extended greatest common divisor.
514     * @param T long.
515     * @param S long.
516     * @return [ gcd(T,S), a ] with a*T + b*S = gcd(T,S).
517     */
518    public long[] hegcd(long T, long S) {
519        long[] ret = new long[2];
520        if (S == 0L) {
521            ret[0] = T;
522            ret[1] = 1L;
523            return ret;
524        }
525        if (T == 0L) {
526            ret[0] = S;
527            ret[1] = 0L;
528            return ret;
529        }
530        //System.out.println("hegcd, T = " + T + ", S = " + S);
531        long a = T;
532        long b = S;
533        long a1 = 1L;
534        long b1 = 0L;
535        while (b != 0L) {
536            long q = a / b;
537            long r = a % b;
538            a = b;
539            b = r;
540            long r1 = a1 - q * b1;
541            a1 = b1;
542            b1 = r1;
543        }
544        if (a1 < 0L) {
545            a1 += S;
546        }
547        ret[0] = a;
548        ret[1] = a1;
549        return ret;
550    }
551
552
553    /**
554     * Long modular inverse.
555     * @param T long.
556     * @param m long.
557     * @return a with with a*T = 1 mod m.
558     */
559    public long modInverse(long T, long m) {
560        if (T == 0L) {
561            throw new NotInvertibleException("zero is not invertible");
562        }
563        long[] hegcd = hegcd(T, m);
564        long a = hegcd[0];
565        if (!(a == 1L || a == -1L)) { // gcd != 1
566            throw new ModularNotInvertibleException("element not invertible, gcd != 1", new BigInteger(m),
567                            new BigInteger(a), new BigInteger(m / a));
568        }
569        long b = hegcd[1];
570        if (b == 0L) { // when m divides this, e.g. m.isUnit()
571            throw new NotInvertibleException("element not invertible, divisible by modul");
572        }
573        if (b < 0L) {
574            b += m;
575        }
576        return b;
577    }
578
579
580    /**
581     * Returns the number of bits in the representation of this ModLong,
582     * including a sign bit.
583     * @return number of bits in the representation of this ModLong, including a
584     *         sign bit.
585     */
586    public long bitLength() {
587        return BigInteger.bitLength(val);
588    }
589
590}