001 /*
002 * $Id: SquarefreeFiniteFieldCharP.java 3290 2010-08-26 09:18:48Z kredel $
003 */
004
005 package edu.jas.ufd;
006
007
008 import java.util.SortedMap;
009 import java.util.TreeMap;
010
011 import org.apache.log4j.Logger;
012
013 import edu.jas.arith.BigInteger;
014 import edu.jas.poly.ExpVector;
015 import edu.jas.poly.GenPolynomial;
016 import edu.jas.poly.GenPolynomialRing;
017 import edu.jas.poly.Monomial;
018 import edu.jas.structure.GcdRingElem;
019 import edu.jas.structure.Power;
020 import edu.jas.structure.RingFactory;
021
022
023 /**
024 * Squarefree decomposition for finite coefficient fields of characteristic p.
025 * @author Heinz Kredel
026 */
027
028 public class SquarefreeFiniteFieldCharP<C extends GcdRingElem<C>> extends SquarefreeFieldCharP<C> {
029
030
031 private static final Logger logger = Logger.getLogger(SquarefreeFiniteFieldCharP.class);
032
033
034 private final boolean debug = logger.isDebugEnabled();
035
036
037 /**
038 * Constructor.
039 */
040 public SquarefreeFiniteFieldCharP(RingFactory<C> fac) {
041 super(fac);
042 // isFinite() predicate now present
043 if ( !fac.isFinite() ) {
044 throw new IllegalArgumentException("fac must be finite");
045 }
046 }
047
048
049 /* --------- char-th roots --------------------- */
050
051 /**
052 * Characteristics root of a coefficient. <b>Note:</b> not needed at the
053 * moment.
054 * @param p coefficient.
055 * @return [p -> k] if exists k with e=k*charactristic(c) and c = p**e,
056 * else null.
057 */
058 public SortedMap<C, Long> rootCharacteristic(C p) {
059 if (p == null) {
060 throw new IllegalArgumentException(this.getClass().getName() + " p == null");
061 }
062 // already checked in constructor:
063 //java.math.BigInteger c = p.factory().characteristic();
064 //if ( c.signum() == 0 ) {
065 // return null;
066 //}
067 SortedMap<C, Long> root = new TreeMap<C, Long>();
068 if (p.isZERO()) {
069 return root;
070 }
071 // true for finite fields:
072 root.put(p, 1L);
073 return root;
074 }
075
076
077 /**
078 * Characteristics root of a coefficient.
079 * @param c coefficient.
080 * @return r with r**p == c, if such an r exists, else null.
081 */
082 public C coeffRootCharacteristic(C c) {
083 if (c == null || c.isZERO()) {
084 return c;
085 }
086 C r = c;
087 if (aCoFac == null && qCoFac == null) {
088 // case ModInteger: c**p == c
089 return r;
090 }
091 if (aCoFac != null) {
092 // case AlgebraicNumber<ModInteger>: r = c**(p**(d-1)), r**p == c
093 long d = aCoFac.totalExtensionDegree();
094 //System.out.println("d = " + d);
095 if (d <= 1) {
096 return r;
097 }
098 BigInteger p = new BigInteger(aCoFac.characteristic());
099 BigInteger q = Power.<BigInteger> positivePower(p, d - 1);
100 //System.out.println("p**(d-1) = " + q);
101 r = Power.<C> positivePower(r, q.getVal());
102 //System.out.println("r**q = " + r);
103 return r;
104 }
105 if (qCoFac != null) {
106 throw new UnsupportedOperationException("case QuotientRing not yet implemented");
107 }
108 return r;
109 }
110
111
112 /**
113 * Characteristics root of a polynomial. <b>Note:</b> call only in
114 * recursion.
115 * @param P polynomial.
116 * @return [p -> k] if exists k with e=k*charactristic(P) and P = p**e,
117 * else null.
118 */
119 public SortedMap<GenPolynomial<C>, Long> rootCharacteristic(GenPolynomial<C> P) {
120 if (P == null) {
121 throw new IllegalArgumentException(this.getClass().getName() + " P == null");
122 }
123 java.math.BigInteger c = P.ring.characteristic();
124 if (c.signum() == 0) {
125 return null;
126 }
127 SortedMap<GenPolynomial<C>, Long> root = new TreeMap<GenPolynomial<C>, Long>();
128 if (P.isZERO()) {
129 return root;
130 }
131 if (P.isONE()) {
132 root.put(P, 1L);
133 return root;
134 }
135 SortedMap<GenPolynomial<C>, Long> sf = squarefreeFactors(P);
136 if (logger.isInfoEnabled()) {
137 logger.info("sf = " + sf);
138 }
139 // better: test if sf.size() == 1 // not ok
140 Long k = null;
141 for (GenPolynomial<C> p : sf.keySet()) {
142 if (p.isConstant()) {
143 //System.out.println("p,const = " + p);
144 continue;
145 }
146 Long e = sf.get(p);
147 java.math.BigInteger E = new java.math.BigInteger(e.toString());
148 java.math.BigInteger r = E.remainder(c);
149 if (!r.equals(java.math.BigInteger.ZERO)) {
150 //System.out.println("r = " + r);
151 return null;
152 }
153 if (k == null) {
154 k = e;
155 } else if (k.compareTo(e) >= 0) {
156 k = e;
157 }
158 }
159 // now c divides all exponents
160 Long cl = c.longValue();
161 GenPolynomial<C> rp = P.ring.getONE();
162 for (GenPolynomial<C> q : sf.keySet()) {
163 Long e = sf.get(q);
164 if (q.isConstant()) { // ensure p-th root
165 C qc = q.leadingBaseCoefficient();
166 //System.out.println("qc,const = " + qc + ", e = " + e);
167 if (e > 1L) {
168 qc = Power.<C> positivePower(qc, e);
169 e = 1L;
170 }
171 C qr = coeffRootCharacteristic(qc);
172 //System.out.println("qr,const = " + qr);
173 q = P.ring.getONE().multiply(qr);
174 root.put(q, 1L);
175 continue;
176 }
177 if (e > k) {
178 long ep = e / cl;
179 q = Power.<GenPolynomial<C>> positivePower(q, ep);
180 }
181 rp = rp.multiply(q);
182 }
183 if (k != null) {
184 k = k / cl;
185 root.put(rp, k);
186 }
187 //System.out.println("sf,root = " + root);
188 return root;
189 }
190
191
192 /**
193 * GenPolynomial char-th root univariate polynomial.
194 * Base coefficient type must be
195 * finite field, that is ModInteger or AlgebraicNumber<ModInteger>
196 * etc.
197 * @param P GenPolynomial.
198 * @return char-th_rootOf(P), or null if no char-th root.
199 */
200 @Override
201 public GenPolynomial<C> baseRootCharacteristic(GenPolynomial<C> P) {
202 if (P == null || P.isZERO()) {
203 return P;
204 }
205 GenPolynomialRing<C> pfac = P.ring;
206 if (pfac.nvar > 1) {
207 // basePthRoot not possible by return type
208 throw new IllegalArgumentException(P.getClass().getName() + " only for univariate polynomials");
209 }
210 RingFactory<C> rf = pfac.coFac;
211 if (rf.characteristic().signum() != 1) {
212 // basePthRoot not possible
213 throw new IllegalArgumentException(P.getClass().getName() + " only for char p > 0 " + rf);
214 }
215 long mp = rf.characteristic().longValue();
216 GenPolynomial<C> d = pfac.getZERO().clone();
217 for (Monomial<C> m : P) {
218 ExpVector f = m.e;
219 long fl = f.getVal(0);
220 if (fl % mp != 0) {
221 return null;
222 }
223 fl = fl / mp;
224 ExpVector e = ExpVector.create(1, 0, fl);
225 // for m.c exists a char-th root, since finite field
226 C r = coeffRootCharacteristic(m.c);
227 d.doPutToMap(e, r);
228 }
229 return d;
230 }
231
232
233 /**
234 * GenPolynomial char-th root univariate polynomial with polynomial coefficients.
235 * @param P recursive univariate GenPolynomial.
236 * @return char-th_rootOf(P), or null if P is no char-th root.
237 */
238 @Override
239 public GenPolynomial<GenPolynomial<C>> recursiveUnivariateRootCharacteristic(
240 GenPolynomial<GenPolynomial<C>> P) {
241 if (P == null || P.isZERO()) {
242 return P;
243 }
244 GenPolynomialRing<GenPolynomial<C>> pfac = P.ring;
245 if (pfac.nvar > 1) {
246 // basePthRoot not possible by return type
247 throw new IllegalArgumentException(P.getClass().getName() + " only for univariate polynomials");
248 }
249 RingFactory<GenPolynomial<C>> rf = pfac.coFac;
250 if (rf.characteristic().signum() != 1) {
251 // basePthRoot not possible
252 throw new IllegalArgumentException(P.getClass().getName() + " only for char p > 0 " + rf);
253 }
254 long mp = rf.characteristic().longValue();
255 GenPolynomial<GenPolynomial<C>> d = pfac.getZERO().clone();
256 for (Monomial<GenPolynomial<C>> m : P) {
257 ExpVector f = m.e;
258 long fl = f.getVal(0);
259 if (fl % mp != 0) {
260 return null;
261 }
262 fl = fl / mp;
263 SortedMap<GenPolynomial<C>, Long> sm = rootCharacteristic(m.c);
264 if (sm == null) {
265 return null;
266 }
267 if (logger.isInfoEnabled()) {
268 logger.info("sm,rec = " + sm);
269 }
270 GenPolynomial<C> r = rf.getONE();
271 for (GenPolynomial<C> rp : sm.keySet()) {
272 long gl = sm.get(rp);
273 if (gl > 1) {
274 rp = Power.<GenPolynomial<C>> positivePower(rp, gl);
275 }
276 r = r.multiply(rp);
277 }
278 ExpVector e = ExpVector.create(1, 0, fl);
279 //System.out.println("put-root r = " + r + ", e = " + e);
280 d.doPutToMap(e, r);
281 }
282 return d;
283 }
284
285 }