001/* 002 * $Id$ 003 */ 004 005package edu.jas.ufd; 006 007 008import java.util.Map; 009import java.util.SortedMap; 010import java.util.TreeMap; 011 012import org.apache.logging.log4j.LogManager; 013import org.apache.logging.log4j.Logger; 014 015import edu.jas.poly.AlgebraicNumber; 016import edu.jas.poly.AlgebraicNumberRing; 017import edu.jas.poly.ExpVector; 018import edu.jas.poly.GenPolynomial; 019import edu.jas.poly.GenPolynomialRing; 020import edu.jas.poly.PolyUtil; 021import edu.jas.structure.GcdRingElem; 022import edu.jas.structure.RingFactory; 023 024 025/** 026 * Squarefree decomposition for coefficient fields of characteristic p. 027 * @author Heinz Kredel 028 */ 029 030public abstract class SquarefreeFieldCharP<C extends GcdRingElem<C>> extends SquarefreeAbstract<C> { 031 032 033 private static final Logger logger = LogManager.getLogger(SquarefreeFieldCharP.class); 034 035 036 //private static final boolean debug = logger.isDebugEnabled(); 037 038 039 /* 040 * Squarefree engine for characteristic p base coefficients. 041 */ 042 //protected final SquarefreeAbstract<C> rengine; 043 044 045 /** 046 * Factory for finite field of characteristic p coefficients. 047 */ 048 protected final RingFactory<C> coFac; 049 050 051 /** 052 * Factory for a algebraic extension of a finite field of characteristic p 053 * coefficients. If <code>coFac</code> is an algebraic extension, then 054 * <code>aCoFac</code> is equal to <code>coFac</code>, else 055 * <code>aCoFac</code> is <code>null</code>. 056 */ 057 protected final AlgebraicNumberRing<C> aCoFac; 058 059 060 /** 061 * Factory for a transcendental extension of a finite field of 062 * characteristic p coefficients. If <code>coFac</code> is an transcendental 063 * extension, then <code>qCoFac</code> is equal to <code>coFac</code>, else 064 * <code>qCoFac</code> is <code>null</code>. 065 */ 066 protected final QuotientRing<C> qCoFac; 067 068 069 /** 070 * Constructor. 071 */ 072 @SuppressWarnings("unchecked") 073 public SquarefreeFieldCharP(RingFactory<C> fac) { 074 super(GCDFactory.<C> getProxy(fac)); 075 if (!fac.isField()) { 076 //throw new IllegalArgumentException("fac must be a field: " + fac.toScript()); 077 logger.warn("fac should be a field: {}", fac.toScript()); 078 } 079 if (fac.characteristic().signum() == 0) { 080 throw new IllegalArgumentException("characteristic(fac) must be non-zero"); 081 } 082 coFac = fac; 083 Object oFac = coFac; 084 if (oFac instanceof AlgebraicNumberRing) { 085 aCoFac = (AlgebraicNumberRing<C>) oFac; // <C> is not correct 086 //rengine = (SquarefreeAbstract) SquarefreeFactory.getImplementation(aCoFac.ring); 087 qCoFac = null; 088 } else { 089 aCoFac = null; 090 if (oFac instanceof QuotientRing) { 091 qCoFac = (QuotientRing<C>) oFac; // <C> is not correct 092 //rengine = (SquarefreeAbstract) SquarefreeFactory.getImplementation(qCoFac.ring); 093 } else { 094 qCoFac = null; 095 } 096 } 097 } 098 099 100 /** 101 * Get the String representation. 102 * @see java.lang.Object#toString() 103 */ 104 @Override 105 public String toString() { 106 return getClass().getName() + " with " + engine + " over " + coFac; 107 } 108 109 110 /** 111 * GenPolynomial polynomial greatest squarefree divisor. 112 * @param P GenPolynomial. 113 * @return squarefree(pp(P)). 114 */ 115 @Override 116 public GenPolynomial<C> baseSquarefreePart(GenPolynomial<C> P) { 117 if (P == null || P.isZERO()) { 118 return P; 119 } 120 GenPolynomialRing<C> pfac = P.ring; 121 if (pfac.nvar > 1) { 122 throw new IllegalArgumentException( 123 this.getClass().getName() + " only for univariate polynomials"); 124 } 125 GenPolynomial<C> s = pfac.getONE(); 126 SortedMap<GenPolynomial<C>, Long> factors = baseSquarefreeFactors(P); 127 //if (logger.isWarnEnabled()) { 128 // logger.warn("sqfPart, better use sqfFactors, factors = {}", factors); 129 //} 130 for (GenPolynomial<C> sp : factors.keySet()) { 131 s = s.multiply(sp); 132 } 133 s = s.monic(); 134 return s; 135 } 136 137 138 /** 139 * GenPolynomial polynomial squarefree factorization. 140 * @param A GenPolynomial. 141 * @return [p_1 -> e_1, ..., p_k -> e_k] with A = prod_{i=1,...,k} 142 * p_i^{e_i} and p_i squarefree and gcd(p_i, p_j) = 1, for i != j. 143 */ 144 @Override 145 public SortedMap<GenPolynomial<C>, Long> baseSquarefreeFactors(GenPolynomial<C> A) { 146 SortedMap<GenPolynomial<C>, Long> sfactors = new TreeMap<GenPolynomial<C>, Long>(); 147 if (A == null || A.isZERO()) { 148 return sfactors; 149 } 150 GenPolynomialRing<C> pfac = A.ring; 151 if (A.isConstant()) { 152 C coeff = A.leadingBaseCoefficient(); 153 //System.out.println("coeff = " + coeff + " @ " + coeff.factory()); 154 SortedMap<C, Long> rfactors = squarefreeFactors(coeff); 155 //System.out.println("rfactors,const = " + rfactors); 156 if (rfactors != null && rfactors.size() > 0) { 157 for (Map.Entry<C, Long> me : rfactors.entrySet()) { 158 C c = me.getKey(); 159 if (!c.isONE()) { 160 GenPolynomial<C> cr = pfac.getONE().multiply(c); 161 Long rk = me.getValue(); // rfactors.get(c); 162 sfactors.put(cr, rk); 163 } 164 } 165 } 166 if (sfactors.isEmpty()) { 167 sfactors.put(A, 1L); 168 } 169 return sfactors; 170 } 171 if (pfac.nvar > 1) { 172 throw new IllegalArgumentException( 173 this.getClass().getName() + " only for univariate polynomials"); 174 } 175 C ldbcf = A.leadingBaseCoefficient(); 176 if (!ldbcf.isONE()) { 177 A = A.divide(ldbcf); 178 SortedMap<C, Long> rfactors = squarefreeFactors(ldbcf); 179 //System.out.println("rfactors,ldbcf = " + rfactors); 180 if (rfactors != null && rfactors.size() > 0) { 181 for (Map.Entry<C, Long> me : rfactors.entrySet()) { 182 C c = me.getKey(); 183 if (!c.isONE()) { 184 GenPolynomial<C> cr = pfac.getONE().multiply(c); 185 Long rk = me.getValue(); //rfactors.get(c); 186 sfactors.put(cr, rk); 187 } 188 } 189 } else { 190 GenPolynomial<C> f1 = pfac.getONE().multiply(ldbcf); 191 //System.out.println("gcda sqf f1 = " + f1); 192 sfactors.put(f1, 1L); 193 } 194 ldbcf = pfac.coFac.getONE(); 195 } 196 // divide by trailing term 197 ExpVector et = A.trailingExpVector(); 198 if (!et.isZERO()) { 199 GenPolynomial<C> tr = pfac.valueOf(et); 200 logger.info("trailing term = {}", tr); 201 A = PolyUtil.<C> basePseudoDivide(A, tr); 202 long ep = et.getVal(0); // univariate 203 et = et.subst(0, 1); 204 tr = pfac.valueOf(et); 205 logger.info("tr, ep = {}, {}", tr, ep); 206 sfactors.put(tr, ep); 207 if (A.length() == 1) { 208 return sfactors; 209 } 210 } 211 GenPolynomial<C> T0 = A; 212 long e = 1L; 213 GenPolynomial<C> Tp; 214 GenPolynomial<C> T = null; 215 GenPolynomial<C> V = null; 216 long k = 0L; 217 long mp = 0L; 218 boolean init = true; 219 while (true) { 220 //System.out.println("T0 = " + T0); 221 if (init) { 222 if (T0.isConstant() || T0.isZERO()) { 223 break; 224 } 225 Tp = PolyUtil.<C> baseDerivative(T0); 226 T = engine.baseGcd(T0, Tp); 227 T = T.monic(); 228 V = PolyUtil.<C> basePseudoDivide(T0, T); 229 //System.out.println("iT0 = " + T0); 230 //System.out.println("iTp = " + Tp); 231 //System.out.println("iT = " + T); 232 //System.out.println("iV = " + V); 233 //System.out.println("const(iV) = " + V.isConstant()); 234 k = 0L; 235 mp = 0L; 236 init = false; 237 } 238 if (V.isConstant()) { 239 mp = pfac.characteristic().longValueExact(); // assert != 0 240 //T0 = PolyUtil.<C> baseModRoot(T,mp); 241 T0 = baseRootCharacteristic(T); 242 logger.info("char root: T0 = {}, T = {}", T0, T); 243 if (T0 == null) { 244 //break; 245 T0 = pfac.getZERO(); 246 } 247 e = e * mp; 248 init = true; 249 continue; 250 } 251 k++; 252 if (mp != 0L && k % mp == 0L) { 253 T = PolyUtil.<C> basePseudoDivide(T, V); 254 System.out.println("k = " + k); 255 //System.out.println("T = " + T); 256 k++; 257 } 258 GenPolynomial<C> W = engine.baseGcd(T, V); 259 W = W.monic(); 260 GenPolynomial<C> z = PolyUtil.<C> basePseudoDivide(V, W); 261 //System.out.println("W = " + W); 262 //System.out.println("z = " + z); 263 V = W; 264 T = PolyUtil.<C> basePseudoDivide(T, V); 265 //System.out.println("V = " + V); 266 //System.out.println("T = " + T); 267 if (z.degree(0) > 0) { 268 if (ldbcf.isONE() && !z.leadingBaseCoefficient().isONE()) { 269 z = z.monic(); 270 //logger.info("z,monic = {}", z); 271 } 272 logger.info("z, k = {}, {}", z, k); 273 sfactors.put(z, (e * k)); 274 } 275 } 276 logger.info("exit char root: T0 = {}, T = {}", T0, T); 277 return sfactors; 278 } 279 280 281 /** 282 * GenPolynomial recursive univariate polynomial greatest squarefree 283 * divisor. 284 * @param P recursive univariate GenPolynomial. 285 * @return squarefree(pp(P)). 286 */ 287 @Override 288 public GenPolynomial<GenPolynomial<C>> recursiveUnivariateSquarefreePart( 289 GenPolynomial<GenPolynomial<C>> P) { 290 if (P == null || P.isZERO()) { 291 return P; 292 } 293 GenPolynomialRing<GenPolynomial<C>> pfac = P.ring; 294 if (pfac.nvar > 1) { 295 throw new IllegalArgumentException( 296 this.getClass().getName() + " only for univariate polynomials"); 297 } 298 GenPolynomial<GenPolynomial<C>> s = pfac.getONE(); 299 SortedMap<GenPolynomial<GenPolynomial<C>>, Long> factors = recursiveUnivariateSquarefreeFactors(P); 300 if (logger.isWarnEnabled()) { 301 logger.info("sqfPart, better use sqfFactors, factors = {}", factors); 302 } 303 for (GenPolynomial<GenPolynomial<C>> sp : factors.keySet()) { 304 s = s.multiply(sp); 305 } 306 s = PolyUtil.<C> monic(s); 307 return s; 308 } 309 310 311 /** 312 * GenPolynomial recursive univariate polynomial squarefree factorization. 313 * @param P recursive univariate GenPolynomial. 314 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} 315 * p_i^{e_i} and p_i squarefree and gcd(p_i, p_j) = 1, for i != j. 316 */ 317 @Override 318 public SortedMap<GenPolynomial<GenPolynomial<C>>, Long> recursiveUnivariateSquarefreeFactors( 319 GenPolynomial<GenPolynomial<C>> P) { 320 SortedMap<GenPolynomial<GenPolynomial<C>>, Long> sfactors = new TreeMap<GenPolynomial<GenPolynomial<C>>, Long>(); 321 if (P == null || P.isZERO()) { 322 return sfactors; 323 } 324 GenPolynomialRing<GenPolynomial<C>> pfac = P.ring; 325 if (pfac.nvar > 1) { 326 // recursiveContent not possible by return type 327 throw new IllegalArgumentException( 328 this.getClass().getName() + " only for univariate polynomials"); 329 } 330 // if base coefficient ring is a field, make monic 331 GenPolynomialRing<C> cfac = (GenPolynomialRing<C>) pfac.coFac; 332 C ldbcf = P.leadingBaseCoefficient().leadingBaseCoefficient(); 333 if (!ldbcf.isONE()) { 334 GenPolynomial<C> lc = cfac.getONE().multiply(ldbcf); 335 GenPolynomial<GenPolynomial<C>> pl = pfac.getONE().multiply(lc); 336 sfactors.put(pl, 1L); 337 C li = ldbcf.inverse(); 338 //System.out.println("li = " + li); 339 P = P.multiply(cfac.getONE().multiply(li)); 340 //System.out.println("P,monic = " + P); 341 ldbcf = P.leadingBaseCoefficient().leadingBaseCoefficient(); 342 logger.debug("new ldbcf: {}", ldbcf); 343 } 344 // factors of content 345 GenPolynomial<C> Pc = engine.recursiveContent(P); 346 logger.info("Pc = {}", Pc); 347 Pc = Pc.monic(); 348 if (!Pc.isONE()) { 349 P = PolyUtil.<C> coefficientPseudoDivide(P, Pc); 350 } 351 SortedMap<GenPolynomial<C>, Long> rsf = squarefreeFactors(Pc); 352 logger.info("rsf = {}", rsf); 353 // add factors of content 354 for (Map.Entry<GenPolynomial<C>, Long> me : rsf.entrySet()) { 355 GenPolynomial<C> c = me.getKey(); 356 if (!c.isONE()) { 357 GenPolynomial<GenPolynomial<C>> cr = pfac.getONE().multiply(c); 358 Long rk = me.getValue(); //rsf.get(c); 359 sfactors.put(cr, rk); 360 } 361 } 362 // divide by trailing term 363 ExpVector et = P.trailingExpVector(); 364 if (!et.isZERO()) { 365 GenPolynomial<GenPolynomial<C>> tr = pfac.valueOf(et); 366 logger.info("trailing term = {}", tr); 367 P = PolyUtil.<C> recursivePseudoDivide(P, tr); 368 long ep = et.getVal(0); // univariate 369 et = et.subst(0, 1); 370 tr = pfac.valueOf(et); 371 sfactors.put(tr, ep); 372 } 373 374 // factors of recursive polynomial 375 GenPolynomial<GenPolynomial<C>> T0 = P; 376 long e = 1L; 377 GenPolynomial<GenPolynomial<C>> Tp; 378 GenPolynomial<GenPolynomial<C>> T = null; 379 GenPolynomial<GenPolynomial<C>> V = null; 380 long k = 0L; 381 long mp = 0L; 382 boolean init = true; 383 while (true) { 384 if (init) { 385 if (T0.isConstant() || T0.isZERO()) { 386 break; 387 } 388 Tp = PolyUtil.<C> recursiveDerivative(T0); 389 //System.out.println("iT0 = " + T0); 390 //System.out.println("iTp = " + Tp); 391 T = engine.recursiveUnivariateGcd(T0, Tp); 392 T = PolyUtil.<C> monic(T); 393 V = PolyUtil.<C> recursivePseudoDivide(T0, T); 394 //System.out.println("iT = " + T); 395 //System.out.println("iV = " + V); 396 k = 0L; 397 mp = 0L; 398 init = false; 399 } 400 if (V.isConstant()) { 401 mp = pfac.characteristic().longValueExact(); // assert != 0 402 //T0 = PolyUtil.<C> recursiveModRoot(T,mp); 403 T0 = recursiveUnivariateRootCharacteristic(T); 404 logger.info("char root: T0r = {}, Tr = {}", T0, T); 405 if (T0 == null) { 406 //break; 407 T0 = pfac.getZERO(); 408 } 409 e = e * mp; 410 init = true; 411 //continue; 412 } 413 k++; 414 if (mp != 0L && k % mp == 0L) { 415 T = PolyUtil.<C> recursivePseudoDivide(T, V); 416 System.out.println("k = " + k); 417 //System.out.println("T = " + T); 418 k++; 419 } 420 GenPolynomial<GenPolynomial<C>> W = engine.recursiveUnivariateGcd(T, V); 421 W = PolyUtil.<C> monic(W); 422 GenPolynomial<GenPolynomial<C>> z = PolyUtil.<C> recursivePseudoDivide(V, W); 423 //System.out.println("W = " + W); 424 //System.out.println("z = " + z); 425 V = W; 426 T = PolyUtil.<C> recursivePseudoDivide(T, V); 427 //System.out.println("V = " + V); 428 //System.out.println("T = " + T); 429 //was: if ( z.degree(0) > 0 ) { 430 if (!z.isONE() && !z.isZERO()) { 431 z = PolyUtil.<C> monic(z); 432 logger.info("z,put = {}", z); 433 sfactors.put(z, (e * k)); 434 } 435 } 436 logger.info("exit char root: T0 = {}, T = {}", T0, T); 437 if (sfactors.size() == 0) { 438 sfactors.put(pfac.getONE(), 1L); 439 } 440 return sfactors; 441 } 442 443 444 /** 445 * GenPolynomial greatest squarefree divisor. 446 * @param P GenPolynomial. 447 * @return squarefree(pp(P)). 448 */ 449 @Override 450 public GenPolynomial<C> squarefreePart(GenPolynomial<C> P) { 451 if (P == null) { 452 throw new IllegalArgumentException(this.getClass().getName() + " P != null"); 453 } 454 if (P.isZERO()) { 455 return P; 456 } 457 GenPolynomialRing<C> pfac = P.ring; 458 if (pfac.nvar <= 1) { 459 return baseSquarefreePart(P); 460 } 461 GenPolynomial<C> s = pfac.getONE(); 462 SortedMap<GenPolynomial<C>, Long> factors = squarefreeFactors(P); 463 if (logger.isWarnEnabled()) { 464 logger.info("sqfPart, better use sqfFactors, factors = {}", factors); 465 } 466 for (GenPolynomial<C> sp : factors.keySet()) { 467 if (sp.isConstant()) { 468 continue; 469 } 470 s = s.multiply(sp); 471 } 472 return s.monic(); 473 } 474 475 476 /** 477 * GenPolynomial squarefree factorization. 478 * @param P GenPolynomial. 479 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1,...,k} 480 * p_i^{e_i} and p_i squarefree and gcd(p_i, p_j) = 1, for i != j. 481 */ 482 @Override 483 public SortedMap<GenPolynomial<C>, Long> squarefreeFactors(GenPolynomial<C> P) { 484 if (P == null) { 485 throw new IllegalArgumentException(this.getClass().getName() + " P != null"); 486 } 487 GenPolynomialRing<C> pfac = P.ring; 488 if (pfac.nvar <= 1) { 489 return baseSquarefreeFactors(P); 490 } 491 SortedMap<GenPolynomial<C>, Long> sfactors = new TreeMap<GenPolynomial<C>, Long>(); 492 if (P.isZERO()) { 493 return sfactors; 494 } 495 if (P.isONE()) { 496 sfactors.put(P, 1L); 497 return sfactors; 498 } 499 GenPolynomialRing<GenPolynomial<C>> rfac = pfac.recursive(1); 500 GenPolynomial<GenPolynomial<C>> Pr = PolyUtil.<C> recursive(rfac, P); 501 SortedMap<GenPolynomial<GenPolynomial<C>>, Long> PP = recursiveUnivariateSquarefreeFactors(Pr); 502 for (Map.Entry<GenPolynomial<GenPolynomial<C>>, Long> m : PP.entrySet()) { 503 Long i = m.getValue(); 504 GenPolynomial<GenPolynomial<C>> Dr = m.getKey(); 505 GenPolynomial<C> D = PolyUtil.<C> distribute(pfac, Dr); 506 sfactors.put(D, i); 507 } 508 return sfactors; 509 } 510 511 512 /** 513 * Coefficient squarefree factorization. 514 * @param coeff coefficient. 515 * @return [p_1 -> e_1, ..., p_k -> e_k] with coeff = prod_{i=1,...,k} 516 * p_i^{e_i} and p_i squarefree and gcd(p_i, p_j) = 1, for i != j. 517 */ 518 @SuppressWarnings("unchecked") 519 @Override 520 public SortedMap<C, Long> squarefreeFactors(C coeff) { 521 if (coeff == null) { 522 return null; 523 } 524 SortedMap<C, Long> factors = new TreeMap<C, Long>(); 525 RingFactory<C> cfac = (RingFactory<C>) coeff.factory(); 526 if (aCoFac != null) { 527 AlgebraicNumber<C> an = (AlgebraicNumber<C>) (Object) coeff; 528 if (cfac.isFinite()) { 529 SquarefreeFiniteFieldCharP<C> reng = (SquarefreeFiniteFieldCharP) SquarefreeFactory 530 .getImplementation(cfac); 531 SortedMap<C, Long> rfactors = reng.rootCharacteristic(coeff); // ?? 532 logger.info("rfactors,finite = {}", rfactors); 533 factors.putAll(rfactors); 534 //return factors; 535 } else { 536 SquarefreeInfiniteAlgebraicFieldCharP<C> reng = (SquarefreeInfiniteAlgebraicFieldCharP) SquarefreeFactory 537 .getImplementation(cfac); 538 SortedMap<AlgebraicNumber<C>, Long> rfactors = reng.squarefreeFactors(an); 539 logger.info("rfactors,infinite,algeb = {}", rfactors); 540 for (Map.Entry<AlgebraicNumber<C>, Long> me : rfactors.entrySet()) { 541 AlgebraicNumber<C> c = me.getKey(); 542 if (!c.isONE()) { 543 C cr = (C) (Object) c; 544 Long rk = me.getValue(); 545 factors.put(cr, rk); 546 } 547 } 548 } 549 } else if (qCoFac != null) { 550 Quotient<C> q = (Quotient<C>) (Object) coeff; 551 SquarefreeInfiniteFieldCharP<C> reng = (SquarefreeInfiniteFieldCharP) SquarefreeFactory 552 .getImplementation(cfac); 553 SortedMap<Quotient<C>, Long> rfactors = reng.squarefreeFactors(q); 554 logger.info("rfactors,infinite = {}", rfactors); 555 for (Map.Entry<Quotient<C>, Long> me : rfactors.entrySet()) { 556 Quotient<C> c = me.getKey(); 557 if (!c.isONE()) { 558 C cr = (C) (Object) c; 559 Long rk = me.getValue(); 560 factors.put(cr, rk); 561 } 562 } 563 } else if (cfac.isFinite()) { 564 SquarefreeFiniteFieldCharP<C> reng = (SquarefreeFiniteFieldCharP) SquarefreeFactory 565 .getImplementation(cfac); 566 SortedMap<C, Long> rfactors = reng.rootCharacteristic(coeff); // ?? 567 logger.info("rfactors,finite = {}", rfactors); 568 factors.putAll(rfactors); 569 //return factors; 570 } else { 571 logger.warn("case {} not implemented", cfac); 572 } 573 return factors; 574 } 575 576 577 /* --------- char-th roots --------------------- */ 578 579 580 /** 581 * GenPolynomial char-th root univariate polynomial. 582 * @param P GenPolynomial. 583 * @return char-th_rootOf(P), or null if no char-th root. 584 */ 585 public abstract GenPolynomial<C> baseRootCharacteristic(GenPolynomial<C> P); 586 587 588 /** 589 * GenPolynomial char-th root univariate polynomial with polynomial 590 * coefficients. 591 * @param P recursive univariate GenPolynomial. 592 * @return char-th_rootOf(P), or null if P is no char-th root. 593 */ 594 public abstract GenPolynomial<GenPolynomial<C>> recursiveUnivariateRootCharacteristic( 595 GenPolynomial<GenPolynomial<C>> P); 596 597 598 /** 599 * Polynomial is char-th root. 600 * @param P polynomial. 601 * @param F = [p_1 -> e_1, ..., p_k -> e_k]. 602 * @return true if P = prod_{i=1,...,k} p_i**(e_i*p), else false. 603 */ 604 public boolean isCharRoot(GenPolynomial<C> P, SortedMap<GenPolynomial<C>, Long> F) { 605 if (P == null || F == null) { 606 throw new IllegalArgumentException("P and F may not be null"); 607 } 608 if (P.isZERO() && F.size() == 0) { 609 return true; 610 } 611 GenPolynomial<C> t = P.ring.getONE(); 612 long p = P.ring.characteristic().longValueExact(); 613 for (Map.Entry<GenPolynomial<C>, Long> me : F.entrySet()) { 614 GenPolynomial<C> f = me.getKey(); 615 Long E = me.getValue(); 616 long e = E.longValue(); 617 GenPolynomial<C> g = f.power(e); 618 if (!f.isConstant()) { 619 g = g.power(p); 620 } 621 t = t.multiply(g); 622 } 623 boolean f = P.equals(t) || P.equals(t.negate()); 624 if (!f) { 625 System.out.println("\nfactorization(map): " + f); 626 System.out.println("P = " + P); 627 System.out.println("t = " + t); 628 P = P.monic(); 629 t = t.monic(); 630 f = P.equals(t) || P.equals(t.negate()); 631 if (f) { 632 return f; 633 } 634 System.out.println("\nfactorization(map): " + f); 635 System.out.println("P = " + P); 636 System.out.println("t = " + t); 637 } 638 return f; 639 } 640 641 642 /** 643 * Recursive polynomial is char-th root. 644 * @param P recursive polynomial. 645 * @param F = [p_1 -> e_1, ..., p_k -> e_k]. 646 * @return true if P = prod_{i=1,...,k} p_i**(e_i*p), else false. 647 */ 648 public boolean isRecursiveCharRoot(GenPolynomial<GenPolynomial<C>> P, 649 SortedMap<GenPolynomial<GenPolynomial<C>>, Long> F) { 650 if (P == null || F == null) { 651 throw new IllegalArgumentException("P and F may not be null"); 652 } 653 if (P.isZERO() && F.size() == 0) { 654 return true; 655 } 656 GenPolynomial<GenPolynomial<C>> t = P.ring.getONE(); 657 long p = P.ring.characteristic().longValueExact(); 658 for (Map.Entry<GenPolynomial<GenPolynomial<C>>, Long> me : F.entrySet()) { 659 GenPolynomial<GenPolynomial<C>> f = me.getKey(); 660 Long E = me.getValue(); 661 long e = E.longValue(); 662 GenPolynomial<GenPolynomial<C>> g = f.power(e); 663 if (!f.isConstant()) { 664 g = g.power(p); 665 } 666 t = t.multiply(g); 667 } 668 boolean f = P.equals(t) || P.equals(t.negate()); 669 if (!f) { 670 System.out.println("\nfactorization(map): " + f); 671 System.out.println("P = " + P); 672 System.out.println("t = " + t); 673 P = P.monic(); 674 t = t.monic(); 675 f = P.equals(t) || P.equals(t.negate()); 676 if (f) { 677 return f; 678 } 679 System.out.println("\nfactorization(map): " + f); 680 System.out.println("P = " + P); 681 System.out.println("t = " + t); 682 } 683 return f; 684 } 685 686 687 /** 688 * Recursive polynomial is char-th root. 689 * @param P recursive polynomial. 690 * @param r = recursive polynomial. 691 * @return true if P = r**p, else false. 692 */ 693 public boolean isRecursiveCharRoot(GenPolynomial<GenPolynomial<C>> P, GenPolynomial<GenPolynomial<C>> r) { 694 if (P == null || r == null) { 695 throw new IllegalArgumentException("P and r may not be null"); 696 } 697 if (P.isZERO() && r.isZERO()) { 698 return true; 699 } 700 long p = P.ring.characteristic().longValueExact(); 701 GenPolynomial<GenPolynomial<C>> t = r.power(p); 702 703 boolean f = P.equals(t) || P.equals(t.negate()); 704 if (!f) { 705 System.out.println("\nisCharRoot: " + f); 706 System.out.println("P = " + P); 707 System.out.println("t = " + t); 708 P = P.monic(); 709 t = t.monic(); 710 f = P.equals(t) || P.equals(t.negate()); 711 if (f) { 712 return f; 713 } 714 System.out.println("\nisCharRoot: " + f); 715 System.out.println("P = " + P); 716 System.out.println("t = " + t); 717 } 718 return f; 719 } 720 721}