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