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 * 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 % (long)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.longValue()); 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}