001/* 002 * $Id: ModInteger.java 4148 2012-08-31 19:49:27Z 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.equals(java.math.BigInteger.ZERO); 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 //JAVA6only: @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 //JAVA6only: @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 //JAVA6only: @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 * ModInteger multiply. 463 * @param S ModInteger. 464 * @return this*S. 465 */ 466 public ModInteger multiply(ModInteger S) { 467 return new ModInteger(ring, val.multiply(S.val)); 468 } 469 470 471 /** 472 * ModInteger product. 473 * @param A ModInteger. 474 * @param B ModInteger. 475 * @return A*B. 476 */ 477 public static ModInteger MIPROD(ModInteger A, ModInteger B) { 478 if (A == null) 479 return null; 480 return A.multiply(B); 481 } 482 483 484 /** 485 * ModInteger summation. 486 * @param S ModInteger. 487 * @return this+S. 488 */ 489 public ModInteger sum(ModInteger S) { 490 return new ModInteger(ring, val.add(S.val)); 491 } 492 493 494 /** 495 * ModInteger summation. 496 * @param A ModInteger. 497 * @param B ModInteger. 498 * @return A+B. 499 */ 500 public static ModInteger MISUM(ModInteger A, ModInteger B) { 501 if (A == null) 502 return null; 503 return A.sum(B); 504 } 505 506 507 /** 508 * ModInteger greatest common divisor. 509 * @param S ModInteger. 510 * @return gcd(this,S). 511 */ 512 public ModInteger gcd(ModInteger S) { 513 if (S.isZERO()) { 514 return this; 515 } 516 if (isZERO()) { 517 return S; 518 } 519 if (isUnit() || S.isUnit()) { 520 return ring.getONE(); 521 } 522 return new ModInteger(ring, val.gcd(S.val)); 523 } 524 525 526 /** 527 * ModInteger half extended greatest common divisor. 528 * @param S ModInteger. 529 * @return [ gcd(this,S), a ] with a*this + b*S = gcd(this,S) for some b. 530 */ 531 public ModInteger[] hegcd(ModInteger S) { 532 ModInteger[] ret = new ModInteger[2]; 533 ret[0] = null; 534 ret[1] = null; 535 if (S == null || S.isZERO()) { 536 ret[0] = this; 537 ret[1] = this.ring.getONE(); 538 return ret; 539 } 540 if (isZERO()) { 541 ret[0] = S; 542 return ret; 543 } 544 //System.out.println("this = " + this + ", S = " + S); 545 java.math.BigInteger[] qr; 546 java.math.BigInteger q = this.val; 547 java.math.BigInteger r = S.val; 548 java.math.BigInteger c1 = BigInteger.ONE.val; 549 java.math.BigInteger d1 = BigInteger.ZERO.val; 550 java.math.BigInteger x1; 551 while (!r.equals(java.math.BigInteger.ZERO)) { 552 qr = q.divideAndRemainder(r); 553 q = qr[0]; 554 x1 = c1.subtract(q.multiply(d1)); 555 c1 = d1; 556 d1 = x1; 557 q = r; 558 r = qr[1]; 559 } 560 //System.out.println("q = " + q + "\n c1 = " + c1 + "\n c2 = " + c2); 561 ret[0] = new ModInteger(ring, q); 562 ret[1] = new ModInteger(ring, c1); 563 //assert ( ((c1.multiply(this)).remainder(S).equals(q) )); 564 return ret; 565 } 566 567 568 /** 569 * ModInteger extended greatest common divisor. 570 * @param S ModInteger. 571 * @return [ gcd(this,S), a, b ] with a*this + b*S = gcd(this,S). 572 */ 573 public ModInteger[] egcd(ModInteger S) { 574 ModInteger[] ret = new ModInteger[3]; 575 ret[0] = null; 576 ret[1] = null; 577 ret[2] = null; 578 if (S == null || S.isZERO()) { 579 ret[0] = this; 580 return ret; 581 } 582 if (isZERO()) { 583 ret[0] = S; 584 return ret; 585 } 586 if (this.isUnit() || S.isUnit()) { 587 ret[0] = ring.getONE(); 588 if (this.isUnit() && S.isUnit()) { 589 //ModInteger half = ring.fromInteger(2).inverse(); 590 //ret[1] = this.inverse().multiply(half); 591 //ret[2] = S.inverse().multiply(half); 592 //System.out.println("gcd = " + (ret[1].multiply(this).sum(ret[2].multiply(S)))); 593 // (1-1*this)/S 594 ret[1] = ring.getONE(); 595 ModInteger x = ret[0].subtract(ret[1].multiply(this)); 596 ret[2] = x.divide(S); 597 //System.out.println("gcd, a, b = " + (ret[1]) + ", " + ret[2]); 598 //System.out.println("gcd = " + (ret[1].multiply(this).sum(ret[2].multiply(S)))); 599 return ret; 600 } 601 if (this.isUnit()) { 602 // oder inverse(S-1)? 603 ret[1] = this.inverse(); 604 ret[2] = ring.getZERO(); 605 return ret; 606 } 607 // if ( S.isUnit() ) { 608 // oder inverse(this-1)? 609 ret[1] = ring.getZERO(); 610 ret[2] = S.inverse(); 611 return ret; 612 //} 613 } 614 //System.out.println("this = " + this + ", S = " + S); 615 java.math.BigInteger[] qr; 616 java.math.BigInteger q = this.val; 617 java.math.BigInteger r = S.val; 618 java.math.BigInteger c1 = BigInteger.ONE.val; 619 java.math.BigInteger d1 = BigInteger.ZERO.val; 620 java.math.BigInteger c2 = BigInteger.ZERO.val; 621 java.math.BigInteger d2 = BigInteger.ONE.val; 622 java.math.BigInteger x1; 623 java.math.BigInteger x2; 624 while (!r.equals(java.math.BigInteger.ZERO)) { 625 qr = q.divideAndRemainder(r); 626 q = qr[0]; 627 x1 = c1.subtract(q.multiply(d1)); 628 x2 = c2.subtract(q.multiply(d2)); 629 c1 = d1; 630 c2 = d2; 631 d1 = x1; 632 d2 = x2; 633 q = r; 634 r = qr[1]; 635 } 636 //System.out.println("q = " + q + "\n c1 = " + c1 + "\n c2 = " + c2); 637 ret[0] = new ModInteger(ring, q); 638 ret[1] = new ModInteger(ring, c1); 639 ret[2] = new ModInteger(ring, c2); 640 return ret; 641 } 642 643}