001/* 002 * $Id: FactorModular.java 4965 2014-10-17 20:07:51Z kredel $ 003 */ 004 005package edu.jas.ufd; 006 007 008import java.util.ArrayList; 009import java.util.List; 010import java.util.Map; 011import java.util.SortedMap; 012import java.util.SortedSet; 013import java.util.TreeMap; 014import java.util.TreeSet; 015 016import org.apache.log4j.Logger; 017 018import edu.jas.arith.BigInteger; 019import edu.jas.arith.ModLongRing; 020import edu.jas.arith.Modular; 021import edu.jas.arith.ModularRingFactory; 022import edu.jas.poly.GenPolynomial; 023import edu.jas.poly.GenPolynomialRing; 024import edu.jas.poly.PolyUtil; 025import edu.jas.structure.GcdRingElem; 026import edu.jas.structure.Power; 027import edu.jas.structure.RingFactory; 028 029 030/** 031 * Modular coefficients factorization algorithms. This class implements 032 * factorization methods for polynomials over (prime) modular integers. 033 * @author Heinz Kredel 034 */ 035 036public class FactorModular<MOD extends GcdRingElem<MOD> & Modular> extends FactorAbsolute<MOD> { 037 038 039 private static final Logger logger = Logger.getLogger(FactorModular.class); 040 041 042 private final boolean debug = logger.isDebugEnabled(); 043 044 045 /** 046 * No argument constructor, do not use. 047 */ 048 @SuppressWarnings({ "cast", "unused" }) 049 private FactorModular() { 050 this((RingFactory<MOD>) (Object) new ModLongRing(13, true)); // hack, 13 unimportant 051 } 052 053 054 /** 055 * Constructor. 056 * @param cfac coefficient ring factory. 057 */ 058 public FactorModular(RingFactory<MOD> cfac) { 059 super(cfac); 060 } 061 062 063 /** 064 * GenPolynomial base distinct degree factorization. 065 * @param P squarefree and monic GenPolynomial. 066 * @return [e_1 -> p_1, ..., e_k -> p_k] with P = prod_{i=1,...,k} p_i 067 * and p_i has only irreducible factors of degree e_i. 068 */ 069 public SortedMap<Long, GenPolynomial<MOD>> baseDistinctDegreeFactors(GenPolynomial<MOD> P) { 070 if (P == null) { 071 throw new IllegalArgumentException(this.getClass().getName() + " P != null"); 072 } 073 SortedMap<Long, GenPolynomial<MOD>> facs = new TreeMap<Long, GenPolynomial<MOD>>(); 074 if (P.isZERO()) { 075 return facs; 076 } 077 GenPolynomialRing<MOD> pfac = P.ring; 078 if (pfac.nvar > 1) { 079 throw new IllegalArgumentException(this.getClass().getName() + " only for univariate polynomials"); 080 } 081 ModularRingFactory<MOD> mr = (ModularRingFactory<MOD>) pfac.coFac; 082 java.math.BigInteger m = mr.getIntegerModul().getVal(); 083 //if (m.longValue() == 2L) { 084 // logger.warn(this.getClass().getName() + " case p = 2 not implemented"); 085 //} 086 GenPolynomial<MOD> x = pfac.univariate(0); 087 GenPolynomial<MOD> h = x; 088 GenPolynomial<MOD> f = P; 089 GenPolynomial<MOD> g; 090 Power<GenPolynomial<MOD>> pow = new Power<GenPolynomial<MOD>>(pfac); 091 long d = 0; 092 while (d + 1 <= f.degree(0) / 2) { 093 d++; 094 h = pow.modPower(h, m, f); 095 g = engine.gcd(h.subtract(x), f); 096 if (!g.isONE()) { 097 facs.put(d, g); 098 f = f.divide(g); 099 } 100 } 101 if (!f.isONE()) { 102 d = f.degree(0); 103 facs.put(d, f); 104 } 105 return facs; 106 } 107 108 109 /** 110 * GenPolynomial base equal degree factorization. 111 * @param P squarefree and monic GenPolynomial. 112 * @param deg such that P has only irreducible factors of degree deg. 113 * @return [p_1,...,p_k] with P = prod_{i=1,...,r} p_i. 114 */ 115 public List<GenPolynomial<MOD>> baseEqualDegreeFactors(GenPolynomial<MOD> P, long deg) { 116 if (P == null) { 117 throw new IllegalArgumentException(this.getClass().getName() + " P != null"); 118 } 119 List<GenPolynomial<MOD>> facs = new ArrayList<GenPolynomial<MOD>>(); 120 if (P.isZERO()) { 121 return facs; 122 } 123 GenPolynomialRing<MOD> pfac = P.ring; 124 if (pfac.nvar > 1) { 125 throw new IllegalArgumentException(this.getClass().getName() + " only for univariate polynomials"); 126 } 127 if (P.degree(0) == deg) { 128 facs.add(P); 129 return facs; 130 } 131 ModularRingFactory<MOD> mr = (ModularRingFactory<MOD>) pfac.coFac; 132 java.math.BigInteger m = mr.getIntegerModul().getVal(); 133 //System.out.println("m = " + m); 134 boolean p2 = false; 135 if (m.equals(java.math.BigInteger.valueOf(2L))) { 136 p2 = true; 137 //throw new RuntimeException(this.getClass().getName() + " case p = 2 not implemented"); 138 } 139 GenPolynomial<MOD> one = pfac.getONE(); 140 GenPolynomial<MOD> t = pfac.univariate(0, 1L); 141 GenPolynomial<MOD> r; 142 GenPolynomial<MOD> h; 143 GenPolynomial<MOD> f = P; 144 //GreatestCommonDivisor<MOD> engine = GCDFactory.<MOD> getImplementation(pfac.coFac); 145 Power<GenPolynomial<MOD>> pow = new Power<GenPolynomial<MOD>>(pfac); 146 GenPolynomial<MOD> g = null; 147 int degi = (int) deg; //f.degree(0); 148 //System.out.println("deg = " + deg); 149 BigInteger di = Power.<BigInteger> positivePower(new BigInteger(m), deg); 150 //System.out.println("di = " + di); 151 java.math.BigInteger d = di.getVal(); //.longValue()-1; 152 //System.out.println("d = " + d); 153 d = d.shiftRight(1); // divide by 2 154 do { 155 if (p2) { 156 h = t; 157 for (int i = 1; i < degi; i++) { 158 h = t.sum(h.multiply(h)); 159 h = h.remainder(f); 160 } 161 t = t.multiply(pfac.univariate(0, 2L)); 162 //System.out.println("h = " + h); 163 } else { 164 r = pfac.random(17, degi, 2 * degi, 1.0f); 165 if (r.degree(0) >= f.degree(0)) { 166 r = r.remainder(f); 167 } 168 r = r.monic(); 169 //System.out.println("r = " + r); 170 h = pow.modPower(r, d, f).subtract(one); 171 degi++; 172 } 173 g = engine.gcd(h, f); 174 //System.out.println("g = " + g); 175 } while (g.degree(0) == 0 || g.degree(0) == f.degree(0)); 176 f = f.divide(g); 177 facs.addAll(baseEqualDegreeFactors(f, deg)); 178 facs.addAll(baseEqualDegreeFactors(g, deg)); 179 return facs; 180 } 181 182 183 /** 184 * GenPolynomial base factorization of a squarefree polynomial. 185 * @param P squarefree and monic! GenPolynomial. 186 * @return [p_1,...,p_k] with P = prod_{i=1,...,r} p_i. 187 */ 188 @Override 189 public List<GenPolynomial<MOD>> baseFactorsSquarefree(GenPolynomial<MOD> P) { 190 if (P == null) { 191 throw new IllegalArgumentException(this.getClass().getName() + " P == null"); 192 } 193 List<GenPolynomial<MOD>> factors = new ArrayList<GenPolynomial<MOD>>(); 194 if (P.isZERO()) { 195 return factors; 196 } 197 if (P.isONE()) { 198 factors.add(P); 199 return factors; 200 } 201 GenPolynomialRing<MOD> pfac = P.ring; 202 if (pfac.nvar > 1) { 203 throw new IllegalArgumentException(this.getClass().getName() + " only for univariate polynomials"); 204 } 205 if (!P.leadingBaseCoefficient().isONE()) { 206 throw new IllegalArgumentException("ldcf(P) != 1: " + P); 207 } 208 SortedMap<Long, GenPolynomial<MOD>> dfacs = baseDistinctDegreeFactors(P); 209 if (debug) { 210 logger.info("dfacs = " + dfacs); 211 //System.out.println("dfacs = " + dfacs); 212 } 213 for (Map.Entry<Long, GenPolynomial<MOD>> me : dfacs.entrySet()) { 214 Long e = me.getKey(); 215 GenPolynomial<MOD> f = me.getValue(); // dfacs.get(e); 216 List<GenPolynomial<MOD>> efacs = baseEqualDegreeFactors(f, e); 217 if (debug) { 218 logger.info("efacs " + e + " = " + efacs); 219 //System.out.println("efacs " + e + " = " + efacs); 220 } 221 factors.addAll(efacs); 222 } 223 //System.out.println("factors = " + factors); 224 factors = PolyUtil.<MOD> monic(factors); 225 SortedSet<GenPolynomial<MOD>> ss = new TreeSet<GenPolynomial<MOD>>(factors); 226 //System.out.println("sorted = " + ss); 227 factors.clear(); 228 factors.addAll(ss); 229 return factors; 230 } 231 232}