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