001/* 002 * $Id: AlgebraicNumberRing.java 4956 2014-10-16 22:45:10Z kredel $ 003 */ 004 005package edu.jas.poly; 006 007 008import java.io.Reader; 009import java.util.ArrayList; 010import java.util.Iterator; 011import java.util.List; 012import java.util.Random; 013 014import org.apache.log4j.Logger; 015 016import edu.jas.kern.Scripting; 017import edu.jas.structure.RingElem; 018import edu.jas.structure.RingFactory; 019import edu.jas.util.CartesianProduct; 020import edu.jas.util.CartesianProductInfinite; 021 022 023/** 024 * Algebraic number factory. Based on GenPolynomial factory with RingElem 025 * interface. Objects of this class are immutable. 026 * @author Heinz Kredel 027 */ 028 029public class AlgebraicNumberRing<C extends RingElem<C>> implements RingFactory<AlgebraicNumber<C>>, 030 Iterable<AlgebraicNumber<C>> { 031 032 033 /** 034 * Ring part of the factory data structure. 035 */ 036 public final GenPolynomialRing<C> ring; 037 038 039 /** 040 * Module part of the factory data structure. 041 */ 042 public final GenPolynomial<C> modul; 043 044 045 /** 046 * Indicator if this ring is a field 047 */ 048 protected int isField = -1; // initially unknown 049 050 051 private static final Logger logger = Logger.getLogger(AlgebraicNumberRing.class); 052 053 054 // private final boolean debug = logger.isDebugEnabled(); 055 056 057 /** 058 * The constructor creates a AlgebraicNumber factory object from a 059 * GenPolynomial objects module. 060 * @param m module GenPolynomial<C>. 061 */ 062 public AlgebraicNumberRing(GenPolynomial<C> m) { 063 ring = m.ring; 064 modul = m; // assert m != 0 065 if (ring.nvar > 1) { 066 throw new IllegalArgumentException("only univariate polynomials allowed"); 067 } 068 } 069 070 071 /** 072 * The constructor creates a AlgebraicNumber factory object from a 073 * GenPolynomial objects module. 074 * @param m module GenPolynomial<C>. 075 * @param isField indicator if m is prime. 076 */ 077 public AlgebraicNumberRing(GenPolynomial<C> m, boolean isField) { 078 ring = m.ring; 079 modul = m; // assert m != 0 080 this.isField = (isField ? 1 : 0); 081 if (ring.nvar > 1) { 082 throw new IllegalArgumentException("only univariate polynomials allowed"); 083 } 084 } 085 086 087 /** 088 * Get the module part. 089 * @return modul. 090 */ 091 public GenPolynomial<C> getModul() { 092 return modul; 093 } 094 095 096 /** 097 * Copy AlgebraicNumber element c. 098 * @param c algebraic number to copy. 099 * @return a copy of c. 100 */ 101 public AlgebraicNumber<C> copy(AlgebraicNumber<C> c) { 102 return new AlgebraicNumber<C>(this, c.val); 103 } 104 105 106 /** 107 * Get the zero element. 108 * @return 0 as AlgebraicNumber. 109 */ 110 public AlgebraicNumber<C> getZERO() { 111 return new AlgebraicNumber<C>(this, ring.getZERO()); 112 } 113 114 115 /** 116 * Get the one element. 117 * @return 1 as AlgebraicNumber. 118 */ 119 public AlgebraicNumber<C> getONE() { 120 return new AlgebraicNumber<C>(this, ring.getONE()); 121 } 122 123 124 /** 125 * Get the generating element. 126 * @return alpha as AlgebraicNumber. 127 */ 128 public AlgebraicNumber<C> getGenerator() { 129 return new AlgebraicNumber<C>(this, ring.univariate(0)); 130 } 131 132 133 /** 134 * Get a list of the generating elements. 135 * @return list of generators for the algebraic structure. 136 * @see edu.jas.structure.ElemFactory#generators() 137 */ 138 public List<AlgebraicNumber<C>> generators() { 139 List<GenPolynomial<C>> gc = ring.generators(); 140 List<AlgebraicNumber<C>> gens = new ArrayList<AlgebraicNumber<C>>(gc.size()); 141 for (GenPolynomial<C> g : gc) { 142 gens.add(new AlgebraicNumber<C>(this, g)); 143 } 144 return gens; 145 } 146 147 148 /** 149 * Is this structure finite or infinite. 150 * @return true if this structure is finite, else false. 151 * @see edu.jas.structure.ElemFactory#isFinite() 152 */ 153 public boolean isFinite() { 154 return ring.coFac.isFinite(); 155 } 156 157 158 /** 159 * Query if this ring is commutative. 160 * @return true if this ring is commutative, else false. 161 */ 162 public boolean isCommutative() { 163 return ring.isCommutative(); 164 } 165 166 167 /** 168 * Query if this ring is associative. 169 * @return true if this ring is associative, else false. 170 */ 171 public boolean isAssociative() { 172 return ring.isAssociative(); 173 } 174 175 176 /** 177 * Query if this ring is a field. 178 * @return true if modul is prime, else false. 179 */ 180 public boolean isField() { 181 if (isField > 0) { 182 return true; 183 } 184 if (isField == 0) { 185 return false; 186 } 187 if (!ring.coFac.isField()) { 188 isField = 0; 189 return false; 190 } 191 return false; 192 } 193 194 195 /** 196 * Set field property of this ring. 197 * @param field true, if this ring is determined to be a field, false, if it 198 * is determined that it is not a field. 199 */ 200 public void setField(boolean field) { 201 if (isField > 0 && field) { 202 return; 203 } 204 if (isField == 0 && !field) { 205 return; 206 } 207 if (field) { 208 isField = 1; 209 } else { 210 isField = 0; 211 } 212 return; 213 } 214 215 216 /** 217 * Get the internal field indicator. 218 * @return internal field indicator. 219 */ 220 public int getField() { 221 return isField; 222 } 223 224 225 /** 226 * Characteristic of this ring. 227 * @return characteristic of this ring. 228 */ 229 public java.math.BigInteger characteristic() { 230 return ring.characteristic(); 231 } 232 233 234 /** 235 * Get a AlgebraicNumber element from a BigInteger value. 236 * @param a BigInteger. 237 * @return a AlgebraicNumber. 238 */ 239 public AlgebraicNumber<C> fillFromInteger(java.math.BigInteger a) { 240 if (characteristic().signum() == 0) { 241 return new AlgebraicNumber<C>(this, ring.fromInteger(a)); 242 } 243 java.math.BigInteger p = characteristic(); 244 java.math.BigInteger b = a; 245 GenPolynomial<C> v = ring.getZERO(); 246 GenPolynomial<C> x = ring.univariate(0, 1L); 247 GenPolynomial<C> t = ring.getONE(); 248 do { 249 java.math.BigInteger[] qr = b.divideAndRemainder(p); 250 java.math.BigInteger q = qr[0]; 251 java.math.BigInteger r = qr[1]; 252 //System.out.println("q = " + q + ", r = " +r); 253 GenPolynomial<C> rp = ring.fromInteger(r); 254 v = v.sum(t.multiply(rp)); 255 t = t.multiply(x); 256 b = q; 257 } while (!b.equals(java.math.BigInteger.ZERO)); 258 AlgebraicNumber<C> an = new AlgebraicNumber<C>(this, v); 259 logger.info("fill(" + a + ") = " + v + ", mod: " + an); 260 //RuntimeException e = new RuntimeException("hihihi"); 261 //e.printStackTrace(); 262 return an; 263 } 264 265 266 /** 267 * Get a AlgebraicNumber element from a long value. 268 * @param a long. 269 * @return a AlgebraicNumber. 270 */ 271 public AlgebraicNumber<C> fillFromInteger(long a) { 272 return fillFromInteger(new java.math.BigInteger("" + a)); 273 } 274 275 276 /** 277 * Get a AlgebraicNumber element from a BigInteger value. 278 * @param a BigInteger. 279 * @return a AlgebraicNumber. 280 */ 281 public AlgebraicNumber<C> fromInteger(java.math.BigInteger a) { 282 return new AlgebraicNumber<C>(this, ring.fromInteger(a)); 283 } 284 285 286 /** 287 * Get a AlgebraicNumber element from a long value. 288 * @param a long. 289 * @return a AlgebraicNumber. 290 */ 291 public AlgebraicNumber<C> fromInteger(long a) { 292 return new AlgebraicNumber<C>(this, ring.fromInteger(a)); 293 // if ( characteristic().signum() == 0 ) { 294 // } 295 // return fromInteger( new java.math.BigInteger(""+a) ); 296 } 297 298 299 /** 300 * Get the String representation as RingFactory. 301 * @see java.lang.Object#toString() 302 */ 303 @Override 304 public String toString() { 305 return "AlgebraicNumberRing[ " + modul.toString() + " | isField=" + isField + " :: " 306 + ring.toString() + " ]"; 307 } 308 309 310 /** 311 * Get a scripting compatible string representation. 312 * @return script compatible representation for this ElemFactory. 313 * @see edu.jas.structure.ElemFactory#toScript() 314 */ 315 @Override 316 public String toScript() { 317 StringBuffer s = new StringBuffer(); 318 s.append("AN("); 319 s.append(modul.toScript()); 320 switch (Scripting.getLang()) { 321 case Ruby: 322 s.append((isField() ? ",true" : ",false")); 323 break; 324 case Python: 325 default: 326 s.append((isField() ? ",True" : ",False")); 327 } 328 s.append(","); 329 s.append(ring.toScript()); 330 s.append(")"); 331 return s.toString(); 332 } 333 334 335 /** 336 * Comparison with any other object. 337 * @see java.lang.Object#equals(java.lang.Object) 338 */ 339 @Override 340 @SuppressWarnings("unchecked") 341 // not jet working 342 public boolean equals(Object b) { 343 if (b == null) { 344 return false; 345 } 346 if (!(b instanceof AlgebraicNumberRing)) { 347 return false; 348 } 349 AlgebraicNumberRing<C> a = (AlgebraicNumberRing<C>) b; 350 return modul.equals(a.modul); 351 } 352 353 354 /** 355 * Hash code for this AlgebraicNumber. 356 * @see java.lang.Object#hashCode() 357 */ 358 @Override 359 public int hashCode() { 360 return 37 * modul.hashCode() + ring.hashCode(); 361 } 362 363 364 /** 365 * AlgebraicNumber random. 366 * @param n such that 0 ≤ v ≤ (2<sup>n</sup>-1). 367 * @return a random integer mod modul. 368 */ 369 public AlgebraicNumber<C> random(int n) { 370 GenPolynomial<C> x = ring.random(n).monic(); 371 return new AlgebraicNumber<C>(this, x); 372 } 373 374 375 /** 376 * AlgebraicNumber random. 377 * @param n such that 0 ≤ v ≤ (2<sup>n</sup>-1). 378 * @param rnd is a source for random bits. 379 * @return a random integer mod modul. 380 */ 381 public AlgebraicNumber<C> random(int n, Random rnd) { 382 GenPolynomial<C> x = ring.random(n, rnd).monic(); 383 return new AlgebraicNumber<C>(this, x); 384 } 385 386 387 /** 388 * Parse AlgebraicNumber from String. 389 * @param s String. 390 * @return AlgebraicNumber from s. 391 */ 392 public AlgebraicNumber<C> parse(String s) { 393 GenPolynomial<C> x = ring.parse(s); 394 return new AlgebraicNumber<C>(this, x); 395 } 396 397 398 /** 399 * Parse AlgebraicNumber from Reader. 400 * @param r Reader. 401 * @return next AlgebraicNumber from r. 402 */ 403 public AlgebraicNumber<C> parse(Reader r) { 404 GenPolynomial<C> x = ring.parse(r); 405 return new AlgebraicNumber<C>(this, x); 406 } 407 408 409 /** 410 * AlgebraicNumber chinese remainder algorithm. Assert deg(c.modul) >= 411 * deg(a.modul) and c.modul * a.modul = this.modul. 412 * @param c AlgebraicNumber. 413 * @param ci inverse of c.modul in ring of a. 414 * @param a other AlgebraicNumber. 415 * @return S, with S mod c.modul == c and S mod a.modul == a. 416 */ 417 public AlgebraicNumber<C> chineseRemainder(AlgebraicNumber<C> c, AlgebraicNumber<C> ci, 418 AlgebraicNumber<C> a) { 419 if (true) { // debug 420 if (c.ring.modul.compareTo(a.ring.modul) < 1) { 421 System.out.println("AlgebraicNumber error " + c + ", " + a); 422 } 423 } 424 AlgebraicNumber<C> b = new AlgebraicNumber<C>(a.ring, c.val); 425 // c mod a.modul 426 // c( tbcf(a.modul) ) if deg(a.modul)==1 427 AlgebraicNumber<C> d = a.subtract(b); // a-c mod a.modul 428 if (d.isZERO()) { 429 return new AlgebraicNumber<C>(this, c.val); 430 } 431 b = d.multiply(ci); // b = (a-c)*ci mod a.modul 432 // (c.modul*b)+c mod this.modul = c mod c.modul = 433 // (c.modul*ci*(a-c)+c) mod a.modul = a mod a.modul 434 GenPolynomial<C> s = c.ring.modul.multiply(b.val); 435 s = s.sum(c.val); 436 return new AlgebraicNumber<C>(this, s); 437 } 438 439 440 /** 441 * AlgebraicNumber interpolation algorithm. Assert deg(c.modul) >= 442 * deg(A.modul) and c.modul * A.modul = this.modul. Special case with 443 * deg(A.modul) == 1. Similar algorithm as chinese remainder algortihm. 444 * @param c AlgebraicNumber. 445 * @param ci inverse of (c.modul)(a) in ring of A. 446 * @param am trailing base coefficient of modul of other AlgebraicNumber A. 447 * @param a value of other AlgebraicNumber A. 448 * @return S, with S(c) == c and S(A) == a. 449 */ 450 public AlgebraicNumber<C> interpolate(AlgebraicNumber<C> c, C ci, C am, C a) { 451 C b = PolyUtil.<C> evaluateMain(ring.coFac /*a*/, c.val, am); 452 // c mod a.modul 453 // c( tbcf(a.modul) ) if deg(a.modul)==1 454 C d = a.subtract(b); // a-c mod a.modul 455 if (d.isZERO()) { 456 return new AlgebraicNumber<C>(this, c.val); 457 } 458 b = d.multiply(ci); // b = (a-c)*ci mod a.modul 459 // (c.modul*b)+c mod this.modul = c mod c.modul = 460 // (c.modul*ci*(a-c)+c) mod a.modul = a mod a.modul 461 GenPolynomial<C> s = c.ring.modul.multiply(b); 462 s = s.sum(c.val); 463 return new AlgebraicNumber<C>(this, s); 464 } 465 466 467 /** 468 * Depth of extension field tower. 469 * @return number of nested algebraic extension fields 470 */ 471 @SuppressWarnings({ "unchecked", "cast" }) 472 public int depth() { 473 AlgebraicNumberRing<C> arr = this; 474 int depth = 1; 475 RingFactory<C> cf = arr.ring.coFac; 476 if (cf instanceof AlgebraicNumberRing) { 477 arr = (AlgebraicNumberRing<C>) (Object) cf; 478 depth += arr.depth(); 479 } 480 return depth; 481 } 482 483 484 /** 485 * Degree of extension field. 486 * @return degree of this algebraic extension field 487 */ 488 public long extensionDegree() { 489 long degree = modul.degree(0); 490 return degree; 491 } 492 493 494 /** 495 * Total degree of nested extension fields. 496 * @return degree of tower of algebraic extension fields 497 */ 498 @SuppressWarnings({ "unchecked", "cast" }) 499 public long totalExtensionDegree() { 500 long degree = modul.degree(0); 501 AlgebraicNumberRing<C> arr = this; 502 RingFactory<C> cf = arr.ring.coFac; 503 if (cf instanceof AlgebraicNumberRing) { 504 arr = (AlgebraicNumberRing<C>) (Object) cf; 505 if (degree == 0L) { 506 degree = arr.totalExtensionDegree(); 507 } else { 508 degree *= arr.totalExtensionDegree(); 509 } 510 } 511 return degree; 512 } 513 514 515 /** 516 * Get a AlgebraicNumber iterator. <b>Note: </b> Only for finite field 517 * coefficients or fields which are iterable. 518 * @return a iterator over all algebraic numbers in this ring. 519 */ 520 public Iterator<AlgebraicNumber<C>> iterator() { 521 return new AlgebraicNumberIterator<C>(this); 522 } 523 524} 525 526 527/** 528 * Algebraic number iterator. 529 * @author Heinz Kredel 530 */ 531class AlgebraicNumberIterator<C extends RingElem<C>> implements Iterator<AlgebraicNumber<C>> { 532 533 534 /** 535 * data structure. 536 */ 537 final Iterator<List<C>> iter; 538 539 540 final List<GenPolynomial<C>> powers; 541 542 543 final AlgebraicNumberRing<C> aring; 544 545 546 private static final Logger logger = Logger.getLogger(AlgebraicNumberIterator.class); 547 548 549 // private final boolean debug = logger.isDebugEnabled(); 550 551 552 /** 553 * CartesianProduct iterator constructor. 554 * @param aring AlgebraicNumberRing components of the Cartesian product. 555 */ 556 @SuppressWarnings("unchecked") 557 public AlgebraicNumberIterator(AlgebraicNumberRing<C> aring) { 558 RingFactory<C> cf = aring.ring.coFac; 559 this.aring = aring; 560 long d = aring.modul.degree(0); 561 //System.out.println("d = " + d); 562 powers = new ArrayList<GenPolynomial<C>>((int) d); 563 for (long j = d - 1; j >= 0L; j--) { 564 powers.add(aring.ring.univariate(0, j)); 565 } 566 //System.out.println("powers = " + powers); 567 if (!(cf instanceof Iterable)) { 568 throw new IllegalArgumentException("only for iterable coefficients implemented"); 569 } 570 List<Iterable<C>> comps = new ArrayList<Iterable<C>>((int) d); 571 Iterable<C> cfi = (Iterable<C>) cf; 572 for (long j = 0L; j < d; j++) { 573 comps.add(cfi); 574 } 575 if (cf.isFinite()) { 576 CartesianProduct<C> tuples = new CartesianProduct<C>(comps); 577 iter = tuples.iterator(); 578 } else { 579 CartesianProductInfinite<C> tuples = new CartesianProductInfinite<C>(comps); 580 iter = tuples.iterator(); 581 } 582 if (logger.isInfoEnabled()) { 583 logger.info("iterator for degree " + d + ", finite = " + cf.isFinite()); 584 } 585 } 586 587 588 /** 589 * Test for availability of a next tuple. 590 * @return true if the iteration has more tuples, else false. 591 */ 592 public boolean hasNext() { 593 return iter.hasNext(); 594 } 595 596 597 /** 598 * Get next tuple. 599 * @return next tuple. 600 */ 601 public AlgebraicNumber<C> next() { 602 List<C> coeffs = iter.next(); 603 //System.out.println("coeffs = " + coeffs); 604 GenPolynomial<C> pol = aring.ring.getZERO(); 605 int i = 0; 606 for (GenPolynomial<C> f : powers) { 607 C c = coeffs.get(i++); 608 if (c.isZERO()) { 609 continue; 610 } 611 pol = pol.sum(f.multiply(c)); 612 } 613 return new AlgebraicNumber<C>(aring, pol); 614 } 615 616 617 /** 618 * Remove a tuple if allowed. 619 */ 620 public void remove() { 621 throw new UnsupportedOperationException("cannnot remove tuples"); 622 } 623 624}