001 /*
002 * $Id: GCDModularTest.java 2958 2010-01-01 17:43:39Z kredel $
003 */
004
005 package edu.jas.ufd;
006
007
008 //import java.util.Map;
009 import java.util.ArrayList;
010 import java.util.List;
011
012 import junit.framework.Test;
013 import junit.framework.TestCase;
014 import junit.framework.TestSuite;
015
016 import edu.jas.arith.BigInteger;
017 import edu.jas.arith.ModInteger;
018 import edu.jas.arith.ModIntegerRing;
019 import edu.jas.arith.PrimeList;
020 import edu.jas.poly.GenPolynomial;
021 import edu.jas.poly.GenPolynomialRing;
022 import edu.jas.poly.PolyUtil;
023 import edu.jas.poly.TermOrder;
024
025
026 /**
027 * GCD Modular algorithm tests with JUnit.
028 * @author Heinz Kredel.
029 */
030
031 public class GCDModularTest extends TestCase {
032
033
034 /**
035 * main.
036 */
037 public static void main(String[] args) {
038 junit.textui.TestRunner.run(suite());
039 }
040
041
042 /**
043 * Constructs a <CODE>GCDModularTest</CODE> object.
044 * @param name String.
045 */
046 public GCDModularTest(String name) {
047 super(name);
048 }
049
050
051 /**
052 */
053 public static Test suite() {
054 TestSuite suite = new TestSuite(GCDModularTest.class);
055 return suite;
056 }
057
058
059 //private final static int bitlen = 100;
060
061 GreatestCommonDivisorAbstract<ModInteger> ufd;
062
063
064 TermOrder to = new TermOrder(TermOrder.INVLEX);
065
066
067 GenPolynomialRing<ModInteger> dfac;
068
069
070 GenPolynomialRing<ModInteger> cfac;
071
072
073 GenPolynomialRing<GenPolynomial<ModInteger>> rfac;
074
075
076 PrimeList primes = new PrimeList();
077
078
079 ModIntegerRing mi;
080
081
082 ModInteger ai;
083
084
085 ModInteger bi;
086
087
088 ModInteger ci;
089
090
091 ModInteger di;
092
093
094 ModInteger ei;
095
096
097 GenPolynomial<ModInteger> a;
098
099
100 GenPolynomial<ModInteger> b;
101
102
103 GenPolynomial<ModInteger> c;
104
105
106 GenPolynomial<ModInteger> d;
107
108
109 GenPolynomial<ModInteger> e;
110
111
112 GenPolynomial<ModInteger> ac;
113
114
115 GenPolynomial<ModInteger> bc;
116
117
118 GenPolynomial<GenPolynomial<ModInteger>> ar;
119
120
121 GenPolynomial<GenPolynomial<ModInteger>> br;
122
123
124 GenPolynomial<GenPolynomial<ModInteger>> cr;
125
126
127 GenPolynomial<GenPolynomial<ModInteger>> dr;
128
129
130 GenPolynomial<GenPolynomial<ModInteger>> er;
131
132
133 GenPolynomial<GenPolynomial<ModInteger>> arc;
134
135
136 GenPolynomial<GenPolynomial<ModInteger>> brc;
137
138
139 int rl = 5;
140
141
142 int kl = 4;
143
144
145 int ll = 5;
146
147
148 int el = 3;
149
150
151 float q = 0.3f;
152
153
154 @Override
155 protected void setUp() {
156 a = b = c = d = e = null;
157 ai = bi = ci = di = ei = null;
158 ar = br = cr = dr = er = null;
159 //mi = new ModIntegerRing(primes.get(0), true);
160 mi = new ModIntegerRing(5L, true);
161 ufd = new GreatestCommonDivisorPrimitive<ModInteger>();
162 dfac = new GenPolynomialRing<ModInteger>(mi, rl, to);
163 cfac = new GenPolynomialRing<ModInteger>(mi, rl - 1, to);
164 rfac = new GenPolynomialRing<GenPolynomial<ModInteger>>(cfac, 1, to);
165 }
166
167
168 @Override
169 protected void tearDown() {
170 a = b = c = d = e = null;
171 ai = bi = ci = di = ei = null;
172 ar = br = cr = dr = er = null;
173 ufd = null;
174 dfac = null;
175 cfac = null;
176 rfac = null;
177 }
178
179
180 /**
181 * Test modular algorithm gcd with modular evaluation recursive algorithm.
182 *
183 */
184 public void testModularEvaluationGcd() {
185
186 GreatestCommonDivisorAbstract<BigInteger> ufd_m = new GreatestCommonDivisorModular(/*false*/);
187
188 GreatestCommonDivisorAbstract<BigInteger> ufd = new GreatestCommonDivisorPrimitive<BigInteger>();
189
190 GenPolynomial<BigInteger> a;
191 GenPolynomial<BigInteger> b;
192 GenPolynomial<BigInteger> c;
193 GenPolynomial<BigInteger> d;
194 GenPolynomial<BigInteger> e;
195
196 GenPolynomialRing<BigInteger> dfac = new GenPolynomialRing<BigInteger>(new BigInteger(), 3, to);
197
198 for (int i = 0; i < 2; i++) {
199 a = dfac.random(kl, ll + i, el + i, q);
200 b = dfac.random(kl, ll + i, el + i, q);
201 c = dfac.random(kl, ll + i, el + i, q);
202 c = c.multiply(dfac.univariate(0));
203 //a = ufd.basePrimitivePart(a);
204 //b = ufd.basePrimitivePart(b);
205
206 if (a.isZERO() || b.isZERO() || c.isZERO()) {
207 // skip for this turn
208 continue;
209 }
210 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
211 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
212 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
213
214 a = a.multiply(c);
215 b = b.multiply(c);
216
217 //System.out.println("a = " + a);
218 //System.out.println("b = " + b);
219
220 d = ufd_m.gcd(a, b);
221
222 c = ufd.basePrimitivePart(c).abs();
223 e = PolyUtil.<BigInteger> basePseudoRemainder(d, c);
224 //System.out.println("c = " + c);
225 //System.out.println("d = " + d);
226
227 assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
228
229 e = PolyUtil.<BigInteger> basePseudoRemainder(a, d);
230 //System.out.println("e = " + e);
231 assertTrue("gcd(a,b) | a" + e, e.isZERO());
232
233 e = PolyUtil.<BigInteger> basePseudoRemainder(b, d);
234 //System.out.println("e = " + e);
235 assertTrue("gcd(a,b) | b" + e, e.isZERO());
236 }
237 }
238
239
240 /**
241 * Test modular algorithm gcd with simple PRS recursive algorithm.
242 *
243 */
244 public void testModularSimpleGcd() {
245
246 GreatestCommonDivisorAbstract<BigInteger> ufd_m = new GreatestCommonDivisorModular(true);
247
248 GreatestCommonDivisorAbstract<BigInteger> ufd = new GreatestCommonDivisorPrimitive<BigInteger>();
249
250 GenPolynomial<BigInteger> a;
251 GenPolynomial<BigInteger> b;
252 GenPolynomial<BigInteger> c;
253 GenPolynomial<BigInteger> d;
254 GenPolynomial<BigInteger> e;
255
256 GenPolynomialRing<BigInteger> dfac = new GenPolynomialRing<BigInteger>(new BigInteger(), 3, to);
257
258 for (int i = 0; i < 1; i++) {
259 a = dfac.random(kl, ll + i, el + i, q);
260 b = dfac.random(kl, ll + i, el + i, q);
261 c = dfac.random(kl, ll + i, el + i, q);
262 c = c.multiply(dfac.univariate(0));
263 //a = ufd.basePrimitivePart(a);
264 //b = ufd.basePrimitivePart(b);
265
266 if (a.isZERO() || b.isZERO() || c.isZERO()) {
267 // skip for this turn
268 continue;
269 }
270 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
271 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
272 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
273
274 a = a.multiply(c);
275 b = b.multiply(c);
276
277 //System.out.println("a = " + a);
278 //System.out.println("b = " + b);
279
280 d = ufd_m.gcd(a, b);
281
282 c = ufd.basePrimitivePart(c).abs();
283 e = PolyUtil.<BigInteger> basePseudoRemainder(d, c);
284 //System.out.println("c = " + c);
285 //System.out.println("d = " + d);
286
287 assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
288
289 e = PolyUtil.<BigInteger> basePseudoRemainder(a, d);
290 //System.out.println("e = " + e);
291 assertTrue("gcd(a,b) | a" + e, e.isZERO());
292
293 e = PolyUtil.<BigInteger> basePseudoRemainder(b, d);
294 //System.out.println("e = " + e);
295 assertTrue("gcd(a,b) | b" + e, e.isZERO());
296 }
297 }
298
299
300 /**
301 * Test recursive content and primitive part, modular coefficients.
302 *
303 */
304 public void testRecursiveContentPPmodular() {
305
306 dfac = new GenPolynomialRing<ModInteger>(mi, 2, to);
307 cfac = new GenPolynomialRing<ModInteger>(mi, 2 - 1, to);
308 rfac = new GenPolynomialRing<GenPolynomial<ModInteger>>(cfac, 1, to);
309
310 GreatestCommonDivisorAbstract<ModInteger> ufd = new GreatestCommonDivisorPrimitive<ModInteger>();
311
312 for (int i = 0; i < 1; i++) {
313 a = cfac.random(kl, ll + 2 * i, el + i, q).monic();
314 cr = rfac.random(kl * (i + 2), ll + 2 * i, el + i, q);
315 cr = PolyUtil.<ModInteger> monic(cr);
316 //System.out.println("a = " + a);
317 //System.out.println("cr = " + cr);
318 //a = ufd.basePrimitivePart(a);
319 //b = distribute(dfac,cr);
320 //b = ufd.basePrimitivePart(b);
321 //cr = recursive(rfac,b);
322 //System.out.println("a = " + a);
323 //System.out.println("cr = " + cr);
324
325 cr = cr.multiply(a);
326 //System.out.println("cr = " + cr);
327
328 if (cr.isZERO()) {
329 // skip for this turn
330 continue;
331 }
332 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
333 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
334 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
335
336 c = ufd.recursiveContent(cr).monic();
337 dr = ufd.recursivePrimitivePart(cr);
338 dr = PolyUtil.<ModInteger> monic(dr);
339 //System.out.println("c = " + c);
340 //System.out.println("dr = " + dr);
341
342 //System.out.println("monic(a) = " + a.monic());
343 //System.out.println("monic(c) = " + c.monic());
344
345 ar = dr.multiply(c);
346 //System.out.println("ar = " + ar);
347 assertEquals("c == cont(c)pp(c)", cr, ar);
348 }
349 }
350
351
352 /**
353 * Test base gcd modular coefficients.
354 *
355 */
356 public void testGCDbaseModular() {
357
358 dfac = new GenPolynomialRing<ModInteger>(mi, 1, to);
359
360 GreatestCommonDivisorAbstract<ModInteger> ufd = new GreatestCommonDivisorPrimitive<ModInteger>();
361
362 for (int i = 0; i < 1; i++) {
363 a = dfac.random(kl, ll, el + 3 + i, q).monic();
364 b = dfac.random(kl, ll, el + 3 + i, q).monic();
365 c = dfac.random(kl, ll, el + 3 + i, q).monic();
366 //System.out.println("a = " + a);
367 //System.out.println("b = " + b);
368 //System.out.println("c = " + c);
369
370 if (a.isZERO() || b.isZERO() || c.isZERO()) {
371 // skip for this turn
372 continue;
373 }
374 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
375 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
376 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
377
378 ac = a.multiply(c);
379 bc = b.multiply(c);
380 //System.out.println("ac = " + ac);
381 //System.out.println("bc = " + bc);
382
383 //e = PolyUtil.<ModInteger>basePseudoRemainder(ac,c);
384 //System.out.println("ac/c a = 0 " + e);
385 //assertTrue("ac/c-a != 0 " + e, e.isZERO() );
386 //e = PolyUtil.<ModInteger>basePseudoRemainder(bc,c);
387 //System.out.println("bc/c-b = 0 " + e);
388 //assertTrue("bc/c-b != 0 " + e, e.isZERO() );
389
390 d = ufd.baseGcd(ac, bc);
391 d = d.monic(); // not required
392 //System.out.println("d = " + d);
393
394 e = PolyUtil.<ModInteger> basePseudoRemainder(d, c);
395 //System.out.println("e = " + e);
396
397 assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
398 }
399 }
400
401
402 /**
403 * Test recursive gcd modular coefficients.
404 *
405 */
406 public void testRecursiveGCDModular() {
407
408 dfac = new GenPolynomialRing<ModInteger>(mi, 2, to);
409 cfac = new GenPolynomialRing<ModInteger>(mi, 2 - 1, to);
410 rfac = new GenPolynomialRing<GenPolynomial<ModInteger>>(cfac, 1, to);
411
412 // GreatestCommonDivisorAbstract<ModInteger> ufd
413 // = new GreatestCommonDivisorPrimitive<ModInteger>();
414
415 for (int i = 0; i < 1; i++) {
416 ar = rfac.random(kl, 2, el + 2, q);
417 br = rfac.random(kl, 2, el + 2, q);
418 cr = rfac.random(kl, 2, el + 2, q);
419 ar = PolyUtil.<ModInteger> monic(ar);
420 br = PolyUtil.<ModInteger> monic(br);
421 cr = PolyUtil.<ModInteger> monic(cr);
422 //System.out.println("ar = " + ar);
423 //System.out.println("br = " + br);
424 //System.out.println("cr = " + cr);
425
426 if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
427 // skip for this turn
428 continue;
429 }
430 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
431 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
432 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
433
434 arc = ar.multiply(cr);
435 brc = br.multiply(cr);
436 //System.out.println("arc = " + arc);
437 //System.out.println("brc = " + brc);
438
439 //er = PolyUtil.<ModInteger>recursivePseudoRemainder(arc,cr);
440 //System.out.println("ac/c-a = 0 " + er);
441 //assertTrue("ac/c-a != 0 " + er, er.isZERO() );
442 //er = PolyUtil.<ModInteger>recursivePseudoRemainder(brc,cr);
443 //System.out.println("bc/c-b = 0 " + er);
444 //assertTrue("bc/c-b != 0 " + er, er.isZERO() );
445
446 dr = ufd.recursiveUnivariateGcd(arc, brc);
447 dr = PolyUtil.<ModInteger> monic(dr);
448 //System.out.println("cr = " + cr);
449 //System.out.println("dr = " + dr);
450
451 er = PolyUtil.<ModInteger> recursivePseudoRemainder(dr, cr);
452 //System.out.println("er = " + er);
453
454 assertTrue("c | gcd(ac,bc) " + er, er.isZERO());
455 }
456 }
457
458
459 /**
460 * Test arbitrary recursive gcd modular coefficients.
461 *
462 */
463 public void testArbitraryRecursiveGCDModular() {
464
465 dfac = new GenPolynomialRing<ModInteger>(mi, 2, to);
466 cfac = new GenPolynomialRing<ModInteger>(mi, 2 - 1, to);
467 rfac = new GenPolynomialRing<GenPolynomial<ModInteger>>(cfac, 1, to);
468
469 // GreatestCommonDivisorAbstract<ModInteger> ufd
470 // = new GreatestCommonDivisorPrimitive<ModInteger>();
471
472 for (int i = 0; i < 1; i++) {
473 ar = rfac.random(kl, 2, el + 2, q);
474 br = rfac.random(kl, 2, el + 2, q);
475 cr = rfac.random(kl, 2, el + 2, q);
476 ar = PolyUtil.<ModInteger> monic(ar);
477 br = PolyUtil.<ModInteger> monic(br);
478 cr = PolyUtil.<ModInteger> monic(cr);
479 //System.out.println("ar = " + ar);
480 //System.out.println("br = " + br);
481 //System.out.println("cr = " + cr);
482
483 if (ar.isZERO() || br.isZERO() || cr.isZERO()) {
484 // skip for this turn
485 continue;
486 }
487 assertTrue("length( cr" + i + " ) <> 0", cr.length() > 0);
488 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
489 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
490
491 arc = ar.multiply(cr);
492 brc = br.multiply(cr);
493 //System.out.println("arc = " + arc);
494 //System.out.println("brc = " + brc);
495
496 //er = PolyUtil.<ModInteger>recursivePseudoRemainder(arc,cr);
497 //System.out.println("ac/c-a = 0 " + er);
498 //assertTrue("ac/c-a != 0 " + er, er.isZERO() );
499 //er = PolyUtil.<ModInteger>recursivePseudoRemainder(brc,cr);
500 //System.out.println("bc/c-b = 0 " + er);
501 //assertTrue("bc/c-b != 0 " + er, er.isZERO() );
502
503 dr = ufd.recursiveGcd(arc, brc);
504 dr = PolyUtil.<ModInteger> monic(dr);
505 //System.out.println("cr = " + cr);
506 //System.out.println("dr = " + dr);
507
508 er = PolyUtil.<ModInteger> recursivePseudoRemainder(dr, cr);
509 //System.out.println("er = " + er);
510
511 assertTrue("c | gcd(ac,bc) " + er, er.isZERO());
512 }
513 }
514
515
516 /**
517 * Test gcd modular coefficients.
518 *
519 */
520 public void testGcdModular() {
521
522 dfac = new GenPolynomialRing<ModInteger>(mi, 4, to);
523
524 for (int i = 0; i < 1; i++) {
525 a = dfac.random(kl, ll, el + i, q).monic();
526 b = dfac.random(kl, ll, el + i, q).monic();
527 c = dfac.random(kl, ll, el + i, q).monic();
528 //System.out.println("a = " + a);
529 //System.out.println("b = " + b);
530 //System.out.println("c = " + c);
531
532 if (a.isZERO() || b.isZERO() || c.isZERO()) {
533 // skip for this turn
534 continue;
535 }
536 assertTrue("length( c" + i + " ) <> 0", c.length() > 0);
537 //assertTrue(" not isZERO( c"+i+" )", !c.isZERO() );
538 //assertTrue(" not isONE( c"+i+" )", !c.isONE() );
539
540 ac = a.multiply(c);
541 bc = b.multiply(c);
542 //System.out.println("ac = " + ac);
543 //System.out.println("bc = " + bc);
544
545 //e = PolyUtil.<ModInteger>basePseudoRemainder(ac,c);
546 //System.out.println("ac/c-a = 0 " + e);
547 //assertTrue("ac/c-a != 0 " + e, e.isZERO() );
548 //e = PolyUtil.<ModInteger>basePseudoRemainder(bc,c);
549 //System.out.println("bc/c-b = 0 " + e);
550 //assertTrue("bc/c-b != 0 " + e, e.isZERO() );
551
552 d = ufd.gcd(ac, bc);
553 //System.out.println("d = " + d);
554 e = PolyUtil.<ModInteger> basePseudoRemainder(d, c);
555 //System.out.println("e = " + e);
556 //System.out.println("c = " + c);
557 assertTrue("c | gcd(ac,bc) " + e, e.isZERO());
558
559 e = PolyUtil.<ModInteger> basePseudoRemainder(ac, d);
560 //System.out.println("gcd(ac,bc) | ac " + e);
561 assertTrue("gcd(ac,bc) | ac " + e, e.isZERO());
562 e = PolyUtil.<ModInteger> basePseudoRemainder(bc, d);
563 //System.out.println("gcd(ac,bc) | bc " + e);
564 assertTrue("gcd(ac,bc) | bc " + e, e.isZERO());
565 }
566 }
567
568
569 /**
570 * Test co-prime factors.
571 *
572 */
573 public void testCoPrime() {
574
575 dfac = new GenPolynomialRing<ModInteger>(mi, 3, to);
576
577 a = dfac.random(kl, 3, 2, q);
578 b = dfac.random(kl, 3, 2, q);
579 c = dfac.random(kl, 3, 2, q);
580 //System.out.println("a = " + a);
581 //System.out.println("b = " + b);
582 //System.out.println("c = " + c);
583
584 if (a.isZERO() || b.isZERO() || c.isZERO()) {
585 // skip for this turn
586 return;
587 }
588 assertTrue("length( a ) <> 0", a.length() > 0);
589
590 d = a.multiply(a).multiply(b).multiply(b).multiply(b).multiply(c);
591 e = a.multiply(b).multiply(c);
592 //System.out.println("d = " + d);
593 //System.out.println("c = " + c);
594
595 List<GenPolynomial<ModInteger>> F = new ArrayList<GenPolynomial<ModInteger>>(5);
596 F.add(a);
597 F.add(b);
598 F.add(c);
599 F.add(d);
600 F.add(e);
601
602 List<GenPolynomial<ModInteger>> P = ufd.coPrime(F);
603 //System.out.println("F = " + F);
604 //System.out.println("P = " + P);
605
606 assertTrue("is co-prime ", ufd.isCoPrime(P));
607 assertTrue("is co-prime of ", ufd.isCoPrime(P, F));
608
609 P = ufd.coPrimeRec(F);
610 //System.out.println("F = " + F);
611 //System.out.println("P = " + P);
612
613 assertTrue("is co-prime ", ufd.isCoPrime(P));
614 assertTrue("is co-prime of ", ufd.isCoPrime(P, F));
615 }
616
617 }