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.ExpVector; 016import edu.jas.poly.GenPolynomial; 017import edu.jas.poly.GenPolynomialRing; 018import edu.jas.poly.Monomial; 019import edu.jas.poly.PolyUtil; 020import edu.jas.structure.GcdRingElem; 021import edu.jas.structure.RingFactory; 022 023 024/** 025 * Squarefree decomposition for infinite coefficient fields of characteristic p. 026 * @author Heinz Kredel 027 */ 028 029public class SquarefreeInfiniteFieldCharP<C extends GcdRingElem<C>> 030 extends SquarefreeFieldCharP<Quotient<C>> { 031 032 033 private static final Logger logger = LogManager.getLogger(SquarefreeInfiniteFieldCharP.class); 034 035 036 //private static final boolean debug = logger.isDebugEnabled(); 037 038 039 /** 040 * Squarefree engine for infinite ring of characteristic p base 041 * coefficients. 042 */ 043 protected final SquarefreeAbstract<C> qengine; 044 045 046 /** 047 * Constructor. 048 */ 049 @SuppressWarnings("unchecked") 050 public SquarefreeInfiniteFieldCharP(RingFactory<Quotient<C>> fac) { 051 super(fac); 052 // isFinite() predicate now present 053 if (fac.isFinite()) { 054 throw new IllegalArgumentException("fac must be in-finite"); 055 } 056 QuotientRing<C> qfac = (QuotientRing<C>) fac; 057 GenPolynomialRing<C> rfac = qfac.ring; 058 qengine = (SquarefreeAbstract) SquarefreeFactory.<C> getImplementation(rfac); 059 //qengine = new SquarefreeFiniteFieldCharP<C>(rfac.coFac); 060 //qengine = new SquarefreeInfiniteRingCharP<C>( rfac.coFac ); 061 } 062 063 064 /* --------- quotient char-th roots --------------------- */ 065 066 067 /** 068 * Squarefree factors of a Quotient. 069 * @param P Quotient. 070 * @return [p_1 -> e_1, ..., p_k -> e_k] with P = prod_{i=1, ..., k} 071 * p_i^{e_i} and p_i squarefree and gcd(p_i, p_j) = 1, for i != j. 072 */ 073 @Override 074 public SortedMap<Quotient<C>, Long> squarefreeFactors(Quotient<C> P) { 075 if (P == null) { 076 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 077 } 078 SortedMap<Quotient<C>, Long> factors = new TreeMap<Quotient<C>, Long>(); 079 if (P.isZERO()) { 080 return factors; 081 } 082 if (P.isONE()) { 083 factors.put(P, 1L); 084 return factors; 085 } 086 GenPolynomial<C> num = P.num; 087 GenPolynomial<C> den = P.den; 088 QuotientRing<C> pfac = P.ring; 089 GenPolynomial<C> one = pfac.ring.getONE(); 090 if (!num.isONE()) { 091 SortedMap<GenPolynomial<C>, Long> nfac = qengine.squarefreeFactors(num); 092 //System.out.println("nfac = " + nfac); 093 for (Map.Entry<GenPolynomial<C>, Long> me : nfac.entrySet()) { 094 GenPolynomial<C> nfp = me.getKey(); 095 Quotient<C> nf = new Quotient<C>(pfac, nfp); 096 factors.put(nf, me.getValue()); //nfac.get(nfp)); 097 } 098 } 099 if (den.isONE()) { 100 if (factors.size() == 0) { 101 factors.put(P, 1L); 102 } 103 return factors; 104 } 105 SortedMap<GenPolynomial<C>, Long> dfac = qengine.squarefreeFactors(den); 106 //System.out.println("dfac = " + dfac); 107 for (Map.Entry<GenPolynomial<C>, Long> me : dfac.entrySet()) { 108 GenPolynomial<C> dfp = me.getKey(); 109 Quotient<C> df = new Quotient<C>(pfac, one, dfp); 110 factors.put(df, me.getValue()); //dfac.get(dfp)); 111 } 112 if (factors.size() == 0) { 113 factors.put(P, 1L); 114 } 115 return factors; 116 } 117 118 119 /** 120 * Characteristics root of a Quotient. 121 * @param P Quotient. 122 * @return [p -> k] if exists k with e=characteristic(P)*k and P = p**e, 123 * else null. 124 */ 125 public SortedMap<Quotient<C>, Long> rootCharacteristic(Quotient<C> P) { 126 if (P == null) { 127 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 128 } 129 java.math.BigInteger c = P.ring.characteristic(); 130 if (c.signum() == 0) { 131 return null; 132 } 133 SortedMap<Quotient<C>, Long> root = new TreeMap<Quotient<C>, Long>(); 134 if (P.isZERO()) { 135 return root; 136 } 137 if (P.isONE()) { 138 root.put(P, 1L); 139 return root; 140 } 141 SortedMap<Quotient<C>, Long> sf = squarefreeFactors(P); 142 if (sf.size() == 0) { 143 return null; 144 } 145 logger.info("sf,quot = {}", sf); 146 // better: test if sf.size() == 2 // no, since num and den factors 147 Long k = null; 148 long cl = c.longValueExact(); 149 for (Map.Entry<Quotient<C>, Long> me : sf.entrySet()) { 150 Quotient<C> p = me.getKey(); 151 //System.out.println("p = " + p); 152 if (p.isConstant()) { // todo: check for non-constants in coefficients 153 continue; 154 } 155 Long e = me.getValue(); //sf.get(p); 156 long E = e.longValue(); 157 long r = E % cl; 158 if (r != 0) { 159 //System.out.println("r = " + r); 160 return null; 161 } 162 if (k == null) { 163 k = e; 164 } else if (k >= e) { 165 k = e; 166 } 167 } 168 if (k == null) { 169 k = 1L; //return null; 170 } 171 // now c divides all exponents of non constant elements 172 for (Map.Entry<Quotient<C>, Long> me : sf.entrySet()) { 173 Quotient<C> q = me.getKey(); 174 Long e = me.getValue(); //sf.get(q); 175 //System.out.println("q = " + q + ", e = " + e); 176 if (e >= k) { 177 e = e / cl; 178 //q = q.power(e); 179 root.put(q, e); 180 } else { // constant case 181 root.put(q, e); 182 } 183 } 184 //System.out.println("root = " + root); 185 return root; 186 } 187 188 189 /** 190 * GenPolynomial char-th root main variable. 191 * @param P univariate GenPolynomial with Quotient coefficients. 192 * @return char-th_rootOf(P), or null, if P is no char-th root. 193 */ 194 public GenPolynomial<Quotient<C>> rootCharacteristic(GenPolynomial<Quotient<C>> P) { 195 if (P == null || P.isZERO()) { 196 return P; 197 } 198 GenPolynomialRing<Quotient<C>> pfac = P.ring; 199 if (pfac.nvar > 1) { 200 // go to recursion 201 GenPolynomialRing<GenPolynomial<Quotient<C>>> rfac = pfac.recursive(1); 202 GenPolynomial<GenPolynomial<Quotient<C>>> Pr = PolyUtil.<Quotient<C>> recursive(rfac, P); 203 GenPolynomial<GenPolynomial<Quotient<C>>> Prc = recursiveUnivariateRootCharacteristic(Pr); 204 if (Prc == null) { 205 return null; 206 } 207 GenPolynomial<Quotient<C>> D = PolyUtil.<Quotient<C>> distribute(pfac, Prc); 208 return D; 209 } 210 RingFactory<Quotient<C>> rf = pfac.coFac; 211 if (rf.characteristic().signum() != 1) { 212 // basePthRoot not possible 213 throw new IllegalArgumentException( 214 P.getClass().getName() + " only for ModInteger polynomials " + rf); 215 } 216 long mp = rf.characteristic().longValueExact(); 217 GenPolynomial<Quotient<C>> d = pfac.getZERO().copy(); 218 for (Monomial<Quotient<C>> m : P) { 219 ExpVector f = m.e; 220 long fl = f.getVal(0); 221 if (fl % mp != 0) { 222 return null; 223 } 224 fl = fl / mp; 225 SortedMap<Quotient<C>, Long> sm = rootCharacteristic(m.c); 226 if (sm == null) { 227 return null; 228 } 229 logger.info("sm,root = {}", sm); 230 Quotient<C> r = rf.getONE(); 231 for (Map.Entry<Quotient<C>, Long> me : sm.entrySet()) { 232 Quotient<C> rp = me.getKey(); 233 long gl = me.getValue(); // sm.get(rp); 234 if (gl > 1) { 235 rp = rp.power(gl); 236 } 237 r = r.multiply(rp); 238 } 239 ExpVector e = ExpVector.create(1, 0, fl); 240 d.doPutToMap(e, r); 241 } 242 logger.info("sm,root,d = {}", d); 243 return d; 244 } 245 246 247 /** 248 * GenPolynomial char-th root univariate polynomial. 249 * @param P GenPolynomial. 250 * @return char-th_rootOf(P). 251 */ 252 @Override 253 public GenPolynomial<Quotient<C>> baseRootCharacteristic(GenPolynomial<Quotient<C>> P) { 254 if (P == null || P.isZERO()) { 255 return P; 256 } 257 GenPolynomialRing<Quotient<C>> pfac = P.ring; 258 if (pfac.nvar > 1) { 259 // basePthRoot not possible by return type 260 throw new IllegalArgumentException(P.getClass().getName() + " only for univariate polynomials"); 261 } 262 RingFactory<Quotient<C>> rf = pfac.coFac; 263 if (rf.characteristic().signum() != 1) { 264 // basePthRoot not possible 265 throw new IllegalArgumentException(P.getClass().getName() + " only for char p > 0 " + rf); 266 } 267 long mp = rf.characteristic().longValueExact(); 268 GenPolynomial<Quotient<C>> d = pfac.getZERO().copy(); 269 for (Monomial<Quotient<C>> m : P) { 270 //System.out.println("m = " + m); 271 ExpVector f = m.e; 272 long fl = f.getVal(0); 273 if (fl % mp != 0) { 274 return null; 275 } 276 fl = fl / mp; 277 SortedMap<Quotient<C>, Long> sm = rootCharacteristic(m.c); 278 if (sm == null) { 279 return null; 280 } 281 logger.info("sm,base,root = {}", sm); 282 Quotient<C> r = rf.getONE(); 283 for (Map.Entry<Quotient<C>, Long> me : sm.entrySet()) { 284 Quotient<C> rp = me.getKey(); 285 //System.out.println("rp = " + rp); 286 long gl = me.getValue(); //sm.get(rp); 287 //System.out.println("gl = " + gl); 288 Quotient<C> re = rp; 289 if (gl > 1) { 290 re = rp.power(gl); 291 } 292 //System.out.println("re = " + re); 293 r = r.multiply(re); 294 } 295 ExpVector e = ExpVector.create(1, 0, fl); 296 d.doPutToMap(e, r); 297 } 298 logger.info("sm,base,d = {}", d); 299 return d; 300 } 301 302 303 /** 304 * GenPolynomial char-th root univariate polynomial with polynomial 305 * coefficients. 306 * @param P recursive univariate GenPolynomial. 307 * @return char-th_rootOf(P), or null if P is no char-th root. 308 */ 309 @Override 310 public GenPolynomial<GenPolynomial<Quotient<C>>> recursiveUnivariateRootCharacteristic( 311 GenPolynomial<GenPolynomial<Quotient<C>>> P) { 312 if (P == null || P.isZERO()) { 313 return P; 314 } 315 GenPolynomialRing<GenPolynomial<Quotient<C>>> pfac = P.ring; 316 if (pfac.nvar > 1) { 317 // basePthRoot not possible by return type 318 throw new IllegalArgumentException( 319 P.getClass().getName() + " only for univariate recursive polynomials"); 320 } 321 RingFactory<GenPolynomial<Quotient<C>>> rf = pfac.coFac; 322 if (rf.characteristic().signum() != 1) { 323 // basePthRoot not possible 324 throw new IllegalArgumentException(P.getClass().getName() + " only for char p > 0 " + rf); 325 } 326 long mp = rf.characteristic().longValueExact(); 327 GenPolynomial<GenPolynomial<Quotient<C>>> d = pfac.getZERO().copy(); 328 for (Monomial<GenPolynomial<Quotient<C>>> m : P) { 329 ExpVector f = m.e; 330 long fl = f.getVal(0); 331 if (fl % mp != 0) { 332 return null; 333 } 334 fl = fl / mp; 335 GenPolynomial<Quotient<C>> r = rootCharacteristic(m.c); 336 if (r == null) { 337 return null; 338 } 339 ExpVector e = ExpVector.create(1, 0, fl); 340 d.doPutToMap(e, r); 341 } 342 return d; 343 } 344 345}