001/* 002 * $Id$ 003 */ 004 005package edu.jas.ufd; 006 007 008import java.util.ArrayList; 009import java.util.List; 010import java.util.Map; 011import java.util.SortedMap; 012import java.util.TreeMap; 013 014import org.apache.logging.log4j.LogManager; 015import org.apache.logging.log4j.Logger; 016 017import edu.jas.gb.GroebnerBaseAbstract; 018import edu.jas.gb.GroebnerBaseSeq; 019import edu.jas.gb.Reduction; 020import edu.jas.gb.ReductionSeq; 021import edu.jas.poly.AlgebraicNumber; 022import edu.jas.poly.AlgebraicNumberRing; 023import edu.jas.poly.ExpVector; 024import edu.jas.poly.GenPolynomial; 025import edu.jas.poly.GenPolynomialRing; 026import edu.jas.poly.Monomial; 027import edu.jas.poly.PolyUtil; 028import edu.jas.structure.GcdRingElem; 029import edu.jas.structure.Power; 030import edu.jas.structure.RingFactory; 031 032 033/** 034 * Squarefree decomposition for algebraic extensions of infinite coefficient 035 * fields of characteristic p > 0. 036 * @author Heinz Kredel 037 */ 038 039public class SquarefreeInfiniteAlgebraicFieldCharP<C extends GcdRingElem<C>> 040 extends SquarefreeFieldCharP<AlgebraicNumber<C>> { 041 042 043 private static final Logger logger = LogManager.getLogger(SquarefreeInfiniteAlgebraicFieldCharP.class); 044 045 046 //private static final boolean debug = logger.isDebugEnabled(); 047 048 049 /** 050 * Squarefree engine for infinite ring of characteristic p base 051 * coefficients. 052 */ 053 protected final SquarefreeAbstract<C> aengine; 054 055 056 /** 057 * Constructor. 058 */ 059 public SquarefreeInfiniteAlgebraicFieldCharP(RingFactory<AlgebraicNumber<C>> fac) { 060 super(fac); 061 // isFinite() predicate now present 062 if (fac.isFinite()) { 063 throw new IllegalArgumentException("fac must be in-finite"); 064 } 065 AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) fac; 066 GenPolynomialRing<C> rfac = afac.ring; 067 //System.out.println("rfac = " + rfac); 068 //System.out.println("rfac = " + rfac.coFac); 069 aengine = SquarefreeFactory.<C> getImplementation(rfac); 070 //System.out.println("aengine = " + aengine); 071 } 072 073 074 /* --------- algebraic number char-th roots --------------------- */ 075 076 077 /** 078 * Squarefree factors of a AlgebraicNumber. 079 * @param P AlgebraicNumber. 080 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1, ..., k} 081 * p_i^{e_i} and p_i squarefree and gcd(p_i, p_j) = 1, for i != j. 082 */ 083 @Override 084 public SortedMap<AlgebraicNumber<C>, Long> squarefreeFactors(AlgebraicNumber<C> P) { 085 if (P == null) { 086 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 087 } 088 SortedMap<AlgebraicNumber<C>, Long> factors = new TreeMap<AlgebraicNumber<C>, Long>(); 089 if (P.isZERO()) { 090 return factors; 091 } 092 if (P.isONE()) { 093 factors.put(P, 1L); 094 return factors; 095 } 096 GenPolynomial<C> an = P.val; 097 AlgebraicNumberRing<C> pfac = P.ring; 098 if (!an.isONE()) { 099 //System.out.println("an = " + an); 100 //System.out.println("aengine = " + aengine); 101 SortedMap<GenPolynomial<C>, Long> nfac = aengine.squarefreeFactors(an); 102 //System.out.println("nfac = " + nfac); 103 for (Map.Entry<GenPolynomial<C>, Long> me : nfac.entrySet()) { 104 GenPolynomial<C> nfp = me.getKey(); 105 AlgebraicNumber<C> nf = new AlgebraicNumber<C>(pfac, nfp); 106 factors.put(nf, me.getValue()); //nfac.get(nfp)); 107 } 108 } 109 if (factors.size() == 0) { 110 factors.put(P, 1L); 111 } 112 return factors; 113 } 114 115 116 /** 117 * Characteristics root of a AlgebraicNumber. 118 * @param P AlgebraicNumber. 119 * @return [p -> k] if exists k with e=characteristic(P)*k and P = p**e, 120 * else null. 121 */ 122 @SuppressWarnings("unchecked") 123 public SortedMap<AlgebraicNumber<C>, Long> rootCharacteristic(AlgebraicNumber<C> P) { 124 if (P == null) { 125 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 126 } 127 java.math.BigInteger c = P.ring.characteristic(); 128 if (c.signum() == 0) { 129 return null; 130 } 131 SortedMap<AlgebraicNumber<C>, Long> root = new TreeMap<AlgebraicNumber<C>, Long>(); 132 if (P.isZERO()) { 133 return root; 134 } 135 if (P.isONE()) { 136 root.put(P, 1L); 137 return root; 138 } 139 // generate system of equations 140 AlgebraicNumberRing<C> afac = P.ring; 141 long deg = afac.modul.degree(0); 142 int d = (int) deg; 143 String[] vn = GenPolynomialRing.newVars("c", d); 144 GenPolynomialRing<AlgebraicNumber<C>> pfac = new GenPolynomialRing<AlgebraicNumber<C>>(afac, d, vn); 145 List<GenPolynomial<AlgebraicNumber<C>>> uv = (List<GenPolynomial<AlgebraicNumber<C>>>) pfac 146 .univariateList(); 147 GenPolynomial<AlgebraicNumber<C>> cp = pfac.getZERO(); 148 GenPolynomialRing<C> apfac = afac.ring; 149 long i = 0; 150 for (GenPolynomial<AlgebraicNumber<C>> pa : uv) { 151 GenPolynomial<C> ca = apfac.univariate(0, i++); 152 GenPolynomial<AlgebraicNumber<C>> pb = pa.multiply(new AlgebraicNumber<C>(afac, ca)); 153 cp = cp.sum(pb); 154 } 155 GenPolynomial<AlgebraicNumber<C>> cpp = Power.<GenPolynomial<AlgebraicNumber<C>>> positivePower(cp, 156 c); 157 if (logger.isInfoEnabled()) { 158 logger.info("cp = {}", cp); 159 logger.info("cp^p = {}", cpp); 160 logger.info("P = {}", P); 161 } 162 GenPolynomialRing<C> ppfac = new GenPolynomialRing<C>(apfac.coFac, pfac); 163 List<GenPolynomial<C>> gl = new ArrayList<GenPolynomial<C>>(); 164 if (deg == c.longValueExact() && afac.modul.length() == 2) { 165 logger.info("deg({}) == char_p({})", deg, c.longValueExact()); 166 for (Monomial<AlgebraicNumber<C>> m : cpp) { 167 ExpVector f = m.e; 168 AlgebraicNumber<C> a = m.c; 169 //System.out.println("a = " + a + " : " + a.toScriptFactory()); 170 GenPolynomial<C> ap = a.val; 171 for (Monomial<C> ma : ap) { 172 ExpVector e = ma.e; 173 C cc = ma.c; 174 C pc = P.val.coefficient(e); 175 C cc1 = ((RingFactory<C>) pc.factory()).getONE(); 176 C pc1 = ((RingFactory<C>) pc.factory()).getZERO(); 177 //System.out.println("cc = " + cc + ", e = " + e); 178 //System.out.println("pc = " + pc + " : " + cc.toScriptFactory()); 179 if (cc instanceof AlgebraicNumber && pc instanceof AlgebraicNumber) { 180 throw new UnsupportedOperationException( 181 "case multiple algebraic extensions not implemented"); 182 } else if (cc instanceof Quotient && pc instanceof Quotient) { 183 Quotient<C> ccp = (Quotient<C>) (Object) cc; 184 Quotient<C> pcp = (Quotient<C>) (Object) pc; 185 if (pcp.isConstant()) { 186 //logger.error("finite field not allowed here {}", afac.toScript()); 187 throw new ArithmeticException("finite field not allowed here " + afac.toScript()); 188 } 189 //C dc = cc.divide(pc); 190 Quotient<C> dcp = ccp.divide(pcp); 191 if (dcp.isConstant()) { // not possible: dc.isConstant() 192 //System.out.println("dcp = " + dcp + " : " + cc.toScriptFactory()); // + ", dc = " + dc); 193 //if ( dcp.num.isConstant() ) 194 cc1 = cc; 195 pc1 = pc; 196 } 197 GenPolynomial<C> r = new GenPolynomial<C>(ppfac, cc1, f); 198 r = r.subtract(pc1); 199 //System.out.println("r = " + r); 200 gl.add(r); 201 } 202 } 203 } 204 } else { 205 for (Monomial<AlgebraicNumber<C>> m : cpp) { 206 ExpVector f = m.e; 207 AlgebraicNumber<C> a = m.c; 208 //System.out.println("m = " + m); 209 GenPolynomial<C> ap = a.val; 210 for (Monomial<C> ma : ap) { 211 ExpVector e = ma.e; 212 C cc = ma.c; 213 C pc = P.val.coefficient(e); 214 GenPolynomial<C> r = new GenPolynomial<C>(ppfac, cc, f); 215 r = r.subtract(pc); 216 //System.out.println("r = " + r); 217 gl.add(r); 218 } 219 } 220 } 221 logger.info("equations = {}", gl); 222 // solve system of equations and construct result 223 Reduction<C> red = new ReductionSeq<C>(); 224 gl = red.irreducibleSet(gl); 225 GroebnerBaseAbstract<C> bb = new GroebnerBaseSeq<C>(); //GBFactory.<C>getImplementation(); 226 int z = bb.commonZeroTest(gl); 227 if (z < 0) { // no solution 228 return null; 229 } 230 logger.info("solution = {}", gl); 231 GenPolynomial<C> car = apfac.getZERO(); 232 for (GenPolynomial<C> pl : gl) { 233 if (pl.length() <= 1) { 234 continue; 235 } 236 if (pl.length() > 2) { 237 throw new IllegalArgumentException("dim > 0 not implemented " + pl); 238 } 239 //System.out.println("pl = " + pl); 240 ExpVector e = pl.leadingExpVector(); 241 int[] v = e.dependencyOnVariables(); 242 if (v == null || v.length == 0) { 243 continue; 244 } 245 int vi = v[0]; 246 //System.out.println("vi = " + vi); 247 GenPolynomial<C> ca = apfac.univariate(0, deg - 1 - vi); 248 //System.out.println("ca = " + ca); 249 C tc = pl.trailingBaseCoefficient(); 250 tc = tc.negate(); 251 if (e.maxDeg() == c.longValueExact()) { // p-th root of tc ... 252 //SortedMap<C, Long> br = aengine.rootCharacteristic(tc); 253 SortedMap<C, Long> br = aengine.squarefreeFactors(tc); 254 //System.out.println("br = " + br); 255 if (br != null && br.size() > 0) { 256 C cc = apfac.coFac.getONE(); 257 for (Map.Entry<C, Long> me : br.entrySet()) { 258 C bc = me.getKey(); 259 long ll = me.getValue(); 260 if (ll % c.longValueExact() == 0L) { 261 long fl = ll / c.longValueExact(); 262 cc = cc.multiply(bc.power(fl)); 263 } else { // fail ? 264 cc = cc.multiply(bc); 265 } 266 } 267 //System.out.println("cc = " + cc); 268 tc = cc; 269 } 270 } 271 ca = ca.multiply(tc); 272 car = car.sum(ca); 273 } 274 AlgebraicNumber<C> rr = new AlgebraicNumber<C>(afac, car); 275 if (logger.isInfoEnabled()) { 276 logger.info("solution AN = {}", rr); 277 //System.out.println("rr = " + rr); 278 } 279 root.put(rr, 1L); 280 return root; 281 } 282 283 284 /** 285 * GenPolynomial char-th root main variable. 286 * @param P univariate GenPolynomial with AlgebraicNumber coefficients. 287 * @return char-th_rootOf(P), or null, if P is no char-th root. 288 */ 289 public GenPolynomial<AlgebraicNumber<C>> rootCharacteristic(GenPolynomial<AlgebraicNumber<C>> P) { 290 if (P == null || P.isZERO()) { 291 return P; 292 } 293 GenPolynomialRing<AlgebraicNumber<C>> pfac = P.ring; 294 if (pfac.nvar > 1) { 295 // go to recursion 296 GenPolynomialRing<GenPolynomial<AlgebraicNumber<C>>> rfac = pfac.recursive(1); 297 GenPolynomial<GenPolynomial<AlgebraicNumber<C>>> Pr = PolyUtil 298 .<AlgebraicNumber<C>> recursive(rfac, P); 299 GenPolynomial<GenPolynomial<AlgebraicNumber<C>>> Prc = recursiveUnivariateRootCharacteristic(Pr); 300 if (Prc == null) { 301 return null; 302 } 303 GenPolynomial<AlgebraicNumber<C>> D = PolyUtil.<AlgebraicNumber<C>> distribute(pfac, Prc); 304 return D; 305 } 306 RingFactory<AlgebraicNumber<C>> rf = pfac.coFac; 307 if (rf.characteristic().signum() != 1) { 308 // basePthRoot not possible 309 throw new IllegalArgumentException( 310 P.getClass().getName() + " only for ModInteger polynomials " + rf); 311 } 312 long mp = rf.characteristic().longValueExact(); 313 GenPolynomial<AlgebraicNumber<C>> d = pfac.getZERO().copy(); 314 for (Monomial<AlgebraicNumber<C>> m : P) { 315 ExpVector f = m.e; 316 long fl = f.getVal(0); 317 if (fl % mp != 0) { 318 return null; 319 } 320 fl = fl / mp; 321 SortedMap<AlgebraicNumber<C>, Long> sm = rootCharacteristic(m.c); 322 if (sm == null) { 323 return null; 324 } 325 logger.info("sm_alg,root = {}", sm); 326 AlgebraicNumber<C> r = rf.getONE(); 327 for (Map.Entry<AlgebraicNumber<C>, Long> me : sm.entrySet()) { 328 AlgebraicNumber<C> rp = me.getKey(); 329 long gl = me.getValue(); 330 if (gl > 1) { 331 rp = rp.power(gl); 332 } 333 r = r.multiply(rp); 334 } 335 ExpVector e = ExpVector.create(1, 0, fl); 336 d.doPutToMap(e, r); 337 } 338 logger.info("sm_alg,root,d = {}", d); 339 return d; 340 } 341 342 343 /** 344 * GenPolynomial char-th root univariate polynomial. 345 * @param P GenPolynomial. 346 * @return char-th_rootOf(P). 347 */ 348 @Override 349 public GenPolynomial<AlgebraicNumber<C>> baseRootCharacteristic(GenPolynomial<AlgebraicNumber<C>> P) { 350 if (P == null || P.isZERO()) { 351 return P; 352 } 353 GenPolynomialRing<AlgebraicNumber<C>> pfac = P.ring; 354 if (pfac.nvar > 1) { 355 // basePthRoot not possible by return type 356 throw new IllegalArgumentException(P.getClass().getName() + " only for univariate polynomials"); 357 } 358 RingFactory<AlgebraicNumber<C>> rf = pfac.coFac; 359 if (rf.characteristic().signum() != 1) { 360 // basePthRoot not possible 361 throw new IllegalArgumentException(P.getClass().getName() + " only for char p > 0 " + rf); 362 } 363 long mp = rf.characteristic().longValueExact(); 364 GenPolynomial<AlgebraicNumber<C>> d = pfac.getZERO().copy(); 365 for (Monomial<AlgebraicNumber<C>> m : P) { 366 //System.out.println("m = " + m); 367 ExpVector f = m.e; 368 long fl = f.getVal(0); 369 if (fl % mp != 0) { 370 return null; 371 } 372 fl = fl / mp; 373 SortedMap<AlgebraicNumber<C>, Long> sm = rootCharacteristic(m.c); 374 if (sm == null) { 375 return null; 376 } 377 logger.info("sm_alg,base,root = {}", sm); 378 AlgebraicNumber<C> r = rf.getONE(); 379 for (Map.Entry<AlgebraicNumber<C>, Long> me : sm.entrySet()) { 380 AlgebraicNumber<C> rp = me.getKey(); 381 //System.out.println("rp = " + rp); 382 long gl = me.getValue(); 383 //System.out.println("gl = " + gl); 384 AlgebraicNumber<C> re = rp; 385 if (gl > 1) { 386 re = rp.power(gl); 387 } 388 //System.out.println("re = " + re); 389 r = r.multiply(re); 390 } 391 ExpVector e = ExpVector.create(1, 0, fl); 392 d.doPutToMap(e, r); 393 } 394 logger.info("sm_alg,base,d = {}", d); 395 return d; 396 } 397 398 399 /** 400 * GenPolynomial char-th root univariate polynomial with polynomial 401 * coefficients. 402 * @param P recursive univariate GenPolynomial. 403 * @return char-th_rootOf(P), or null if P is no char-th root. 404 */ 405 @Override 406 public GenPolynomial<GenPolynomial<AlgebraicNumber<C>>> recursiveUnivariateRootCharacteristic( 407 GenPolynomial<GenPolynomial<AlgebraicNumber<C>>> P) { 408 if (P == null || P.isZERO()) { 409 return P; 410 } 411 GenPolynomialRing<GenPolynomial<AlgebraicNumber<C>>> pfac = P.ring; 412 if (pfac.nvar > 1) { 413 // basePthRoot not possible by return type 414 throw new IllegalArgumentException( 415 P.getClass().getName() + " only for univariate recursive polynomials"); 416 } 417 RingFactory<GenPolynomial<AlgebraicNumber<C>>> rf = pfac.coFac; 418 if (rf.characteristic().signum() != 1) { 419 // basePthRoot not possible 420 throw new IllegalArgumentException(P.getClass().getName() + " only for char p > 0 " + rf); 421 } 422 long mp = rf.characteristic().longValueExact(); 423 GenPolynomial<GenPolynomial<AlgebraicNumber<C>>> d = pfac.getZERO().copy(); 424 for (Monomial<GenPolynomial<AlgebraicNumber<C>>> m : P) { 425 ExpVector f = m.e; 426 long fl = f.getVal(0); 427 if (fl % mp != 0) { 428 return null; 429 } 430 fl = fl / mp; 431 GenPolynomial<AlgebraicNumber<C>> r = rootCharacteristic(m.c); 432 if (r == null) { 433 return null; 434 } 435 ExpVector e = ExpVector.create(1, 0, fl); 436 d.doPutToMap(e, r); 437 } 438 return d; 439 } 440 441}