001 /*
002 * $Id: FactorAlgebraic.java 3670 2011-06-25 19:04:28Z kredel $
003 */
004
005 package edu.jas.ufd;
006
007
008 import java.util.ArrayList;
009 import java.util.List;
010
011 import org.apache.log4j.Logger;
012
013 import edu.jas.poly.AlgebraicNumber;
014 import edu.jas.poly.AlgebraicNumberRing;
015 import edu.jas.poly.GenPolynomial;
016 import edu.jas.poly.GenPolynomialRing;
017 import edu.jas.poly.PolyUtil;
018 import edu.jas.poly.TermOrder;
019 import 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
030 public 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 = true || logger.isInfoEnabled();
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 super(fac);
059 this.factorCoeff = FactorFactory.<C> getImplementation(fac.ring.coFac);
060 }
061
062
063 /**
064 * GenPolynomial base factorization of a squarefree polynomial.
065 * @param P squarefree GenPolynomial<AlgebraicNumber<C>>.
066 * @return [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i.
067 */
068 @Override
069 public List<GenPolynomial<AlgebraicNumber<C>>> baseFactorsSquarefree(GenPolynomial<AlgebraicNumber<C>> P) {
070 if (P == null) {
071 throw new IllegalArgumentException(this.getClass().getName() + " P == null");
072 }
073 List<GenPolynomial<AlgebraicNumber<C>>> factors = new ArrayList<GenPolynomial<AlgebraicNumber<C>>>();
074 if (P.isZERO()) {
075 return factors;
076 }
077 if (P.isONE()) {
078 factors.add(P);
079 return factors;
080 }
081 GenPolynomialRing<AlgebraicNumber<C>> pfac = P.ring; // Q(alpha)[x]
082 if (pfac.nvar > 1) {
083 throw new IllegalArgumentException("only for univariate polynomials");
084 }
085 AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) pfac.coFac;
086 AlgebraicNumber<C> ldcf = P.leadingBaseCoefficient();
087 if (!ldcf.isONE()) {
088 P = P.monic();
089 factors.add(pfac.getONE().multiply(ldcf));
090 }
091 //System.out.println("\nP = " + P);
092 if (false && debug) {
093 Squarefree<AlgebraicNumber<C>> sqengine = SquarefreeFactory.<AlgebraicNumber<C>> getImplementation(afac);
094 if ( !sqengine.isSquarefree(P) ) {
095 throw new RuntimeException("P not squarefree: " + sqengine.squarefreeFactors(P));
096 }
097 GenPolynomial<C> modu = afac.modul;
098 if ( !factorCoeff.isIrreducible(modu) ) {
099 throw new RuntimeException("modul not irreducible: " + factorCoeff.factors(modu));
100 }
101 System.out.println("P squarefree and modul irreducible");
102 //GreatestCommonDivisor<AlgebraicNumber<C>> aengine //= GCDFactory.<AlgebraicNumber<C>> getProxy(afac);
103 // = new GreatestCommonDivisorSimple<AlgebraicNumber<C>>( /*cfac.coFac*/ );
104 }
105
106 // search squarefree norm
107 long k = 0L;
108 long ks = k;
109 GenPolynomial<C> res = null;
110 boolean sqf = false;
111 //int[] klist = new int[]{ 0, 1, 2, 3, -1, -2, -3 , 5, -5, 7, -7, 101, -101, 1001, -1001 };
112 //int[] klist = new int[]{ 0, 1, 2, 3, -1, -2, -3 , 5, -5, 7, -7, 23, -23, 167, -167 };
113 //int[] klist = new int[] { 0, -1, -2, 1, 2, -3, 3 };
114 int[] klist = new int[] { 0, -1, -2, 1, 2 };
115 int ki = 0;
116 while (!sqf) {
117 // k = 0,1,2,-1,-2
118 if (ki >= klist.length) {
119 break;
120 }
121 k = klist[ki];
122 ki++;
123 // compute norm with x -> ( y - k x )
124 ks = k;
125 res = PolyUfdUtil.<C> norm(P, ks);
126 //System.out.println("res = " + res);
127 if (res.isZERO() || res.isConstant()) {
128 continue;
129 }
130 sqf = factorCoeff.isSquarefree(res);
131 //System.out.println("sqf("+ks+") = " + res.degree());
132 //System.out.println("resfact = " + factorCoeff.baseFactors(res) + "\n");
133 }
134 // if Res is now squarefree, else must take radical factorization
135 List<GenPolynomial<C>> nfacs;
136 if (!sqf) {
137 //System.out.println("\nres = " + res);
138 System.out.println("sqf(" + ks + ") = " + res.degree());
139 //res = factorCoeff.squarefreePart(res); // better use obtained factors
140 //res = factorCoeff.baseFactors(res).lastKey();
141 }
142 //res = res.monic();
143 if (logger.isInfoEnabled()) {
144 logger.info("res = " + res);
145 //System.out.println("\nres = " + res);
146 }
147 nfacs = factorCoeff.baseFactorsRadical(res);
148 if (logger.isInfoEnabled()) {
149 logger.info("res facs = " + nfacs); // Q[X]
150 //System.out.println("\nnfacs = " + nfacs); // Q[X]
151 }
152 if (nfacs.size() == 1) {
153 factors.add(P);
154 return factors;
155 }
156
157 // compute gcds of factors with polynomial in Q(alpha)[X]
158 GenPolynomial<AlgebraicNumber<C>> Pp = P;
159 //System.out.println("Pp = " + Pp);
160 GenPolynomial<AlgebraicNumber<C>> Ni;
161 for (GenPolynomial<C> nfi : nfacs) {
162 //System.out.println("nfi = " + nfi);
163 Ni = PolyUfdUtil.<C> substituteConvertToAlgebraicCoefficients(pfac, nfi, ks);
164 if (logger.isDebugEnabled()) {
165 logger.info("Ni = " + Ni);
166 //System.out.println("Pp = " + Pp);
167 //System.out.println("Ni = " + Ni);
168 }
169 // compute gcds of factors with polynomial
170 GenPolynomial<AlgebraicNumber<C>> pni = engine.gcd(Ni, Pp);
171 if (!pni.leadingBaseCoefficient().isONE()) {
172 //System.out.println("gcd(Ni,Pp) not monic " + pni);
173 pni = pni.monic();
174 }
175 if (logger.isInfoEnabled()) {
176 logger.info("gcd(Ni,Pp) = " + pni);
177 //System.out.println("gcd(Ni,Pp) = " + pni);
178 }
179 if (!pni.isONE()) {
180 factors.add(pni);
181 Pp = Pp.divide(pni);
182 // } else {
183 // GenPolynomial<AlgebraicNumber<C>> qni = Pp.divide(Ni);
184 // GenPolynomial<AlgebraicNumber<C>> rni = Pp.remainder(Ni);
185 // System.out.println("div qni = " + qni);
186 // System.out.println("div rni = " + rni);
187 // continue;
188 // //throw new RuntimeException("gcd(Ni,Pp) == 1");
189 }
190 }
191 if (!Pp.isZERO() && !Pp.isONE()) { // irreducible rest
192 factors.add(Pp);
193 }
194 //System.out.println("afactors = " + factors);
195 return factors;
196 }
197
198 }