001/* 002 * $Id$ 003 */ 004 005package edu.jas.application; 006 007 008import java.io.Reader; 009import java.util.ArrayList; 010import java.util.List; 011import java.util.Random; 012import java.util.SortedSet; 013import java.util.TreeSet; 014 015import org.apache.logging.log4j.Logger; 016import org.apache.logging.log4j.LogManager; 017 018import edu.jas.gb.SolvableGroebnerBaseAbstract; 019import edu.jas.gb.SolvableGroebnerBaseSeq; 020import edu.jas.poly.GenPolynomial; 021import edu.jas.poly.GenSolvablePolynomial; 022import edu.jas.poly.GenSolvablePolynomialRing; 023import edu.jas.structure.GcdRingElem; 024import edu.jas.structure.RingFactory; 025import edu.jas.structure.QuotPair; 026import edu.jas.structure.QuotPairFactory; 027import edu.jas.structure.Value; 028import edu.jas.structure.ValueFactory; 029 030 031/** 032 * SolvableResidue ring factory based on GenSolvablePolynomialRing with 033 * GcdRingFactory interface. Objects of this class are immutable. 034 * @author Heinz Kredel 035 */ 036public class SolvableResidueRing<C extends GcdRingElem<C>> 037 implements RingFactory<SolvableResidue<C>>, 038 QuotPairFactory<GenPolynomial<C>, SolvableResidue<C>>, 039 ValueFactory<GenPolynomial<C>, SolvableResidue<C>> { 040 041 042 private static final Logger logger = LogManager.getLogger(SolvableResidueRing.class); 043 044 045 //private static final boolean debug = logger.isDebugEnabled(); 046 047 048 /** 049 * Groebner base engine. 050 */ 051 protected final SolvableGroebnerBaseAbstract<C> bb; 052 053 054 /** 055 * Solvable polynomial ideal for the reduction. 056 */ 057 public final SolvableIdeal<C> ideal; 058 059 060 /** 061 * Polynomial ring of the factory. Shortcut to ideal.list.ring. 062 */ 063 public final GenSolvablePolynomialRing<C> ring; 064 065 066 /** 067 * Indicator if this ring is a field. 068 */ 069 protected int isField = -1; // initially unknown 070 071 072 /** 073 * The constructor creates a SolvableResidueRing object from an Ideal. 074 * @param i polynomial ideal. 075 */ 076 public SolvableResidueRing(SolvableIdeal<C> i) { 077 this(i, false); 078 } 079 080 081 /** 082 * The constructor creates a SolvableResidueRing object from an 083 * SolvableIdeal. 084 * @param i solvable polynomial ideal. 085 * @param isMaximal true, if ideal is maxmal. 086 */ 087 public SolvableResidueRing(SolvableIdeal<C> i, boolean isMaximal) { 088 ideal = i.GB(); // cheap if isGB 089 ring = ideal.getRing(); 090 bb = new SolvableGroebnerBaseSeq<C>(); 091 if (isMaximal) { 092 isField = 1; 093 return; 094 } 095 if (ideal.isONE()) { 096 logger.warn("ideal is one, so all residues are 0"); 097 } 098 //System.out.println("rr ring = " + ring.getClass().getName()); 099 //System.out.println("rr cofac = " + ring.coFac.getClass().getName()); 100 } 101 102 103 /** 104 * Factory for base elements. 105 */ 106 public GenSolvablePolynomialRing<C> pairFactory() { 107 return ring; 108 } 109 110 111 /** 112 * Factory for base elements. 113 */ 114 public GenSolvablePolynomialRing<C> valueFactory() { 115 return ring; 116 } 117 118 119 /** 120 * Create from numerator. 121 */ 122 @SuppressWarnings("unchecked") 123 public SolvableResidue<C> create(GenPolynomial<C> n) { 124 return new SolvableResidue<C>(this, (GenSolvablePolynomial<C>) n); 125 } 126 127 128 /** 129 * Create from numerator, denominator pair. 130 */ 131 @SuppressWarnings("unchecked") 132 public SolvableResidue<C> create(GenPolynomial<C> n, GenPolynomial<C> d) { 133 if (d != null && !d.isONE()) { 134 throw new UnsupportedOperationException("d must be 1, but d = " + d); 135 } 136 return new SolvableResidue<C>(this, (GenSolvablePolynomial<C>) n); 137 } 138 139 140 /** 141 * Is this structure finite or infinite. 142 * @return true if this structure is finite, else false. 143 * @see edu.jas.structure.ElemFactory#isFinite() 144 */ 145 public boolean isFinite() { 146 return ideal.commonZeroTest() <= 0 && ring.coFac.isFinite(); 147 } 148 149 150 /** 151 * Copy SolvableResidue element c. 152 * @param c 153 * @return a copy of c. 154 */ 155 public SolvableResidue<C> copy(SolvableResidue<C> c) { 156 //System.out.println("rr copy in = " + c.val); 157 if (c == null) { // where does this happen? 158 return getZERO(); // or null? 159 } 160 SolvableResidue<C> r = new SolvableResidue<C>(this, c.val); 161 //System.out.println("rr copy out = " + r.val); 162 //System.out.println("rr copy ideal = " + ideal.list.list); 163 return r; //new SolvableResidue<C>( c.ring, c.val ); 164 } 165 166 167 /** 168 * Get the zero element. 169 * @return 0 as SolvableResidue. 170 */ 171 public SolvableResidue<C> getZERO() { 172 return new SolvableResidue<C>(this, ring.getZERO()); 173 } 174 175 176 /** 177 * Get the one element. 178 * @return 1 as SolvableResidue. 179 */ 180 public SolvableResidue<C> getONE() { 181 SolvableResidue<C> one = new SolvableResidue<C>(this, ring.getONE()); 182 if (one.isZERO()) { 183 logger.warn("ideal is one, so all residues are 0"); 184 } 185 return one; 186 } 187 188 189 /** 190 * Get a list of the generating elements. 191 * @return list of generators for the algebraic structure. 192 * @see edu.jas.structure.ElemFactory#generators() 193 */ 194 public List<SolvableResidue<C>> generators() { 195 List<GenPolynomial<C>> pgens = ring.generators(); 196 List<SolvableResidue<C>> gens = new ArrayList<SolvableResidue<C>>(pgens.size()); 197 SortedSet<SolvableResidue<C>> sgens = new TreeSet<SolvableResidue<C>>(); 198 List<GenSolvablePolynomial<C>> rgens = new ArrayList<GenSolvablePolynomial<C>>(pgens.size()); 199 SolvableIdeal<C> gi = new SolvableIdeal<C>(ring, rgens); 200 SolvableResidueRing<C> gr = new SolvableResidueRing<C>(gi); 201 for (GenPolynomial<C> p : pgens) { 202 GenSolvablePolynomial<C> s = (GenSolvablePolynomial<C>) p; 203 SolvableResidue<C> r = new SolvableResidue<C>(this, s); 204 if (r.isZERO()) { 205 continue; 206 } 207 if (!r.isONE() && r.val.isConstant()) { 208 continue; 209 } 210 // avoid duplicate generators 211 SolvableResidue<C> x = new SolvableResidue<C>(gr, r.val); 212 if (x.isZERO()) { 213 continue; 214 } 215 if (!x.isONE() && x.val.isConstant()) { 216 continue; 217 } 218 r = new SolvableResidue<C>(this, x.val); 219 if (r.isZERO()) { 220 continue; 221 } 222 r = r.monic(); 223 if (!r.isONE() && !r.val.isConstant()) { 224 rgens.add(r.val); 225 //System.out.println("rgens = " + rgens); 226 gi = new SolvableIdeal<C>(ring, rgens); 227 gr = new SolvableResidueRing<C>(gi); 228 } 229 //gens.add(r); 230 sgens.add(r); 231 } 232 gens.addAll(sgens); 233 return gens; 234 } 235 236 237 /** 238 * Query if this ring is commutative. 239 * @return true if this ring is commutative, else false. 240 */ 241 public boolean isCommutative() { 242 return ring.isCommutative(); // check also vector space structure 243 } 244 245 246 /** 247 * Query if this ring is associative. 248 * @return true if this ring is associative, else false. 249 */ 250 public boolean isAssociative() { 251 return ring.isAssociative(); // sufficient ?? 252 } 253 254 255 /** 256 * Query if this ring is a field. 257 * @return false. 258 */ 259 public boolean isField() { 260 if (isField > 0) { 261 return true; 262 } 263 if (isField == 0) { 264 return false; 265 } 266 if (ideal.isMaximal()) { 267 isField = 1; 268 return true; 269 } 270 return false; 271 } 272 273 274 /** 275 * Characteristic of this ring. 276 * @return characteristic of this ring. 277 */ 278 public java.math.BigInteger characteristic() { 279 return ring.characteristic(); 280 } 281 282 283 /** 284 * Get a SolvableResidue element from a BigInteger value. 285 * @param a BigInteger. 286 * @return a SolvableResidue. 287 */ 288 public SolvableResidue<C> fromInteger(java.math.BigInteger a) { 289 return new SolvableResidue<C>(this, ring.fromInteger(a)); 290 } 291 292 293 /** 294 * Get a SolvableResidue element from a long value. 295 * @param a long. 296 * @return a SolvableResidue. 297 */ 298 public SolvableResidue<C> fromInteger(long a) { 299 return new SolvableResidue<C>(this, ring.fromInteger(a)); 300 } 301 302 303 /** 304 * Get the String representation as RingFactory. 305 * @see java.lang.Object#toString() 306 */ 307 @Override 308 public String toString() { 309 return "SolvableResidueRing[ " + ideal.toString() + " ]"; 310 } 311 312 313 /** 314 * Get a scripting compatible string representation. 315 * @return script compatible representation for this ElemFactory. 316 * @see edu.jas.structure.ElemFactory#toScript() 317 */ 318 @Override 319 public String toScript() { 320 // Python case 321 return "SRC(" + ideal.list.toScript() + ")"; 322 //return "SRC(" + ideal.toScript() + "," + ring.toScript() + ")"; 323 } 324 325 326 /** 327 * Comparison with any other object. 328 * @see java.lang.Object#equals(java.lang.Object) 329 */ 330 @Override 331 @SuppressWarnings("unchecked") 332 public boolean equals(Object b) { 333 if (!(b instanceof SolvableResidueRing)) { 334 return false; 335 } 336 SolvableResidueRing<C> a = null; 337 try { 338 a = (SolvableResidueRing<C>) b; 339 } catch (ClassCastException e) { 340 } 341 if (a == null) { 342 return false; 343 } 344 if (!ring.equals(a.ring)) { 345 return false; 346 } 347 return ideal.equals(a.ideal); 348 } 349 350 351 /** 352 * Hash code for this residue ring. 353 * @see java.lang.Object#hashCode() 354 */ 355 @Override 356 public int hashCode() { 357 int h; 358 h = ideal.hashCode(); 359 return h; 360 } 361 362 363 /** 364 * SolvableResidue random. 365 * @param n such that 0 ≤ v ≤ (2<sup>n</sup>-1). 366 * @return a random residue element. 367 */ 368 public SolvableResidue<C> random(int n) { 369 GenSolvablePolynomial<C> x = ring.random(n).monic(); 370 return new SolvableResidue<C>(this, x); 371 } 372 373 374 /** 375 * Generate a random residum polynomial. 376 * @param k bitsize of random coefficients. 377 * @param l number of terms. 378 * @param d maximal degree in each variable. 379 * @param q density of nozero exponents. 380 * @return a random residue polynomial. 381 */ 382 public SolvableResidue<C> random(int k, int l, int d, float q) { 383 GenSolvablePolynomial<C> x = ring.random(k, l, d, q).monic(); 384 return new SolvableResidue<C>(this, x); 385 } 386 387 388 /** 389 * SolvableResidue random. 390 * @param n such that 0 ≤ v ≤ (2<sup>n</sup>-1). 391 * @param rnd is a source for random bits. 392 * @return a random residue element. 393 */ 394 public SolvableResidue<C> random(int n, Random rnd) { 395 GenSolvablePolynomial<C> x = ring.random(n, rnd).monic(); 396 return new SolvableResidue<C>(this, x); 397 } 398 399 400 /** 401 * Parse SolvableResidue from String. 402 * @param s String. 403 * @return SolvableResidue from s. 404 */ 405 public SolvableResidue<C> parse(String s) { 406 GenSolvablePolynomial<C> x = ring.parse(s); 407 return new SolvableResidue<C>(this, x); 408 } 409 410 411 /** 412 * Parse SolvableResidue from Reader. 413 * @param r Reader. 414 * @return next SolvableResidue from r. 415 */ 416 public SolvableResidue<C> parse(Reader r) { 417 GenSolvablePolynomial<C> x = ring.parse(r); 418 return new SolvableResidue<C>(this, x); 419 } 420 421}