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