Source code

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