001/* 002 * $Id: FactorAlgebraic.java 4028 2012-07-24 18:42:16Z kredel $ 003 */ 004 005package edu.jas.ufd; 006 007 008import java.util.ArrayList; 009import java.util.List; 010 011import org.apache.log4j.Logger; 012 013import edu.jas.poly.AlgebraicNumber; 014import edu.jas.poly.AlgebraicNumberRing; 015import edu.jas.poly.GenPolynomial; 016import edu.jas.poly.GenPolynomialRing; 017import edu.jas.poly.PolyUtil; 018import edu.jas.poly.TermOrder; 019import edu.jas.structure.GcdRingElem; 020 021 022/** 023 * Algebraic number coefficients factorization algorithms. This class implements 024 * factorization methods for polynomials over algebraic numbers over rational 025 * numbers or over (prime) modular integers. 026 * @author Heinz Kredel 027 * @param <C> coefficient type 028 */ 029 030public class FactorAlgebraic<C extends GcdRingElem<C>> extends FactorAbsolute<AlgebraicNumber<C>> { 031 032 033 private static final Logger logger = Logger.getLogger(FactorAlgebraic.class); 034 035 036 private final boolean debug = logger.isDebugEnabled(); 037 038 039 /** 040 * Factorization engine for base coefficients. 041 */ 042 public final FactorAbstract<C> factorCoeff; 043 044 045 /** 046 * No argument constructor. <b>Note:</b> can't use this constructor. 047 */ 048 protected FactorAlgebraic() { 049 throw new IllegalArgumentException("don't use this constructor"); 050 } 051 052 053 /** 054 * Constructor. 055 * @param fac algebraic number factory. 056 */ 057 public FactorAlgebraic(AlgebraicNumberRing<C> fac) { 058 this(fac, FactorFactory.<C> getImplementation(fac.ring.coFac) ); 059 } 060 061 062 /** 063 * Constructor. 064 * @param fac algebraic number factory. 065 * @param factorCoeff factorization engine for polynomials over base 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(GenPolynomial<AlgebraicNumber<C>> P) { 080 if (P == null) { 081 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 082 } 083 List<GenPolynomial<AlgebraicNumber<C>>> factors = new ArrayList<GenPolynomial<AlgebraicNumber<C>>>(); 084 if (P.isZERO()) { 085 return factors; 086 } 087 if (P.isONE()) { 088 factors.add(P); 089 return factors; 090 } 091 GenPolynomialRing<AlgebraicNumber<C>> pfac = P.ring; // Q(alpha)[x] 092 if (pfac.nvar > 1) { 093 throw new IllegalArgumentException("only for univariate polynomials"); 094 } 095 AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) pfac.coFac; 096 AlgebraicNumber<C> ldcf = P.leadingBaseCoefficient(); 097 if (!ldcf.isONE()) { 098 P = P.monic(); 099 factors.add(pfac.getONE().multiply(ldcf)); 100 } 101 //System.out.println("\nP = " + P); 102 if (debug) { 103 Squarefree<AlgebraicNumber<C>> sqengine = SquarefreeFactory.<AlgebraicNumber<C>> getImplementation(afac); 104 if ( !sqengine.isSquarefree(P) ) { 105 throw new RuntimeException("P not squarefree: " + sqengine.squarefreeFactors(P)); 106 } 107 GenPolynomial<C> modu = afac.modul; 108 if ( !factorCoeff.isIrreducible(modu) ) { 109 throw new RuntimeException("modul not irreducible: " + factorCoeff.factors(modu)); 110 } 111 System.out.println("P squarefree and modul irreducible"); 112 //GreatestCommonDivisor<AlgebraicNumber<C>> aengine //= GCDFactory.<AlgebraicNumber<C>> getProxy(afac); 113 // = new GreatestCommonDivisorSimple<AlgebraicNumber<C>>( /*cfac.coFac*/ ); 114 } 115 116 // search squarefree norm 117 long k = 0L; 118 long ks = k; 119 GenPolynomial<C> res = null; 120 boolean sqf = false; 121 //int[] klist = new int[]{ 0, 1, 2, 3, -1, -2, -3 , 5, -5, 7, -7, 101, -101, 1001, -1001 }; 122 //int[] klist = new int[]{ 0, 1, 2, 3, -1, -2, -3 , 5, -5, 7, -7, 23, -23, 167, -167 }; 123 //int[] klist = new int[] { 0, -1, -2, 1, 2, -3, 3 }; 124 int[] klist = new int[] { 0, -1, -2, 1, 2 }; 125 int ki = 0; 126 while (!sqf) { 127 // k = 0,1,2,-1,-2 128 if (ki >= klist.length) { 129 break; 130 } 131 k = klist[ki]; 132 ki++; 133 // compute norm with x -> ( y - k x ) 134 ks = k; 135 res = PolyUfdUtil.<C> norm(P, ks); 136 //System.out.println("res = " + res); 137 if (res.isZERO() || res.isConstant()) { 138 continue; 139 } 140 sqf = factorCoeff.isSquarefree(res); 141 //System.out.println("sqf("+ks+") = " + res.degree()); 142 //System.out.println("resfact = " + factorCoeff.baseFactors(res) + "\n"); 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 System.out.println("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 if (logger.isInfoEnabled()) { 154 logger.info("res = " + res); 155 //System.out.println("\nres = " + res); 156 } 157 nfacs = factorCoeff.baseFactorsRadical(res); 158 if (logger.isInfoEnabled()) { 159 logger.info("res facs = " + nfacs); // Q[X] 160 //System.out.println("\nnfacs = " + nfacs); // Q[X] 161 } 162 if (nfacs.size() == 1) { 163 factors.add(P); 164 return factors; 165 } 166 167 // compute gcds of factors with polynomial in Q(alpha)[X] 168 GenPolynomial<AlgebraicNumber<C>> Pp = P; 169 //System.out.println("Pp = " + Pp); 170 GenPolynomial<AlgebraicNumber<C>> Ni; 171 for (GenPolynomial<C> nfi : nfacs) { 172 //System.out.println("nfi = " + nfi); 173 Ni = PolyUfdUtil.<C> substituteConvertToAlgebraicCoefficients(pfac, nfi, ks); 174 if (logger.isInfoEnabled()) { 175 logger.info("Ni = " + Ni); 176 //System.out.println("Pp = " + Pp); 177 //System.out.println("Ni = " + Ni); 178 } 179 // compute gcds of factors with polynomial 180 GenPolynomial<AlgebraicNumber<C>> pni = engine.gcd(Ni, Pp); 181 if (!pni.leadingBaseCoefficient().isONE()) { 182 //System.out.println("gcd(Ni,Pp) not monic " + pni); 183 pni = pni.monic(); 184 } 185 if (logger.isInfoEnabled()) { 186 logger.info("gcd(Ni,Pp) = " + pni); 187 //System.out.println("gcd(Ni,Pp) = " + pni); 188 } 189 if (!pni.isONE()) { 190 factors.add(pni); 191 Pp = Pp.divide(pni); 192 // } else { 193 // GenPolynomial<AlgebraicNumber<C>> qni = Pp.divide(Ni); 194 // GenPolynomial<AlgebraicNumber<C>> rni = Pp.remainder(Ni); 195 // System.out.println("div qni = " + qni); 196 // System.out.println("div rni = " + rni); 197 // continue; 198 // //throw new RuntimeException("gcd(Ni,Pp) == 1"); 199 } 200 } 201 if (!Pp.isZERO() && !Pp.isONE()) { // irreducible rest 202 factors.add(Pp); 203 } 204 //System.out.println("afactors = " + factors); 205 return factors; 206 } 207 208}