001/* 002 * $Id: FactorAlgebraicPrim.java 4110 2012-08-19 12:02:16Z kredel $ 003 */ 004 005package edu.jas.application; 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; 020import edu.jas.ufd.FactorAbsolute; 021import edu.jas.ufd.FactorAbstract; 022import edu.jas.ufd.PolyUfdUtil; 023import edu.jas.ufd.Squarefree; 024import edu.jas.ufd.SquarefreeFactory; 025 026 027/** 028 * Algebraic number coefficients factorization algorithms. This class 029 * implements factorization methods for polynomials over algebraic 030 * numbers over rational numbers or over (prime) modular integers. The 031 * algorithm uses zero dimensional ideal prime decomposition. 032 * @author Heinz Kredel 033 * @param <C> coefficient type 034 */ 035 036public class FactorAlgebraicPrim<C extends GcdRingElem<C>> extends FactorAbsolute<AlgebraicNumber<C>> { 037 038 039 //FactorAbstract<AlgebraicNumber<C>> 040 041 042 private static final Logger logger = Logger.getLogger(FactorAlgebraicPrim.class); 043 044 045 //private final boolean debug = logger.isInfoEnabled(); 046 047 048 /** 049 * Factorization engine for base coefficients. 050 */ 051 public final FactorAbstract<C> factorCoeff; 052 053 054 /** 055 * No argument constructor. <b>Note:</b> can't use this constructor. 056 */ 057 protected FactorAlgebraicPrim() { 058 throw new IllegalArgumentException("don't use this constructor"); 059 } 060 061 062 /** 063 * Constructor. 064 * @param fac algebraic number factory. 065 */ 066 public FactorAlgebraicPrim(AlgebraicNumberRing<C> fac) { 067 this(fac, FactorFactory.<C> getImplementation(fac.ring.coFac)); 068 } 069 070 071 /** 072 * Constructor. 073 * @param fac algebraic number factory. 074 * @param factorCoeff factorization engine for polynomials over base 075 * coefficients. 076 */ 077 public FactorAlgebraicPrim(AlgebraicNumberRing<C> fac, FactorAbstract<C> factorCoeff) { 078 super(fac); 079 this.factorCoeff = factorCoeff; 080 } 081 082 083 /** 084 * GenPolynomial base factorization of a squarefree polynomial. 085 * @param P squarefree GenPolynomial<AlgebraicNumber<C>>. 086 * @return [p_1,...,p_k] with P = prod_{i=1, ..., k} p_i. 087 */ 088 @Override 089 public List<GenPolynomial<AlgebraicNumber<C>>> baseFactorsSquarefree(GenPolynomial<AlgebraicNumber<C>> P) { 090 if (P == null) { 091 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 092 } 093 List<GenPolynomial<AlgebraicNumber<C>>> factors = new ArrayList<GenPolynomial<AlgebraicNumber<C>>>(); 094 if (P.isZERO()) { 095 return factors; 096 } 097 if (P.isONE()) { 098 factors.add(P); 099 return factors; 100 } 101 GenPolynomialRing<AlgebraicNumber<C>> pfac = P.ring; // Q(alpha)[x] 102 if (pfac.nvar > 1) { 103 throw new IllegalArgumentException("only for univariate polynomials"); 104 } 105 AlgebraicNumberRing<C> afac = (AlgebraicNumberRing<C>) pfac.coFac; 106 107 AlgebraicNumber<C> ldcf = P.leadingBaseCoefficient(); 108 if (!ldcf.isONE()) { 109 P = P.monic(); 110 factors.add(pfac.getONE().multiply(ldcf)); 111 } 112 //System.out.println("\nP = " + P); 113 if (logger.isDebugEnabled()) { 114 Squarefree<AlgebraicNumber<C>> sqengine = SquarefreeFactory 115 .<AlgebraicNumber<C>> getImplementation(afac); 116 if (!sqengine.isSquarefree(P)) { 117 throw new RuntimeException("P not squarefree: " + sqengine.squarefreeFactors(P)); 118 } 119 GenPolynomial<C> modu = afac.modul; 120 if (!factorCoeff.isIrreducible(modu)) { 121 throw new RuntimeException("modul not irreducible: " + factorCoeff.factors(modu)); 122 } 123 System.out.println("P squarefree and modul irreducible via ideal decomposition"); 124 //GreatestCommonDivisor<AlgebraicNumber<C>> aengine //= GCDFactory.<AlgebraicNumber<C>> getProxy(afac); 125 // = new GreatestCommonDivisorSimple<AlgebraicNumber<C>>( /*cfac.coFac*/ ); 126 } 127 GenPolynomial<C> agen = afac.modul; 128 GenPolynomialRing<C> cfac = afac.ring; 129 GenPolynomialRing<GenPolynomial<C>> rfac = new GenPolynomialRing<GenPolynomial<C>>(cfac, pfac); 130 TermOrder to = new TermOrder(TermOrder.INVLEX); 131 String[] vars = new String[2]; 132 vars[0] = cfac.getVars()[0]; 133 vars[1] = rfac.getVars()[0]; 134 GenPolynomialRing<C> dfac = new GenPolynomialRing<C>(cfac.coFac, to, vars); 135 // transform minimal polynomial to bi-variate polynomial 136 GenPolynomial<C> Ad = agen.extend(dfac, 0, 0L); 137 // transform to bi-variate polynomial 138 GenPolynomial<GenPolynomial<C>> Pc = PolyUtil.<C> fromAlgebraicCoefficients(rfac, P); 139 //System.out.println("Pc = " + Pc.toScript()); 140 GenPolynomial<C> Pd = PolyUtil.<C> distribute(dfac, Pc); 141 //System.out.println("Ad = " + Ad.toScript()); 142 //System.out.println("Pd = " + Pd.toScript()); 143 144 List<GenPolynomial<C>> id = new ArrayList<GenPolynomial<C>>(2); 145 id.add(Ad); 146 id.add(Pd); 147 Ideal<C> I = new Ideal<C>(dfac, id); 148 List<IdealWithUniv<C>> Iul = I.zeroDimPrimeDecomposition(); 149 //System.out.println("prime decomp = " + Iul); 150 if (Iul.size() == 1) { 151 factors.add(P); 152 return factors; 153 } 154 GenPolynomial<AlgebraicNumber<C>> f = pfac.getONE(); 155 for (IdealWithUniv<C> Iu : Iul) { 156 List<GenPolynomial<C>> pl = Iu.ideal.getList(); 157 GenPolynomial<C> ag = PolyUtil.<C> selectWithVariable(pl, 1); 158 GenPolynomial<C> pg = PolyUtil.<C> selectWithVariable(pl, 0); 159 //System.out.println("ag = " + ag.toScript()); 160 //System.out.println("pg = " + pg.toScript()); 161 if (ag.equals(Ad)) { 162 //System.out.println("found factor --------------------"); 163 GenPolynomial<GenPolynomial<C>> pgr = PolyUtil.<C> recursive(rfac, pg); 164 GenPolynomial<AlgebraicNumber<C>> pga = PolyUtil.<C> convertRecursiveToAlgebraicCoefficients( 165 pfac, pgr); 166 //System.out.println("pga = " + pga.toScript()); 167 f = f.multiply(pga); 168 factors.add(pga); 169 } else { 170 logger.warn("algebraic number mismatch: ag = " + ag + ", expected Ad = " + Ad); 171 } 172 } 173 f = f.subtract(P); 174 //System.out.println("f = " + f.toScript()); 175 if (!f.isZERO()) { 176 throw new RuntimeException("no factorization: " + f + ", factors = " + factors); 177 } 178 return factors; 179 //return new edu.jas.ufd.FactorAlgebraic<C>(afac).baseFactorsSquarefree(P); 180 } 181 182}