001/* 002 * $Id: SolvableResidue.java 5156 2015-03-21 11:56:59Z kredel $ 003 */ 004 005package edu.jas.application; 006 007 008import java.util.ArrayList; 009import java.util.List; 010 011import edu.jas.kern.PrettyPrint; 012import edu.jas.poly.ExpVector; 013import edu.jas.poly.GenPolynomial; 014import edu.jas.poly.GenSolvablePolynomial; 015import edu.jas.structure.GcdRingElem; 016import edu.jas.structure.NotInvertibleException; 017import edu.jas.structure.QuotPair; 018import edu.jas.structure.QuotPairFactory; 019import edu.jas.structure.Value; 020import edu.jas.structure.ValueFactory; 021 022 023/** 024 * SolvableResidue ring element based on GenSolvablePolynomial with GcdRingElem 025 * interface. Objects of this class are immutable. 026 * @author Heinz Kredel 027 */ 028public class SolvableResidue<C extends GcdRingElem<C>> 029 implements GcdRingElem<SolvableResidue<C>>, QuotPair<GenPolynomial<C>>, Value<GenPolynomial<C>> { 030 031 032 /** 033 * SolvableResidue class factory data structure. 034 */ 035 public final SolvableResidueRing<C> ring; 036 037 038 /** 039 * Value part of the element data structure. 040 */ 041 public final GenSolvablePolynomial<C> val; 042 043 044 /** 045 * Flag to remember if this residue element is a unit. -1 is unknown, 1 is 046 * unit, 0 not a unit. 047 */ 048 protected int isunit = -1; // initially unknown 049 050 051 /** 052 * The constructor creates a SolvableResidue object from a ring factory. 053 * @param r solvable residue ring factory. 054 */ 055 public SolvableResidue(SolvableResidueRing<C> r) { 056 this(r, r.ring.getZERO(), 0); 057 } 058 059 060 /** 061 * The constructor creates a SolvableResidue object from a ring factory and 062 * a polynomial. 063 * @param r solvable residue ring factory. 064 * @param a solvable polynomial. 065 */ 066 public SolvableResidue(SolvableResidueRing<C> r, GenSolvablePolynomial<C> a) { 067 this(r, a, -1); 068 } 069 070 071 /** 072 * The constructor creates a SolvableResidue object from a ring factory, a 073 * polynomial and an indicator if a is a unit. 074 * @param r solvable residue ring factory. 075 * @param a solvable polynomial. 076 * @param u isunit indicator, -1, 0, 1. 077 */ 078 public SolvableResidue(SolvableResidueRing<C> r, GenSolvablePolynomial<C> a, int u) { 079 ring = r; 080 val = ring.ideal.normalform(a); //.monic() no go 081 if (u == 0 || u == 1) { 082 isunit = u; 083 return; 084 } 085 if (val.isZERO()) { 086 isunit = 0; 087 return; 088 } 089 if (ring.isField()) { 090 isunit = 1; 091 return; 092 } 093 if (val.isUnit()) { 094 isunit = 1; 095 //} else { // not possible 096 //isunit = 0; 097 } 098 isunit = -1; 099 } 100 101 102 /** 103 * Get the corresponding element factory. 104 * @return factory for this Element. 105 * @see edu.jas.structure.Element#factory() 106 */ 107 public SolvableResidueRing<C> factory() { 108 return ring; 109 } 110 111 112 /** 113 * Value. Returns the value. 114 * @see edu.jas.structure.Value#value() 115 */ 116 public GenSolvablePolynomial<C> value() { 117 return val; 118 } 119 120 121 /** 122 * Numerator. Returns the value. 123 * @see edu.jas.structure.QuotPair#numerator() 124 */ 125 public GenSolvablePolynomial<C> numerator() { 126 return val; 127 } 128 129 130 /** 131 * Denominator. Returns 1. 132 * @see edu.jas.structure.QuotPair#denominator() 133 */ 134 public GenSolvablePolynomial<C> denominator() { 135 return ring.ring.getONE(); 136 } 137 138 139 /** 140 * Clone this. 141 * @see java.lang.Object#clone() 142 */ 143 @Override 144 public SolvableResidue<C> copy() { 145 return new SolvableResidue<C>(ring, val, isunit); 146 } 147 148 149 /** 150 * Is SolvableResidue zero. 151 * @return If this is 0 then true is returned, else false. 152 * @see edu.jas.structure.RingElem#isZERO() 153 */ 154 public boolean isZERO() { 155 return val.isZERO(); 156 } 157 158 159 /** 160 * Is SolvableResidue one. 161 * @return If this is 1 then true is returned, else false. 162 * @see edu.jas.structure.RingElem#isONE() 163 */ 164 public boolean isONE() { 165 return val.isONE(); 166 } 167 168 169 /** 170 * Is SolvableResidue unit. 171 * @return If this is a unit then true is returned, else false. 172 * @see edu.jas.structure.RingElem#isUnit() 173 */ 174 public boolean isUnit() { 175 if (isunit > 0) { 176 return true; 177 } 178 if (isunit == 0) { 179 return false; 180 } 181 // not jet known 182 boolean u = ring.ideal.isUnit(val); 183 if (u) { 184 isunit = 1; // seems to be wrong for solvable polynomial rings 185 } else { 186 isunit = 0; 187 } 188 return isunit > 0; 189 } 190 191 192 /** 193 * Is SolvableResidue a constant. 194 * @return true if this.val is a constant polynomial, else false. 195 */ 196 public boolean isConstant() { 197 return val.isConstant(); 198 } 199 200 201 /** 202 * Get the String representation as RingElem. 203 * @see java.lang.Object#toString() 204 */ 205 @Override 206 public String toString() { 207 if (PrettyPrint.isTrue()) { 208 return val.toString(ring.ring.getVars()); 209 } 210 return "SolvableResidue[ " + val.toString() + " mod " + ring.toString() + " ]"; 211 } 212 213 214 /** 215 * Get a scripting compatible string representation. 216 * @return script compatible representation for this Element. 217 * @see edu.jas.structure.Element#toScript() 218 */ 219 @Override 220 public String toScript() { 221 // Python case 222 return val.toScript(); 223 // return "PolySolvableResidue( " + val.toScript() 224 // + ", " + ring.toScript() + " )"; 225 } 226 227 228 /** 229 * Get a scripting compatible string representation of the factory. 230 * @return script compatible representation for this ElemFactory. 231 * @see edu.jas.structure.Element#toScriptFactory() 232 */ 233 @Override 234 public String toScriptFactory() { 235 // Python case 236 return factory().toScript(); 237 } 238 239 240 /** 241 * SolvableResidue comparison. 242 * @param b SolvableResidue. 243 * @return sign(this-b), 0 means that this and b are equivalent in this 244 * residue class ring. 245 */ 246 @Override 247 public int compareTo(SolvableResidue<C> b) { 248 GenSolvablePolynomial<C> v = b.val; 249 if (!ring.equals(b.ring)) { 250 v = ring.ideal.normalform(v); 251 } 252 return val.compareTo(v); 253 } 254 255 256 /** 257 * Comparison with any other object. 258 * @see java.lang.Object#equals(java.lang.Object) 259 * @return true means that this and b are equivalent in this residue class 260 * ring. 261 */ 262 @Override 263 @SuppressWarnings("unchecked") 264 public boolean equals(Object b) { 265 if (!(b instanceof SolvableResidue)) { 266 return false; 267 } 268 SolvableResidue<C> a = null; 269 try { 270 a = (SolvableResidue<C>) b; 271 } catch (ClassCastException e) { 272 } 273 if (a == null) { 274 return false; 275 } 276 return compareTo(a) == 0; 277 } 278 279 280 /** 281 * Hash code for this residue. 282 * @see java.lang.Object#hashCode() 283 */ 284 @Override 285 public int hashCode() { 286 int h; 287 h = ring.hashCode(); 288 h = 37 * h + val.hashCode(); 289 return h; 290 } 291 292 293 /** 294 * SolvableResidue absolute value. 295 * @return the absolute value of this. 296 * @see edu.jas.structure.RingElem#abs() 297 */ 298 public SolvableResidue<C> abs() { 299 return new SolvableResidue<C>(ring, (GenSolvablePolynomial<C>) val.abs(), isunit); 300 } 301 302 303 /** 304 * SolvableResidue summation. 305 * @param S SolvableResidue. 306 * @return this+S. 307 */ 308 public SolvableResidue<C> sum(SolvableResidue<C> S) { 309 return new SolvableResidue<C>(ring, (GenSolvablePolynomial<C>) val.sum(S.val)); 310 } 311 312 313 /** 314 * SolvableResidue negate. 315 * @return -this. 316 * @see edu.jas.structure.RingElem#negate() 317 */ 318 public SolvableResidue<C> negate() { 319 return new SolvableResidue<C>(ring, (GenSolvablePolynomial<C>) val.negate(), isunit); 320 } 321 322 323 /** 324 * SolvableResidue signum. 325 * @see edu.jas.structure.RingElem#signum() 326 * @return signum(this). 327 */ 328 public int signum() { 329 return val.signum(); 330 } 331 332 333 /** 334 * SolvableResidue subtraction. 335 * @param S SolvableResidue. 336 * @return this-S. 337 */ 338 public SolvableResidue<C> subtract(SolvableResidue<C> S) { 339 return new SolvableResidue<C>(ring, (GenSolvablePolynomial<C>) val.subtract(S.val)); 340 } 341 342 343 /** 344 * SolvableResidue division. 345 * @param S SolvableResidue. 346 * @return this/S. 347 */ 348 public SolvableResidue<C> divide(SolvableResidue<C> S) { 349 if (ring.isField()) { 350 return multiply(S.inverse()); 351 } 352 try { 353 return multiply(S.inverse()); 354 } catch (NotInvertibleException ignored) { 355 System.out.println("catch: " + ignored); 356 //ignored.printStackTrace(); 357 // ignored 358 } 359 List<GenSolvablePolynomial<C>> Q = new ArrayList<GenSolvablePolynomial<C>>(1); 360 Q.add(ring.ring.getZERO()); 361 List<GenSolvablePolynomial<C>> V = new ArrayList<GenSolvablePolynomial<C>>(1); 362 V.add(S.val); 363 GenSolvablePolynomial<C> x = ring.bb.sred.leftNormalform(Q, V, val); 364 GenSolvablePolynomial<C> y = Q.get(0); 365 System.out.println("SolvableResidue val = " + val + ", div = " + S.val + ", quotient = " + y 366 + ", remainder = " + x); 367 return new SolvableResidue<C>(ring, y); 368 } 369 370 371 /** 372 * SolvableResidue inverse. 373 * @see edu.jas.structure.RingElem#inverse() 374 * @return S with S = 1/this if defined. 375 */ 376 public SolvableResidue<C> inverse() { 377 GenSolvablePolynomial<C> x = ring.ideal.inverse(val); 378 SolvableResidue<C> xp = new SolvableResidue<C>(ring, x, 1); 379 if (xp.isZERO()) { 380 throw new NotInvertibleException("(" + x + ") * (" + val + ") = " + x.multiply(val) + " = 0 mod " 381 + ring.ideal); 382 } 383 if (!xp.multiply(this).isONE()) { 384 throw new NotInvertibleException("(" + x + ") * (" + val + ") = " + x.multiply(val) 385 + " != 1 mod " + ring.ideal); 386 } 387 return xp; 388 } 389 390 391 /** 392 * SolvableResidue remainder. 393 * @param S SolvableResidue. 394 * @return this - (this/S)*S. 395 */ 396 public SolvableResidue<C> remainder(SolvableResidue<C> S) { 397 List<GenSolvablePolynomial<C>> V = new ArrayList<GenSolvablePolynomial<C>>(1); 398 V.add(S.val); 399 GenSolvablePolynomial<C> x = ring.bb.sred.leftNormalform(V, val); 400 return new SolvableResidue<C>(ring, x); 401 } 402 403 404 /** 405 * SolvableResidue multiplication. 406 * @param S SolvableResidue. 407 * @return this*S. 408 */ 409 public SolvableResidue<C> multiply(SolvableResidue<C> S) { 410 GenSolvablePolynomial<C> x = val.multiply(S.val); 411 int i = -1; 412 if (isunit == 1 && S.isunit == 1) { 413 i = 1; 414 } else if (isunit == 0 || S.isunit == 0) { 415 i = 0; 416 } 417 return new SolvableResidue<C>(ring, x, i); 418 } 419 420 421 /** 422 * SolvableResidue multiplication. 423 * @param S GenSolvablePolynomial. 424 * @return this*S. 425 */ 426 public SolvableResidue<C> multiply(GenSolvablePolynomial<C> S) { 427 GenSolvablePolynomial<C> x = val.multiply(S); 428 int i = -1; 429 if (isunit == 1 && S.isUnit()) { 430 i = 1; 431 } else if (isunit == 0 || !S.isUnit()) { 432 i = 0; 433 } 434 return new SolvableResidue<C>(ring, x, i); 435 } 436 437 438 /* 439 * SolvableResidue multiplication. 440 * @param s coefficient. 441 * @return this*s. 442 */ 443 public SolvableResidue<C> multiply(C s) { 444 GenSolvablePolynomial<C> x = val.multiply(s); 445 int i = -1; 446 if (isunit == 1 && s.isUnit()) { 447 i = 1; 448 } else if (isunit == 0 || !s.isUnit()) { 449 i = 0; 450 } 451 return new SolvableResidue<C>(ring, x, i); 452 } 453 454 455 /** 456 * SolvableResidue multiplication. 457 * @param e exponent. 458 * @return this*X<sup>e</sup>. 459 */ 460 public SolvableResidue<C> multiply(ExpVector e) { 461 GenSolvablePolynomial<C> x = val.multiply(e); 462 int i = -1; 463 if (isunit == 1 && e.isZERO()) { 464 i = 1; 465 } else if (isunit == 0 || !e.isZERO()) { 466 i = 0; 467 } 468 return new SolvableResidue<C>(ring, x, i); 469 } 470 471 472 /** 473 * SolvableResidue monic. 474 * @return this with monic value part. 475 */ 476 public SolvableResidue<C> monic() { 477 return new SolvableResidue<C>(ring, val.monic(), isunit); 478 } 479 480 481 /** 482 * Greatest common divisor. 483 * @param b other element. 484 * @return gcd(this,b). 485 */ 486 public SolvableResidue<C> gcd(SolvableResidue<C> b) { 487 throw new UnsupportedOperationException("gcd not implemented"); 488 // GenSolvablePolynomial<C> x = ring.engine.gcd(val, b.val); 489 // int i = -1; // gcd might become a unit 490 // if (x.isONE()) { 491 // i = 1; 492 // } else { 493 // System.out.println("SolvableResidue gcd = " + x); 494 // } 495 // if (isunit == 1 && b.isunit == 1) { 496 // i = 1; 497 // } 498 // return new SolvableResidue<C>(ring, x, i); 499 } 500 501 502 /** 503 * Extended greatest common divisor. <b>Note: </b>Not implemented, throws 504 * UnsupportedOperationException. 505 * @param b other element. 506 * @return [ gcd(this,b), c1, c2 ] with c1*this + c2*b = gcd(this,b). 507 */ 508 public SolvableResidue<C>[] egcd(SolvableResidue<C> b) { 509 throw new UnsupportedOperationException("egcd not implemented"); 510 } 511}