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