001/* 002 * $Id: FactorModularTest.java 4019 2012-07-22 18:31:13Z kredel $ 003 */ 004 005package edu.jas.ufd; 006 007 008import java.util.SortedMap; 009 010import junit.framework.Test; 011import junit.framework.TestCase; 012import junit.framework.TestSuite; 013 014import edu.jas.arith.ModInteger; 015import edu.jas.arith.ModIntegerRing; 016import edu.jas.arith.PrimeList; 017import edu.jas.kern.ComputerThreads; 018import edu.jas.poly.GenPolynomial; 019import edu.jas.poly.GenPolynomialRing; 020import edu.jas.poly.TermOrder; 021 022 023/** 024 * Factor modular tests with JUnit. 025 * @author Heinz Kredel. 026 */ 027 028public class FactorModularTest extends TestCase { 029 030 031 /** 032 * main. 033 */ 034 public static void main(String[] args) { 035 //BasicConfigurator.configure(); 036 junit.textui.TestRunner.run(suite()); 037 } 038 039 040 /** 041 * Constructs a <CODE>FactorModularTest</CODE> object. 042 * @param name String. 043 */ 044 public FactorModularTest(String name) { 045 super(name); 046 } 047 048 049 /** 050 */ 051 public static Test suite() { 052 TestSuite suite = new TestSuite(FactorModularTest.class); 053 return suite; 054 } 055 056 057 int rl = 3; 058 059 060 int kl = 5; 061 062 063 int ll = 5; 064 065 066 int el = 3; 067 068 069 float q = 0.3f; 070 071 072 @Override 073 protected void setUp() { 074 } 075 076 077 @Override 078 protected void tearDown() { 079 ComputerThreads.terminate(); 080 } 081 082 083 /** 084 * Test dummy for Junit. 085 * 086 */ 087 public void testDummy() { 088 } 089 090 091 /** 092 * Test modular factorization. 093 * 094 */ 095 public void testModularFactorization() { 096 097 PrimeList pl = new PrimeList(PrimeList.Range.medium); 098 TermOrder to = new TermOrder(TermOrder.INVLEX); 099 ModIntegerRing cfac = new ModIntegerRing(pl.get(3)); 100 //System.out.println("cfac = " + cfac); 101 GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(cfac, 1, to); 102 FactorModular<ModInteger> fac = new FactorModular<ModInteger>(cfac); 103 104 for (int i = 1; i < 4; i++) { 105 int facs = 0; 106 GenPolynomial<ModInteger> a = null; //pfac.random(kl,ll*(i+1),el*(i+1),q); 107 GenPolynomial<ModInteger> b = pfac.random(kl, ll * (i + 1), el * (i + 1), q); 108 GenPolynomial<ModInteger> c = pfac.random(kl, ll * (i + 1), el * (i + 1), q); 109 if (b.isZERO() || c.isZERO()) { 110 continue; 111 } 112 if (c.degree() > 0) { 113 facs++; 114 } 115 if (b.degree() > 0) { 116 facs++; 117 } 118 a = c.multiply(b); 119 if (a.isConstant()) { 120 continue; 121 } 122 a = a.monic(); 123 //System.out.println("\na = " + a); 124 //System.out.println("b = " + b); 125 //System.out.println("c = " + c); 126 127 SortedMap<GenPolynomial<ModInteger>, Long> sm = fac.baseFactors(a); 128 //System.out.println("sm = " + sm); 129 130 if (sm.size() >= facs) { 131 assertTrue("#facs < " + facs, sm.size() >= facs); 132 } else { 133 long sf = 0; 134 for (Long e : sm.values()) { 135 sf += e; 136 } 137 assertTrue("#facs < " + facs, sf >= facs); 138 } 139 140 boolean t = fac.isFactorization(a, sm); 141 //System.out.println("t = " + t); 142 assertTrue("prod(factor(a)) = a", t); 143 } 144 } 145 146 147 /** 148 * Test modular factorization example. 149 * 150 */ 151 public void testModularFactorizationExam() { 152 153 TermOrder to = new TermOrder(TermOrder.INVLEX); 154 ModIntegerRing cfac = new ModIntegerRing(7); 155 //System.out.println("cfac = " + cfac); 156 String[] vars = new String[] { "x" }; 157 GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(cfac, 1, to, vars); 158 FactorModular<ModInteger> fac = new FactorModular<ModInteger>(cfac); 159 160 int facs = 3; 161 GenPolynomial<ModInteger> a = pfac.parse("(x^12+5)"); 162 a = a.monic(); 163 //System.out.println("\na = " + a); 164 165 SortedMap<GenPolynomial<ModInteger>, Long> sm = fac.baseFactors(a); 166 //System.out.println("sm = " + sm); 167 168 if (sm.size() >= facs) { 169 assertTrue("#facs < " + facs, sm.size() >= facs); 170 } else { 171 long sf = 0; 172 for (Long e : sm.values()) { 173 sf += e; 174 } 175 assertTrue("#facs < " + facs, sf >= facs); 176 } 177 178 boolean t = fac.isFactorization(a, sm); 179 //System.out.println("t = " + t); 180 assertTrue("prod(factor(a)) = a", t); 181 } 182 183 184 /** 185 * Test modular factorization, case p = 2. 186 * 187 */ 188 public void testModular2Factorization() { 189 190 TermOrder to = new TermOrder(TermOrder.INVLEX); 191 ModIntegerRing cfac = new ModIntegerRing(2L); 192 //System.out.println("cfac = " + cfac); 193 GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(cfac, 1, to); 194 FactorModular<ModInteger> fac = new FactorModular<ModInteger>(cfac); 195 196 for (int i = 1; i < 4; i++) { 197 int facs = 0; 198 GenPolynomial<ModInteger> a = null; //pfac.random(kl,ll*(i+1),el*(i+1),q); 199 GenPolynomial<ModInteger> b = pfac.random(kl, ll * (i + 1), el * (i + 1), q); 200 GenPolynomial<ModInteger> c = pfac.random(kl, ll * (i + 1), el * (i + 1), q); 201 if (b.isZERO() || c.isZERO()) { 202 continue; 203 } 204 if (c.degree() > 0) { 205 facs++; 206 } 207 if (b.degree() > 0) { 208 facs++; 209 } 210 a = c.multiply(b); 211 if (a.isConstant()) { 212 continue; 213 } 214 a = a.monic(); 215 //System.out.println("\na = " + a); 216 //System.out.println("b = " + b); 217 //System.out.println("c = " + c); 218 219 SortedMap<GenPolynomial<ModInteger>, Long> sm = fac.baseFactors(a); 220 //System.out.println("sm = " + sm); 221 222 if (sm.size() >= facs) { 223 assertTrue("#facs < " + facs, sm.size() >= facs); 224 } else { 225 long sf = 0; 226 for (Long e : sm.values()) { 227 sf += e; 228 } 229 assertTrue("#facs < " + facs, sf >= facs); 230 } 231 232 boolean t = fac.isFactorization(a, sm); 233 //System.out.println("t = " + t); 234 assertTrue("prod(factor(a)) = a", t); 235 } 236 } 237 238 239 /** 240 * Test multivariate modular factorization. 241 * 242 */ 243 public void testMultivariateModularFactorization() { 244 245 //PrimeList pl = new PrimeList(PrimeList.Range.small); 246 TermOrder to = new TermOrder(TermOrder.INVLEX); 247 ModIntegerRing cfac = new ModIntegerRing(13); // pl.get(3), 7, 11, 13 248 GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(cfac, rl, to); 249 FactorModular<ModInteger> fac = new FactorModular<ModInteger>(cfac); 250 251 for (int i = 1; i < 2; i++) { 252 int facs = 0; 253 GenPolynomial<ModInteger> a = null; //pfac.random(kl,ll*(i+1),el,q); 254 GenPolynomial<ModInteger> b = pfac.random(kl, 2, el, q); 255 GenPolynomial<ModInteger> c = pfac.random(kl, 2, el, q); 256 if (b.isZERO() || c.isZERO()) { 257 continue; 258 } 259 if (c.degree() > 0) { 260 facs++; 261 } 262 if (b.degree() > 0) { 263 facs++; 264 } 265 a = c.multiply(b); 266 if (a.isConstant()) { 267 continue; 268 } 269 //a = a.monic(); 270 //System.out.println("\na = " + a); 271 //System.out.println("b = " + b); 272 //System.out.println("c = " + c); 273 274 SortedMap<GenPolynomial<ModInteger>, Long> sm = fac.factors(a); 275 //System.out.println("sm = " + sm); 276 277 if (sm.size() >= facs) { 278 assertTrue("#facs < " + facs, sm.size() >= facs); 279 } else { 280 long sf = 0; 281 for (Long e : sm.values()) { 282 sf += e; 283 } 284 assertTrue("#facs < " + facs, sf >= facs); 285 } 286 287 boolean t = fac.isFactorization(a, sm); 288 //System.out.println("t = " + t); 289 assertTrue("prod(factor(a)) = a", t); 290 } 291 } 292 293 294 /** 295 * Test modular absolute factorization. 296 * 297 */ 298 public void testBaseModularAbsoluteFactorization() { 299 300 TermOrder to = new TermOrder(TermOrder.INVLEX); 301 ModIntegerRing cfac = new ModIntegerRing(17); 302 String[] alpha = new String[] { "alpha" }; 303 //String[] vars = new String[] { "z" }; 304 GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(cfac, 1, to, alpha); 305 GenPolynomial<ModInteger> agen = pfac.univariate(0, 4); 306 agen = agen.sum(pfac.fromInteger(1)); // x^4 + 1 307 308 FactorModular<ModInteger> engine = new FactorModular<ModInteger>(cfac); 309 310 FactorsMap<ModInteger> F 311 //= engine.baseFactorsAbsoluteSquarefree(agen); 312 //= engine.baseFactorsAbsoluteIrreducible(agen); 313 = engine.baseFactorsAbsolute(agen); 314 //System.out.println("agen = " + agen); 315 //System.out.println("F = " + F); 316 317 boolean t = engine.isAbsoluteFactorization(F); 318 //System.out.println("t = " + t); 319 assertTrue("prod(factor(a)) = a", t); 320 } 321 322}