001/* 002 * $Id$ 003 */ 004 005package edu.jas.ufd; 006 007 008import java.util.ArrayList; 009import java.util.List; 010import java.util.SortedMap; 011 012import edu.jas.arith.BigInteger; 013import edu.jas.arith.BigRational; 014import edu.jas.arith.ModInt; 015import edu.jas.arith.ModIntRing; 016import edu.jas.arith.ModInteger; 017import edu.jas.arith.ModIntegerRing; 018import edu.jas.arith.ModLong; 019import edu.jas.arith.ModLongRing; 020import edu.jas.kern.ComputerThreads; 021import edu.jas.poly.AlgebraicNumber; 022import edu.jas.poly.AlgebraicNumberRing; 023import edu.jas.poly.GenPolynomial; 024import edu.jas.poly.GenPolynomialRing; 025import edu.jas.poly.PolyUtil; 026import edu.jas.poly.TermOrder; 027import edu.jas.poly.TermOrderByName; 028import edu.jas.ps.UnivPowerSeries; 029import edu.jas.ps.UnivPowerSeriesRing; 030import edu.jas.structure.Power; 031import edu.jas.vector.GenMatrix; 032import edu.jas.vector.GenMatrixRing; 033import edu.jas.vector.GenVector; 034import edu.jas.vector.LinAlg; 035 036import junit.framework.Test; 037import junit.framework.TestCase; 038import junit.framework.TestSuite; 039 040 041/** 042 * PolyUfdUtil tests with JUnit. 043 * @author Heinz Kredel 044 */ 045 046public class PolyUfdUtilTest extends TestCase { 047 048 049 /** 050 * main. 051 */ 052 public static void main(String[] args) { 053 junit.textui.TestRunner.run(suite()); 054 ComputerThreads.terminate(); 055 } 056 057 058 /** 059 * Constructs a <CODE>PolyUtilTest</CODE> object. 060 * @param name String. 061 */ 062 public PolyUfdUtilTest(String name) { 063 super(name); 064 } 065 066 067 /** 068 */ 069 public static Test suite() { 070 TestSuite suite = new TestSuite(PolyUfdUtilTest.class); 071 return suite; 072 } 073 074 075 TermOrder to = TermOrderByName.INVLEX; 076 077 078 GenPolynomialRing<BigInteger> dfac; 079 080 081 GenPolynomialRing<BigInteger> cfac; 082 083 084 GenPolynomialRing<GenPolynomial<BigInteger>> rfac; 085 086 087 BigInteger ai, bi, ci, di, ei; 088 089 090 GenPolynomial<BigInteger> a, b, c, d, e; 091 092 093 GenPolynomial<GenPolynomial<BigInteger>> ar, br, cr, dr, er; 094 095 096 GenPolynomialRing<BigRational> crfac; 097 098 099 GenPolynomialRing<GenPolynomial<BigRational>> rrfac; 100 101 102 GenPolynomial<GenPolynomial<BigRational>> arr, brr, crr, drr, err, frr; 103 104 105 int rl = 5; 106 107 108 int kl = 5; 109 110 111 int ll = 5; 112 113 114 int el = 3; 115 116 117 float q = 0.3f; 118 119 120 @Override 121 protected void setUp() { 122 a = b = c = d = e = null; 123 ai = bi = ci = di = ei = null; 124 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl, to); 125 cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl - 1, to); 126 rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, to); 127 } 128 129 130 @Override 131 protected void tearDown() { 132 a = b = c = d = e = null; 133 ai = bi = ci = di = ei = null; 134 dfac = null; 135 cfac = null; 136 rfac = null; 137 ComputerThreads.terminate(); 138 } 139 140 141 protected static java.math.BigInteger getPrime1() { 142 long prime = 2; //2^60-93; // 2^30-35; //19; knuth (2,390) 143 for (int i = 1; i < 60; i++) { 144 prime *= 2; 145 } 146 prime -= 93; 147 //prime = 37; 148 //System.out.println("p1 = " + prime); 149 return new java.math.BigInteger("" + prime); 150 } 151 152 153 protected static java.math.BigInteger getPrime2() { 154 long prime = 2; //2^60-93; // 2^30-35; //19; knuth (2,390) 155 for (int i = 1; i < 30; i++) { 156 prime *= 2; 157 } 158 prime -= 35; 159 //prime = 19; 160 //System.out.println("p1 = " + prime); 161 return new java.math.BigInteger("" + prime); 162 } 163 164 165 /** 166 * Test Kronecker substitution. 167 */ 168 public void testKroneckerSubstitution() { 169 for (int i = 0; i < 10; i++) { 170 a = dfac.random(kl, ll * 2, el * 5, q); 171 long d = a.degree() + 1L; 172 //System.out.println("\na = " + a); 173 //System.out.println("deg(a)+1 = " + d); 174 175 b = PolyUfdUtil.<BigInteger> substituteKronecker(a, d); 176 //System.out.println("b = " + b); 177 178 c = PolyUfdUtil.<BigInteger> backSubstituteKronecker(dfac, b, d); 179 //System.out.println("c = " + c); 180 e = a.subtract(c); 181 //System.out.println("e = " + e); 182 assertTrue("back(subst(a)) = a", e.isZERO()); 183 } 184 } 185 186 187 /** 188 * Test algebraic number field. 189 */ 190 public void testAlgebraicNumberField() { 191 int deg = 11; 192 // characteristic non zero, small 193 ModLongRing gfp = new ModLongRing(32003); 194 //System.out.println("gfp = " + gfp.toScript()); 195 AlgebraicNumberRing<ModLong> gfpq = PolyUfdUtil.<ModLong> algebraicNumberField(gfp, deg); 196 //System.out.println("gfpq = " + gfpq.toScript()); 197 assertTrue("gfpq.isField: ", gfpq.isField()); 198 199 // characteristic non zero, large 200 ModIntegerRing gfP = new ModIntegerRing(getPrime1()); 201 //System.out.println("gfP = " + gfP.toScript()); 202 AlgebraicNumberRing<ModInteger> gfPq = PolyUfdUtil.<ModInteger> algebraicNumberField(gfP, deg); 203 //System.out.println("gfPq = " + gfPq.toScript()); 204 assertTrue("gfPq.isField: ", gfPq.isField()); 205 206 // characteristic zero 207 BigRational q = BigRational.ONE; 208 //System.out.println("q = " + q.toScriptFactory()); 209 AlgebraicNumberRing<BigRational> gfqq = PolyUfdUtil.<BigRational> algebraicNumberField(q, deg); 210 //System.out.println("gfqq = " + gfqq.toScript()); 211 assertTrue("gfqq.isField: ", gfqq.isField()); 212 213 //PolyUfdUtil.<BigRational> ensureFieldProperty(gfqq); 214 //System.out.println("gfqq = " + gfqq); 215 //assertTrue("gfqq.isField: ", gfqq.isField()); 216 } 217 218 219 /** 220 * Test recursive dense pseudo division. 221 */ 222 public void testRecursivePseudoDivisionDense() { 223 String[] cnames = new String[] { "x" }; 224 String[] mnames = new String[] { "t" }; 225 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), to, cnames); 226 //GenPolynomialRing<BigRational> rdfac = new GenPolynomialRing<BigRational>(new BigRational(1),dfac); 227 rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(dfac, to, mnames); 228 QuotientRing<BigInteger> qfac = new QuotientRing<BigInteger>(dfac); 229 GenPolynomialRing<Quotient<BigInteger>> rqfac = new GenPolynomialRing<Quotient<BigInteger>>(qfac, 230 rfac); 231 //System.out.println("\ndfac = " + dfac); 232 //System.out.println("rdfac = " + rdfac); 233 //System.out.println("rfac = " + rfac); 234 //System.out.println("qfac = " + qfac); 235 //System.out.println("rqfac = " + rqfac); 236 237 ar = rfac.random(kl, 2 * ll, el + 4, q); 238 //ar = rfac.parse(" ( -2 x^4 + 8 x^3 - 5 x^2 - x + 6 ) t^3 + ( 2 x - 8 ) t^2 - ( 13 x^4 - 13 x^3 + x^2 + 2 x - 13 ) "); 239 br = rfac.random(kl, 2 * ll, el + 2, q); 240 //ar = ar.multiply(br); 241 //br = rfac.parse(" ( 13 ) t^3 + ( 3 x^2 - 6 ) t - ( 13 x^4 - 8 x^3 + 10 x^2 + 22 x + 21 ) "); 242 //System.out.println("ar = " + ar); 243 //System.out.println("br = " + br); 244 245 dr = PolyUtil.<BigInteger> recursivePseudoDivide(ar, br); 246 //System.out.println("qr = " + dr); 247 cr = PolyUtil.<BigInteger> recursiveDensePseudoRemainder(ar, br); 248 //System.out.println("rr = " + cr); 249 250 //boolean t = PolyUtil.<BigInteger> isRecursivePseudoQuotientRemainder(ar, br, dr, cr); 251 //System.out.println("assertTrue lc^n a = q b + r: " + t); 252 //assertTrue("lc^n a = q b + r: " + cr, t); // ?? not always true 253 254 GenPolynomial<Quotient<BigInteger>> ap = PolyUfdUtil 255 .<BigInteger> quotientFromIntegralCoefficients(rqfac, ar); 256 GenPolynomial<Quotient<BigInteger>> bp = PolyUfdUtil 257 .<BigInteger> quotientFromIntegralCoefficients(rqfac, br); 258 GenPolynomial<Quotient<BigInteger>> cp = PolyUfdUtil 259 .<BigInteger> quotientFromIntegralCoefficients(rqfac, cr); 260 GenPolynomial<Quotient<BigInteger>> dp = PolyUfdUtil 261 .<BigInteger> quotientFromIntegralCoefficients(rqfac, dr); 262 //System.out.println("ap = " + ap); 263 //System.out.println("bp = " + bp); 264 //System.out.println("cp = " + cp); 265 ////System.out.println("dp = " + dp); 266 //System.out.println("dp = " + dp.monic()); 267 268 GenPolynomial<Quotient<BigInteger>> qp = ap.divide(bp); 269 GenPolynomial<Quotient<BigInteger>> rp = ap.remainder(bp); 270 ////System.out.println("qp = " + qp); 271 //System.out.println("qp = " + qp.monic()); 272 //System.out.println("rp = " + rp); 273 GenPolynomial<Quotient<BigInteger>> rhs = qp.multiply(bp).sum(rp); 274 //System.out.println("qp bp + rp = " + rhs); 275 276 assertEquals("ap = qp bp + rp: ", ap, rhs); 277 278 assertEquals("cp = rp: ", rp.monic(), cp.monic()); 279 //System.out.println("dp = qp: " + qp.monic().equals(dp.monic()) ); 280 assertEquals("dp = qp: ", qp.monic(), dp.monic()); // ?? 281 } 282 283 284 /** 285 * Test recursive sparse pseudo division. 286 */ 287 public void testRecursivePseudoDivisionSparse() { 288 String[] cnames = new String[] { "x" }; 289 String[] mnames = new String[] { "t" }; 290 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), to, cnames); 291 //GenPolynomialRing<BigRational> rdfac = new GenPolynomialRing<BigRational>(new BigRational(1),dfac); 292 rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(dfac, to, mnames); 293 QuotientRing<BigInteger> qfac = new QuotientRing<BigInteger>(dfac); 294 GenPolynomialRing<Quotient<BigInteger>> rqfac = new GenPolynomialRing<Quotient<BigInteger>>(qfac, 295 rfac); 296 //System.out.println("\ndfac = " + dfac); 297 //System.out.println("rdfac = " + rdfac); 298 //System.out.println("rfac = " + rfac); 299 //System.out.println("qfac = " + qfac); 300 //System.out.println("rqfac = " + rqfac); 301 302 ar = rfac.random(kl, 2 * ll, el + 4, q); 303 //ar = rfac.parse(" ( -2 x^4 + 8 x^3 - 5 x^2 - x + 6 ) t^3 + ( 2 x - 8 ) t^2 - ( 13 x^4 - 13 x^3 + x^2 + 2 x - 13 ) "); 304 br = rfac.random(kl, 2 * ll, el + 2, q); 305 //ar = ar.multiply(br); 306 //br = rfac.parse(" ( 13 ) t^3 + ( 3 x^2 - 6 ) t - ( 13 x^4 - 8 x^3 + 10 x^2 + 22 x + 21 ) "); 307 //System.out.println("ar = " + ar); 308 //System.out.println("br = " + br); 309 310 dr = PolyUtil.<BigInteger> recursivePseudoDivide(ar, br); 311 //System.out.println("qr = " + dr); 312 cr = PolyUtil.<BigInteger> recursiveSparsePseudoRemainder(ar, br); 313 //System.out.println("rr = " + cr); 314 315 boolean t = PolyUtil.<BigInteger> isRecursivePseudoQuotientRemainder(ar, br, dr, cr); 316 //System.out.println("assertTrue lc^n a = q b + r: " + t); 317 assertTrue("lc^n a = q b + r: " + dr + "*b + " + cr, t); // not always true, some what fixed 318 319 GenPolynomial<Quotient<BigInteger>> ap = PolyUfdUtil 320 .<BigInteger> quotientFromIntegralCoefficients(rqfac, ar); 321 GenPolynomial<Quotient<BigInteger>> bp = PolyUfdUtil 322 .<BigInteger> quotientFromIntegralCoefficients(rqfac, br); 323 GenPolynomial<Quotient<BigInteger>> cp = PolyUfdUtil 324 .<BigInteger> quotientFromIntegralCoefficients(rqfac, cr); 325 GenPolynomial<Quotient<BigInteger>> dp = PolyUfdUtil 326 .<BigInteger> quotientFromIntegralCoefficients(rqfac, dr); 327 //System.out.println("ap = " + ap); 328 //System.out.println("bp = " + bp); 329 //System.out.println("cp = " + cp); 330 ////System.out.println("dp = " + dp); 331 //System.out.println("dp = " + dp.monic()); 332 333 GenPolynomial<Quotient<BigInteger>> qp = ap.divide(bp); 334 GenPolynomial<Quotient<BigInteger>> rp = ap.remainder(bp); 335 ////System.out.println("qp = " + qp); 336 //System.out.println("qp = " + qp.monic()); 337 //System.out.println("rp = " + rp); 338 GenPolynomial<Quotient<BigInteger>> rhs = qp.multiply(bp).sum(rp); 339 //System.out.println("qp bp + rp = " + rhs); 340 341 assertEquals("ap = qp bp + rp: ", ap, rhs); 342 343 //System.out.println("cp = rp: rp_m = " + rp.monic() + ", cp_m = " + cp.monic()); 344 assertEquals("cp = rp: ", rp.monic(), cp.monic()); 345 //System.out.println("dp = qp: " + qp.monic().equals(dp.monic()) ); 346 //System.out.println("qp = dp: qp_m = " + qp.monic() + ", dp_m = " + dp.monic()); 347 assertEquals("dp = qp: ", qp.monic(), dp.monic()); // ?? 348 } 349 350 351 /** 352 * Test integer from rational coefficients, recursive. 353 */ 354 public void testRecursiveIntegerFromRationalCoefficients() { 355 crfac = new GenPolynomialRing<BigRational>(new BigRational(1), cfac); 356 rrfac = new GenPolynomialRing<GenPolynomial<BigRational>>(crfac, rfac); 357 //System.out.println("\ncfac = " + cfac); 358 //System.out.println("crfac = " + crfac); 359 //System.out.println("rfac = " + rfac); 360 //System.out.println("rrfac = " + rrfac); 361 362 // BigRational 363 arr = rrfac.random(kl * kl, 2 * ll, el + 4, q); 364 arr = arr.sum(arr).multiply(arr); //rrfac.fromInteger(11)); 365 //System.out.println("arr = " + arr); 366 367 // BigInteger 368 ar = PolyUfdUtil.integerFromRationalCoefficients(rfac, arr); 369 //System.out.println("ar = " + ar); 370 371 crr = PolyUtil.<BigRational> monic(arr); 372 //System.out.println("crr = " + crr); 373 374 // BigRational 375 err = PolyUfdUtil.<BigRational> fromIntegerCoefficients(rrfac, ar); 376 //System.out.println("err = " + err); 377 err = PolyUtil.<BigRational> monic(err); 378 //System.out.println("err = " + err); 379 380 assertEquals("crr != err: ", crr, err); 381 } 382 383 384 /** 385 * Test norm over algebraic number field. 386 */ 387 public void testNormAlgebraicNumberField() { 388 int deg = 5; 389 // characteristic zero 390 BigRational q = BigRational.ONE; 391 //System.out.println("q = " + q.toScriptFactory()); 392 AlgebraicNumberRing<BigRational> gfqq = PolyUfdUtil.<BigRational> algebraicNumberField(q, deg); 393 //System.out.println("gfqq = " + gfqq.toScript()); 394 assertTrue("gfqq.isField: ", gfqq.isField()); 395 396 GenPolynomialRing<AlgebraicNumber<BigRational>> pafac; 397 pafac = new GenPolynomialRing<AlgebraicNumber<BigRational>>(gfqq, new String[] { "x" }, 398 TermOrderByName.INVLEX); 399 //System.out.println("pafac = " + pafac.toScript()); 400 401 GenPolynomial<AlgebraicNumber<BigRational>> P, Q, R; 402 P = pafac.random(2, 4, 3, 0.4f).monic(); 403 Q = pafac.random(2, 4, 3, 0.4f).monic(); 404 R = P.multiply(Q); 405 //System.out.println("P = " + P); 406 //System.out.println("Q = " + Q); 407 //System.out.println("R = " + R); 408 409 GenPolynomial<BigRational> nP, nQ, nR, nPQ, rem, gcd; 410 nP = PolyUfdUtil.<BigRational> norm(P); 411 nQ = PolyUfdUtil.<BigRational> norm(Q); 412 nR = PolyUfdUtil.<BigRational> norm(R); 413 nPQ = nP.multiply(nQ); 414 //System.out.println("normP = " + nP); 415 //System.out.println("normQ = " + nQ); 416 //System.out.println("normR = " + nR); 417 //System.out.println("normPQ = " + nPQ); 418 419 //System.out.println("normP*normQ = norm(P*Q): " + nPQ.equals(nR) + "\n"); 420 if (nPQ.equals(nR)) { 421 assertEquals("normP*normQ == norm(P*Q)", nPQ, nR); 422 return; 423 } 424 rem = nR.remainder(nPQ); 425 //System.out.println("norm(P*Q) mod normP*normQ == 0: " + rem.isZERO()); 426 if (rem.isZERO()) { 427 assertTrue("norm(P*Q) mod normP*normQ == 0", rem.isZERO()); 428 return; 429 } 430 431 GreatestCommonDivisorAbstract<BigRational> gcdr = GCDFactory.getImplementation(q); 432 gcd = gcdr.gcd(nPQ, nR); 433 //System.out.println("gcd(norm(P*Q), normP*normQ) != 1: " + (!gcd.isONE())); 434 if (!gcd.isONE()) { 435 assertFalse("gcd(norm(P*Q), normP*normQ) != 1", gcd.isONE()); 436 return; 437 } 438 // unreachable: 439 FactorAbstract<BigRational> facr = FactorFactory.getImplementation(q); 440 SortedMap<GenPolynomial<BigRational>, Long> fnPQ = facr.factors(nPQ); 441 System.out.println("fnPQ = " + fnPQ); 442 SortedMap<GenPolynomial<BigRational>, Long> fnR = facr.factors(nR); 443 System.out.println("fnR = " + fnR); 444 } 445 446 447 /** 448 * Test multivariate norm over algebraic number field. 449 */ 450 public void testMultiNormAlgebraicNumberField() { 451 int deg = 5; 452 // characteristic zero 453 BigRational q = BigRational.ONE; 454 //System.out.println("q = " + q.toScriptFactory()); 455 AlgebraicNumberRing<BigRational> gfqq = PolyUfdUtil.<BigRational> algebraicNumberField(q, deg); 456 //System.out.println("gfqq = " + gfqq.toScript()); 457 assertTrue("gfqq.isField: ", gfqq.isField()); 458 459 GenPolynomialRing<AlgebraicNumber<BigRational>> pafac; 460 pafac = new GenPolynomialRing<AlgebraicNumber<BigRational>>(gfqq, new String[] { "x", "y" }, 461 TermOrderByName.INVLEX); 462 //System.out.println("pafac = " + pafac.toScript()); 463 464 GenPolynomial<AlgebraicNumber<BigRational>> P, Q, R; 465 P = pafac.random(2, 4, 2, 0.2f).monic(); 466 Q = pafac.random(2, 4, 2, 0.2f).monic(); 467 R = P.multiply(Q); 468 //System.out.println("P = " + P); 469 //System.out.println("Q = " + Q); 470 //System.out.println("R = " + R); 471 472 GenPolynomial<BigRational> nP, nQ, nR, nPQ, rem, gcd; 473 nP = PolyUfdUtil.<BigRational> norm(P); 474 nQ = PolyUfdUtil.<BigRational> norm(Q); 475 nR = PolyUfdUtil.<BigRational> norm(R); 476 nPQ = nP.multiply(nQ); 477 //System.out.println("normP = " + nP); 478 //System.out.println("normQ = " + nQ); 479 //System.out.println("normR = " + nR); 480 //System.out.println("normPQ = " + nPQ); 481 482 //System.out.println("normP*normQ == norm(P*Q): " + nPQ.equals(nR) + "\n"); 483 if (nPQ.equals(nR)) { 484 assertEquals("normP*normQ == norm(P*Q)", nPQ, nR); 485 return; 486 } 487 488 rem = nR.remainder(nPQ); 489 //System.out.println("norm(P*Q) mod normP*normQ == 0: " + rem.isZERO()); 490 if (rem.isZERO()) { 491 assertTrue("norm(P*Q) mod normP*normQ == 0", rem.isZERO()); 492 return; 493 } 494 495 GreatestCommonDivisorAbstract<BigRational> gcdr = GCDFactory.getImplementation(q); 496 gcd = gcdr.gcd(nPQ, nR); 497 //System.out.println("gcd(norm(P*Q), normP*normQ) != 1: " + (!gcd.isONE())); 498 if (!gcd.isONE()) { 499 assertFalse("gcd(norm(P*Q), normP*normQ) != 1", gcd.isONE()); 500 return; 501 } 502 // unreachable: 503 FactorAbstract<BigRational> facr = FactorFactory.getImplementation(q); 504 SortedMap<GenPolynomial<BigRational>, Long> fnPQ = facr.factors(nPQ); 505 System.out.println("fnPQ = " + fnPQ); 506 SortedMap<GenPolynomial<BigRational>, Long> fnR = facr.factors(nR); 507 System.out.println("fnR = " + fnR); 508 } 509 510 511 /** 512 * Q matrix construction for Berlekamp. 513 */ 514 public void testQmatix() { 515 int q = 11; //32003; //11; 516 ModIntRing mi = new ModIntRing(q); 517 // for (ModInt s : mi) { 518 // System.out.print(" " + s + " "); 519 // } 520 // System.out.println("mi = " + mi.toScript()); 521 GenPolynomialRing<ModInt> pfac = new GenPolynomialRing<ModInt>(mi, new String[] { "x" }); 522 //System.out.println("pfac = " + pfac.toScript()); 523 GenPolynomial<ModInt> A = pfac.parse("x^6 - 3 x^5 + x^4 - 3 x^3 - x^2 -3 x + 1"); 524 //System.out.println("A = " + A.toScript()); 525 int d = (int) A.degree(0); 526 ArrayList<ArrayList<ModInt>> Q = PolyUfdUtil.<ModInt> constructQmatrix(A); 527 //System.out.println("Q = " + Q); 528 int n = Q.size(); 529 int m = Q.get(0).size(); 530 assertTrue("size(Q) == deg(a): " + Q, n == d); 531 assertTrue("size(Q(0)) == deg(a): " + Q, m == d); 532 533 GenMatrixRing<ModInt> mfac = new GenMatrixRing<ModInt>(mi, n, m); 534 //System.out.println("mfac = " + mfac.toScript()); 535 GenMatrix<ModInt> Qm = new GenMatrix<ModInt>(mfac, Q); 536 //System.out.println("Qm = " + Qm); 537 GenMatrix<ModInt> Qm1 = Qm.subtract(mfac.getONE()); 538 //System.out.println("Qm1 = " + Qm1); 539 540 LinAlg<ModInt> lu = new LinAlg<ModInt>(); 541 List<GenVector<ModInt>> Nsb = lu.nullSpaceBasis(Qm1); 542 //System.out.println("Nsb = " + Nsb); 543 //GenMatrixRing<ModInt> nfac = new GenMatrixRing<ModInt>(mi,k,d); 544 GenMatrix<ModInt> Ns = mfac.fromVectors(Nsb); 545 //System.out.println("Ns = " + Ns); 546 GenMatrix<ModInt> L1 = Ns.negate(); //mfac.getONE().subtract(Ns); 547 //System.out.println("L1 = " + L1); 548 int k = L1.ring.rows; 549 //System.out.println("k = " + k); 550 assertTrue("0 <= k && k < n: " + L1, 0 <= k && k < n); 551 552 // test with random polynomial 553 do { 554 A = pfac.random(10); 555 //System.out.println("A = " + A.toScript()); 556 } while (A.isZERO() || A.degree(0) <= 1); 557 d = (int) A.degree(0); 558 Q = PolyUfdUtil.<ModInt> constructQmatrix(A); 559 //System.out.println("Q = " + Q); 560 n = Q.size(); 561 m = Q.get(0).size(); 562 assertTrue("size(Q) == deg(a): " + Q, n == d); 563 assertTrue("size(Q(0)) == deg(a): " + Q, m == d); 564 ArrayList<ArrayList<ModInt>> Qa = Q; 565 566 mfac = new GenMatrixRing<ModInt>(mi, n, m); 567 //System.out.println("mfac = " + mfac.toScript()); 568 Qm = new GenMatrix<ModInt>(mfac, Q); 569 //System.out.println("Qm = " + Qm); 570 Qm1 = Qm.subtract(mfac.getONE()); 571 //System.out.println("Qm1 = " + Qm1); 572 573 Nsb = lu.nullSpaceBasis(Qm1); 574 //System.out.println("Nsb = " + Nsb); 575 //GenMatrixRing<ModInt> nfac = new GenMatrixRing<ModInt>(mi,k,d); 576 Ns = mfac.fromVectors(Nsb); 577 //System.out.println("Ns = " + Ns); 578 L1 = Ns.negate(); //mfac.getONE().subtract(Ns); 579 //System.out.println("L1 = " + L1); 580 k = L1.ring.rows; 581 //System.out.println("k = " + k); 582 assertTrue("0 <= k && k < n: " + L1, 0 <= k && k <= n); 583 584 // test with modPower 585 GenPolynomial<ModInt> x = pfac.univariate(0); 586 //System.out.println("x = " + x.toScript()); 587 GenPolynomial<ModInt> r = pfac.getONE(); 588 //System.out.println("r = " + r.toScript()); 589 ArrayList<GenPolynomial<ModInt>> Qp = new ArrayList<GenPolynomial<ModInt>>(); 590 Qp.add(r); 591 GenPolynomial<ModInt> pow = Power.<GenPolynomial<ModInt>> modPositivePower(x, q, A); 592 //System.out.println("pow = " + pow.toScript()); 593 Qp.add(pow); 594 r = pow; 595 for (int i = 2; i < d; i++) { 596 r = r.multiply(pow).remainder(A); 597 Qp.add(r); 598 } 599 //System.out.println("Qp = " + Qp); 600 assertTrue("deg(r) < deg(A): " + Qp, r.degree(0) <= A.degree(0)); 601 602 UnivPowerSeriesRing<ModInt> psfac = new UnivPowerSeriesRing<ModInt>(pfac); 603 //System.out.println("psfac = " + psfac.toScript()); 604 ArrayList<ArrayList<ModInt>> Qb = new ArrayList<ArrayList<ModInt>>(); 605 for (GenPolynomial<ModInt> p : Qp) { 606 UnivPowerSeries<ModInt> ps = psfac.fromPolynomial(p); 607 //System.out.println("ps = " + ps.toScript()); 608 ArrayList<ModInt> pr = new ArrayList<ModInt>(); 609 for (int i = 0; i < d; i++) { 610 ModInt c = ps.coefficient(i); 611 pr.add(c); 612 } 613 Qb.add(pr); 614 } 615 //System.out.println("Qb = " + Qb); 616 assertEquals("Qa == Qb: ", Qa, Qb); 617 } 618 619 620 /** 621 * Test search evaluation points. 622 */ 623 public void testSearchEvaluationPoints() { 624 //System.out.println("dfac = " + dfac.toScript()); 625 crfac = new GenPolynomialRing<BigRational>(new BigRational(1), dfac); 626 //System.out.println("crfac = " + crfac.toScript()); 627 SquarefreeAbstract<BigInteger> isqf = SquarefreeFactory.getImplementation(dfac.coFac); 628 SquarefreeAbstract<BigRational> rsqf = SquarefreeFactory.getImplementation(crfac.coFac); 629 for (int i = 0; i < 5; i++) { 630 a = dfac.random(kl, ll * 2, el * 5, q); 631 //System.out.println("a = " + a + ", isSquarefree: " + isqf.isSquarefree(a)); 632 a = isqf.squarefreePart(a); 633 EvalPoints<BigInteger> L = PolyUfdUtil.<BigInteger> evaluationPoints(a); 634 //System.out.println("L = " + L); 635 assertFalse("L != (): ", L.evalPoints.isEmpty()); 636 637 GenPolynomial<BigRational> ar = crfac.random(kl, ll, el * 2, q * 1.5f); 638 //System.out.println("ar = " + ar + ", isSquarefree: " + rsqf.isSquarefree(ar)); 639 ar = rsqf.squarefreePart(ar); 640 EvalPoints<BigRational> Lr = PolyUfdUtil.<BigRational> evaluationPoints(ar); 641 //System.out.println("Lr = " + Lr); 642 assertFalse("Lr != (): ", Lr.evalPoints.isEmpty()); 643 } 644 } 645 646}