Source code

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