001/* 002 * $Id$ 003 */ 004 005package edu.jas.ufd; 006 007 008import java.util.ArrayList; 009import java.util.List; 010 011import org.apache.logging.log4j.LogManager; 012import org.apache.logging.log4j.Logger; 013 014import edu.jas.poly.AlgebraicNumber; 015import edu.jas.poly.AlgebraicNumberRing; 016import edu.jas.poly.GenPolynomial; 017import edu.jas.poly.GenPolynomialRing; 018import edu.jas.structure.GcdRingElem; 019 020 021/** 022 * Algebraic number coefficients factorization algorithms. This class implements 023 * factorization methods for polynomials over algebraic numbers over rational 024 * numbers or over (prime) modular integers. 025 * @author Heinz Kredel 026 * @param <C> coefficient type 027 */ 028 029public class FactorAlgebraic<C extends GcdRingElem<C>> extends FactorAbsolute<AlgebraicNumber<C>> { 030 031 032 private static final Logger logger = LogManager.getLogger(FactorAlgebraic.class); 033 034 035 private static final boolean debug = logger.isDebugEnabled(); 036 037 038 /** 039 * Factorization engine for base coefficients. 040 */ 041 public final FactorAbstract<C> factorCoeff; 042 043 044 /** 045 * No argument constructor. <b>Note:</b> can't use this constructor. 046 */ 047 protected FactorAlgebraic() { 048 throw new IllegalArgumentException("don't use this constructor"); 049 } 050 051 052 /** 053 * Constructor. 054 * @param fac algebraic number factory. 055 */ 056 public FactorAlgebraic(AlgebraicNumberRing<C> fac) { 057 this(fac, FactorFactory.<C> getImplementation(fac.ring.coFac)); 058 } 059 060 061 /** 062 * Constructor. 063 * @param fac algebraic number factory. 064 * @param factorCoeff factorization engine for polynomials over base 065 * coefficients. 066 */ 067 public FactorAlgebraic(AlgebraicNumberRing<C> fac, FactorAbstract<C> factorCoeff) { 068 super(fac); 069 this.factorCoeff = factorCoeff; 070 } 071 072 073 /** 074 * GenPolynomial base factorization of a squarefree polynomial. 075 * @param P squarefree GenPolynomial<AlgebraicNumber<C>>. 076 * @return [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i. 077 */ 078 @Override 079 public List<GenPolynomial<AlgebraicNumber<C>>> baseFactorsSquarefree( 080 GenPolynomial<AlgebraicNumber<C>> P) { 081 if (P == null) { 082 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 083 } 084 List<GenPolynomial<AlgebraicNumber<C>>> factors = new ArrayList<GenPolynomial<AlgebraicNumber<C>>>(); 085 if (P.isZERO()) { 086 return factors; 087 } 088 if (P.isONE()) { 089 factors.add(P); 090 return factors; 091 } 092 GenPolynomialRing<AlgebraicNumber<C>> pfac = P.ring; // Q(alpha)[x] 093 if (pfac.nvar > 1) { 094 throw new IllegalArgumentException("only for univariate polynomials"); 095 } 096 AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) pfac.coFac; 097 AlgebraicNumber<C> ldcf = P.leadingBaseCoefficient(); 098 if (!ldcf.isONE()) { 099 P = P.monic(); 100 factors.add(pfac.getONE().multiply(ldcf)); 101 } 102 //System.out.println("\nP = " + P); 103 if (debug) { 104 Squarefree<AlgebraicNumber<C>> sqengine = SquarefreeFactory 105 .<AlgebraicNumber<C>> getImplementation(afac); 106 if (!sqengine.isSquarefree(P)) { 107 throw new RuntimeException("P not squarefree: " + sqengine.squarefreeFactors(P)); 108 } 109 GenPolynomial<C> modu = afac.modul; 110 if (!factorCoeff.isIrreducible(modu)) { 111 throw new RuntimeException("modul not irreducible: " + factorCoeff.factors(modu)); 112 } 113 System.out.println("P squarefree and modul irreducible"); 114 //GreatestCommonDivisor<AlgebraicNumber<C>> aengine //= GCDFactory.<AlgebraicNumber<C>> getProxy(afac); 115 // = new GreatestCommonDivisorSimple<AlgebraicNumber<C>>( /*cfac.coFac*/ ); 116 } 117 118 // search squarefree norm 119 long k = 0L; 120 long ks = k; 121 GenPolynomial<C> res = null; 122 boolean sqf = false; 123 //int[] klist = new int[]{ 0, 1, 2, 3, -1, -2, -3 , 5, -5, 7, -7, 101, -101, 1001, -1001 }; 124 //int[] klist = new int[]{ 0, 1, 2, 3, -1, -2, -3 , 5, -5, 7, -7, 23, -23, 167, -167 }; 125 //int[] klist = new int[] { 0, -1, -2, 1, 2, -3, 3 }; 126 int[] klist = new int[] { 0, -1, -2, 1, 2 }; 127 int ki = 0; 128 while (!sqf) { 129 // k = 0,1,2,-1,-2 130 if (ki >= klist.length) { 131 break; 132 } 133 k = klist[ki]; 134 ki++; 135 // compute norm with x -> ( y - k x ) 136 ks = k; 137 res = PolyUfdUtil.<C> norm(P, ks); 138 //System.out.println("res = " + res); 139 if (res.isZERO() || res.isConstant()) { 140 continue; 141 } 142 sqf = factorCoeff.isSquarefree(res); 143 } 144 // if Res is now squarefree, else must take radical factorization 145 List<GenPolynomial<C>> nfacs; 146 if (!sqf) { 147 //System.out.println("\nres = " + res); 148 logger.warn("sqf({}) = {}", ks, res.degree()); 149 //res = factorCoeff.squarefreePart(res); // better use obtained factors 150 //res = factorCoeff.baseFactors(res).lastKey(); 151 } 152 //res = res.monic(); 153 logger.info("res = {}", res); 154 nfacs = factorCoeff.baseFactorsRadical(res); 155 logger.info("res facs = {}", nfacs); // Q[X] 156 if (nfacs.size() == 1) { 157 factors.add(P); 158 return factors; 159 } 160 161 // compute gcds of factors with polynomial in Q(alpha)[X] 162 GenPolynomial<AlgebraicNumber<C>> Pp = P; 163 //System.out.println("Pp = " + Pp); 164 GenPolynomial<AlgebraicNumber<C>> Ni; 165 for (GenPolynomial<C> nfi : nfacs) { 166 //System.out.println("nfi = " + nfi); 167 Ni = PolyUfdUtil.<C> substituteConvertToAlgebraicCoefficients(pfac, nfi, ks); 168 if (logger.isInfoEnabled()) { 169 logger.info("Ni = {}", Ni); 170 //System.out.println("Pp = " + Pp); 171 } 172 // compute gcds of factors with polynomial 173 GenPolynomial<AlgebraicNumber<C>> pni = engine.gcd(Ni, Pp); 174 if (!pni.leadingBaseCoefficient().isONE()) { 175 pni = pni.monic(); 176 } 177 logger.info("gcd(Ni,Pp) = {}", pni); 178 if (!pni.isONE()) { 179 factors.add(pni); 180 Pp = Pp.divide(pni); 181 } 182 } 183 if (!Pp.isZERO() && !Pp.isONE()) { // irreducible rest 184 factors.add(Pp); 185 } 186 //System.out.println("afactors = " + factors); 187 return factors; 188 } 189 190 191 /** 192 * GenPolynomial factorization of a squarefree polynomial. 193 * @param P squarefree and primitive! (respectively monic) 194 * GenPolynomial<AlgebraicNumber<C>>. 195 * @return [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i. 196 */ 197 @Override 198 public List<GenPolynomial<AlgebraicNumber<C>>> factorsSquarefree(GenPolynomial<AlgebraicNumber<C>> P) { 199 if (P == null) { 200 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 201 } 202 List<GenPolynomial<AlgebraicNumber<C>>> factors = new ArrayList<GenPolynomial<AlgebraicNumber<C>>>(); 203 if (P.isZERO()) { 204 return factors; 205 } 206 if (P.isONE()) { 207 factors.add(P); 208 return factors; 209 } 210 GenPolynomialRing<AlgebraicNumber<C>> pfac = P.ring; // Q(alpha)[x1,...,xn] 211 if (pfac.nvar <= 1) { 212 throw new IllegalArgumentException("only for multivariate polynomials"); 213 } 214 //AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) pfac.coFac; 215 AlgebraicNumber<C> ldcf = P.leadingBaseCoefficient(); 216 if (!ldcf.isONE()) { 217 P = P.monic(); 218 factors.add(pfac.getONE().multiply(ldcf)); 219 } 220 if (P.degreeVector().totalDeg() <= 1L) { 221 factors.add(P); 222 return factors; 223 } 224 //System.out.println("\nP = " + P); 225 226 // search squarefree norm 227 long k = 0L; 228 long ks = k; 229 GenPolynomial<C> res = null; 230 boolean sqf = false; 231 //int[] klist = new int[]{ 0, 1, 2, 3, -1, -2, -3 , 5, -5, 7, -7, 101, -101, 1001, -1001 }; 232 //int[] klist = new int[]{ 0, 1, 2, 3, -1, -2, -3 , 5, -5, 7, -7, 23, -23, 167, -167 }; 233 //int[] klist = new int[] { 0, -1, -2, 1, 2, -3, 3 }; 234 int[] klist = new int[] { 0, -1, -2, 1, 2 }; 235 int ki = 0; 236 while (!sqf) { 237 // k = 0,1,2,-1,-2 238 if (ki >= klist.length) { 239 logger.warn("sqf({}) = {}", ks, res.degree()); 240 break; 241 } 242 k = klist[ki]; 243 ki++; 244 // compute norm with x -> ( y - k x ) 245 ks = k; 246 res = PolyUfdUtil.<C> norm(P, ks); 247 //System.out.println("res = " + res); 248 if (res.isZERO() || res.isConstant()) { 249 continue; 250 } 251 sqf = factorCoeff.isSquarefree(res); 252 //System.out.println("resfact = " + factorCoeff.factors(res) + "\n"); 253 } 254 // if Res is now squarefree, else must take radical factorization 255 List<GenPolynomial<C>> nfacs; 256 if (!sqf) { 257 System.out.println("sqf_" + pfac.nvar + "(" + ks + ") = " + res.degree()); 258 } 259 //res = res.monic(); 260 logger.info("res = {}", res); 261 logger.info("factorCoeff = {}", factorCoeff); 262 nfacs = factorCoeff.factorsRadical(res); 263 //System.out.println("\nnfacs = " + nfacs); // Q[X] 264 logger.info("res facs = {}", nfacs); // Q[X] 265 if (nfacs.size() == 1) { 266 factors.add(P); 267 return factors; 268 } 269 270 // compute gcds of factors with polynomial in Q(alpha)[X] 271 GenPolynomial<AlgebraicNumber<C>> Pp = P; 272 //System.out.println("Pp = " + Pp); 273 GenPolynomial<AlgebraicNumber<C>> Ni; 274 for (GenPolynomial<C> nfi : nfacs) { 275 //System.out.println("nfi = " + nfi); 276 Ni = PolyUfdUtil.<C> substituteConvertToAlgebraicCoefficients(pfac, nfi, ks); 277 if (logger.isInfoEnabled()) { 278 logger.info("Ni = {}", Ni); 279 //System.out.println("Pp = " + Pp); 280 } 281 // compute gcds of factors with polynomial 282 GenPolynomial<AlgebraicNumber<C>> pni = engine.gcd(Ni, Pp); 283 if (!pni.leadingBaseCoefficient().isONE()) { 284 //System.out.println("gcd(Ni,Pp) not monic " + pni); 285 pni = pni.monic(); 286 } 287 logger.info("gcd(Ni,Pp) = {}", pni); 288 //System.out.println("gcd(Ni,Pp) = " + pni); 289 if (!pni.isONE()) { 290 factors.add(pni); 291 Pp = Pp.divide(pni); 292 } 293 } 294 if (!Pp.isZERO() && !Pp.isONE()) { // irreducible rest 295 factors.add(Pp); 296 } 297 //factors.add(P); 298 return factors; 299 } 300 301}