001 /*
002 * $Id: HenselMultUtilTest.java 3672 2011-06-26 11:25:19Z kredel $
003 */
004
005 package edu.jas.application;
006
007
008 import java.util.ArrayList;
009 import java.util.List;
010
011 import org.apache.log4j.BasicConfigurator;
012
013 import junit.framework.Test;
014 import junit.framework.TestCase;
015 import junit.framework.TestSuite;
016
017 import edu.jas.arith.PrimeList;
018 import edu.jas.arith.BigInteger;
019 import edu.jas.arith.ModInteger;
020 import edu.jas.arith.ModIntegerRing;
021 import edu.jas.arith.ModLong;
022 import edu.jas.arith.ModLongRing;
023 import edu.jas.arith.ModularRingFactory;
024 import edu.jas.structure.Power;
025 import edu.jas.kern.ComputerThreads;
026 import edu.jas.poly.ExpVector;
027 import edu.jas.poly.GenPolynomial;
028 import edu.jas.poly.GenPolynomialRing;
029 import edu.jas.poly.PolyUtil;
030 import edu.jas.poly.TermOrder;
031 import edu.jas.ufd.GreatestCommonDivisor;
032 import edu.jas.ufd.HenselMultUtil;
033 import edu.jas.ufd.NoLiftingException;
034 import edu.jas.ufd.GCDFactory;
035
036
037 /**
038 * HenselMultUtil tests with JUnit.
039 * Two seperate classes because of package dependency.
040 * @see edu.jas.ufd.HenselMultUtilTest
041 * @author Heinz Kredel.
042 */
043
044 public class HenselMultUtilTest extends TestCase {
045
046
047 /**
048 * main.
049 */
050 public static void main(String[] args) {
051 BasicConfigurator.configure();
052 junit.textui.TestRunner.run(suite());
053 ComputerThreads.terminate();
054 }
055
056
057 /**
058 * Constructs a <CODE>HenselMultUtilTest</CODE> object.
059 * @param name String.
060 */
061 public HenselMultUtilTest(String name) {
062 super(name);
063 }
064
065
066 /**
067 */
068 public static Test suite() {
069 TestSuite suite = new TestSuite(HenselMultUtilTest.class);
070 return suite;
071 }
072
073
074 TermOrder tord = new TermOrder(TermOrder.INVLEX);
075
076
077 GenPolynomialRing<BigInteger> dfac;
078
079
080 GenPolynomialRing<BigInteger> cfac;
081
082
083 GenPolynomialRing<GenPolynomial<BigInteger>> rfac;
084
085
086 BigInteger ai;
087
088
089 BigInteger bi;
090
091
092 BigInteger ci;
093
094
095 BigInteger di;
096
097
098 BigInteger ei;
099
100
101 GenPolynomial<BigInteger> a;
102
103
104 GenPolynomial<BigInteger> b;
105
106
107 GenPolynomial<BigInteger> c;
108
109
110 GenPolynomial<BigInteger> d;
111
112
113 GenPolynomial<BigInteger> e;
114
115
116 int rl = 2;
117
118
119 int kl = 5;
120
121
122 int ll = 5;
123
124
125 int el = 3;
126
127
128 float q = 0.3f;
129
130
131 @Override
132 protected void setUp() {
133 a = b = c = d = e = null;
134 ai = bi = ci = di = ei = null;
135 dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl, tord);
136 cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl - 1, tord);
137 rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, tord);
138 }
139
140
141 @Override
142 protected void tearDown() {
143 a = b = c = d = e = null;
144 ai = bi = ci = di = ei = null;
145 dfac = null;
146 cfac = null;
147 rfac = null;
148 ComputerThreads.terminate();
149 }
150
151
152 protected static java.math.BigInteger getPrime1() {
153 return PrimeList.getLongPrime(60,93);
154 }
155
156
157 protected static java.math.BigInteger getPrime2() {
158 return PrimeList.getLongPrime(30,35);
159 }
160
161
162 /**
163 * Test multivariate diophant lifting.
164 */
165 public void testDiophantLifting() {
166 java.math.BigInteger p;
167 //p = getPrime1();
168 p = new java.math.BigInteger("19");
169 //p = new java.math.BigInteger("5");
170 BigInteger m = new BigInteger(p);
171
172 ModIntegerRing pm = new ModIntegerRing(p, false);
173 //ModLongRing pl = new ModLongRing(p, false);
174 //GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(pm, 2, tord, new String[]{ "x", "y" });
175 GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(pm, 3, tord, new String[]{ "x", "y", "z" });
176 GenPolynomialRing<BigInteger> ifac = new GenPolynomialRing<BigInteger>(new BigInteger(),pfac);
177
178 BigInteger mi = m;
179 long k = 5L;
180 long d = 3L;
181 java.math.BigInteger pk = p.pow((int)k);
182 m = new BigInteger(pk);
183
184 ModIntegerRing pkm = new ModIntegerRing(pk, false);
185 //ModLongRing pkl = new ModLongRing(pk, false);
186 GenPolynomialRing<ModInteger> pkfac = new GenPolynomialRing<ModInteger>(pkm, pfac);
187 dfac = new GenPolynomialRing<BigInteger>(mi, pfac);
188
189 //GreatestCommonDivisor<BigInteger> ufd = GCDFactory.getProxy(mi);
190 GreatestCommonDivisor<BigInteger> ufd = GCDFactory.getImplementation(mi);
191
192 //ModLong v = pl.fromInteger(3L);
193 ModInteger v = pkm.fromInteger(5L);
194 List<ModInteger> V = new ArrayList<ModInteger>(1);
195 V.add(v);
196 V.add(pkm.fromInteger(3L));
197 //System.out.println("V = " + V);
198
199 GenPolynomial<ModInteger> ap;
200 GenPolynomial<ModInteger> bp;
201 GenPolynomial<ModInteger> cp;
202 GenPolynomial<ModInteger> dp;
203 GenPolynomial<ModInteger> sp;
204 GenPolynomial<ModInteger> tp;
205 GenPolynomial<ModInteger> rp;
206
207 for (int i = 1; i < 2; i++) {
208 a = dfac.random(kl + 7 * i, ll, el + 3, q).abs();
209 b = dfac.random(kl + 7 * i, ll, el + 2, q).abs();
210 //a = dfac.parse(" y^2 + 2 x y - 3 y + x^2 - 3 x - 4 ");
211 //b = dfac.parse(" y^2 + 2 x y + 5 y + x^2 + 5 x + 4 ");
212 //a = dfac.parse(" (x - 4 + y)*( x + y + 1 ) ");
213 //b = dfac.parse(" (x + 4 + y)*( x + y + 1 ) ");
214 //a = dfac.parse(" (x - 4 + y) ");
215 ///a = dfac.parse(" (x - 13 + y) ");
216 ///b = dfac.parse(" (x + 4 + y) ");
217 //a = dfac.parse(" (x - 1)*(1 + x) ");
218 //b = dfac.parse(" (x - 2)*(3 + x) ");
219 //a = dfac.parse(" (x - 1)*(y + x) ");
220 //b = dfac.parse(" (x - 2)*(y - x) ");
221 //a = dfac.parse(" (x - 1)*(y + 1) ");
222 //b = dfac.parse(" (x - 2)*(y - 1) ");
223 //a = dfac.parse(" (x - 1)*(y^2 + 1) ");
224 //b = dfac.parse(" (x - 2)*(y^2 - 1) ");
225 //a = dfac.parse(" z + (y - 1)*(1 + y) ");
226 //b = dfac.parse(" z + (y - 2)*(2 + y) ");
227 //a = dfac.parse(" (y - 1)*(1 + y) ");
228 //b = dfac.parse(" (y - 2)*(2 + y) ");
229 ///a = dfac.parse(" (y - 3) "); //2 // tp = 47045880 = -1
230 ///b = dfac.parse(" (y - 1) "); // sp = 1
231 //a = dfac.parse(" (y - 4) "); // tp = 15681960
232 //b = dfac.parse(" (y - 1) "); // sp = 31363921
233 //a = dfac.parse(" (x - 3) "); // tp = 15681960, 1238049
234 //b = dfac.parse(" (x - 1) "); // sp = 31363921, -1238049
235 //a = dfac.parse(" ( y^2 + x^3 - 2 x ) ");
236 //b = dfac.parse(" ( y - x^2 + 3 ) ");
237
238 c = ufd.gcd(a,b);
239 //System.out.println("\na = " + a);
240 //System.out.println("b = " + b);
241 //System.out.println("c = " + c);
242
243 if ( ! c.isUnit() ) {
244 continue;
245 }
246 //c = dfac.parse(" x y z ");
247 //System.out.println("c = " + c);
248
249 ap = PolyUtil.<ModInteger> fromIntegerCoefficients(pkfac,a);
250 bp = PolyUtil.<ModInteger> fromIntegerCoefficients(pkfac,b);
251 cp = PolyUtil.<ModInteger> fromIntegerCoefficients(pkfac,c);
252 //if (ap.degree(0) < 1 || bp.degree(0) < 1) {
253 // continue;
254 //}
255 //System.out.println("\nap = " + ap);
256 //System.out.println("bp = " + bp);
257 //System.out.println("cp = " + cp);
258
259 List<GenPolynomial<ModInteger>> lift;
260 try {
261 lift = HenselMultUtil.<ModInteger> liftDiophant(ap, bp, cp, V, d, k); // 5 is max
262 sp = lift.get(0);
263 tp = lift.get(1);
264 //System.out.println("liftMultiDiophant:");
265 //System.out.println("sp = " + sp);
266 //System.out.println("tp = " + tp);
267 //System.out.println("isDiophantLift: " + HenselUtil.<ModInteger> isDiophantLift(bp,ap,sp,tp,cp) );
268
269 GenPolynomialRing<ModInteger> qfac = sp.ring;
270 //System.out.println("qfac = " + qfac.toScript());
271 assertEquals("pkfac == qfac: " + qfac, pkfac, qfac);
272
273 rp = bp.multiply(sp).sum( ap.multiply(tp) ); // order
274 //System.out.println("\nrp = " + rp);
275
276 //not true: System.out.println("a s + b t = c: " + cp.equals(rp));
277 //assertEquals("a s + b t = c ", dp,rp);
278
279 GenPolynomialRing<ModInteger> cfac = pkfac.contract(1);
280 ModInteger vp = pkfac.coFac.fromInteger(V.get(0).getSymmetricInteger().getVal());
281 GenPolynomial<ModInteger> ya = pkfac.univariate(1);
282 ya = ya.subtract(vp);
283 ya = Power.<GenPolynomial<ModInteger>>power(pkfac,ya,d+1);
284 //System.out.println("ya = " + ya);
285 List<GenPolynomial<ModInteger>> Y = new ArrayList<GenPolynomial<ModInteger>>();
286 Y.add(ya);
287 vp = pkfac.coFac.fromInteger(V.get(1).getSymmetricInteger().getVal());
288 GenPolynomial<ModInteger> za = pkfac.univariate(0);
289 za = za.subtract(vp);
290 za = Power.<GenPolynomial<ModInteger>>power(pkfac,za,d+1);
291 //System.out.println("za = " + za);
292 Y.add(za);
293 //System.out.println("\nY = " + Y);
294 Ideal<ModInteger> Yi = new Ideal<ModInteger>(pkfac,Y);
295 //System.out.println("Yi = " + Yi);
296 ResidueRing<ModInteger> Yr = new ResidueRing<ModInteger>(Yi);
297 //System.out.println("Yr = " + Yr);
298
299 Residue<ModInteger> apr = new Residue<ModInteger>(Yr,ap);
300 Residue<ModInteger> bpr = new Residue<ModInteger>(Yr,bp);
301 Residue<ModInteger> cpr = new Residue<ModInteger>(Yr,cp);
302 Residue<ModInteger> spr = new Residue<ModInteger>(Yr,sp);
303 Residue<ModInteger> tpr = new Residue<ModInteger>(Yr,tp);
304 Residue<ModInteger> rpr = bpr.multiply(spr).sum( apr.multiply(tpr) ); // order
305 //System.out.println("\napr = " + apr);
306 //System.out.println("bpr = " + bpr);
307 //System.out.println("cpr = " + cpr);
308 //System.out.println("spr = " + spr);
309 //System.out.println("tpr = " + tpr);
310 //System.out.println("rpr = " + rpr);
311 //System.out.println("ar sr + br tr = cr: " + cpr.equals(rpr) + "\n");
312 assertEquals("ar sr + br tr = cr ", cpr,rpr);
313 } catch (NoLiftingException e) {
314 // can happen: fail("" + e);
315 System.out.println("e = " + e);
316 }
317 }
318 }
319
320
321 /**
322 * Test multivariate diophant lifting list.
323 */
324 public void testDiophantLiftingList() {
325 java.math.BigInteger p;
326 //p = getPrime1();
327 p = new java.math.BigInteger("19");
328 //p = new java.math.BigInteger("5");
329 BigInteger m = new BigInteger(p);
330
331 ModIntegerRing pm = new ModIntegerRing(p, false);
332 //ModLongRing pl = new ModLongRing(p, false);
333 //GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(pm, 2, tord, new String[]{ "x", "y" });
334 GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(pm, 3, tord, new String[]{ "x", "y", "z" });
335 //GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(pm, 4, tord, new String[]{ "w", "x", "y", "z" });
336 GenPolynomialRing<BigInteger> ifac = new GenPolynomialRing<BigInteger>(new BigInteger(),pfac);
337
338 BigInteger mi = m;
339 long k = 5L;
340 long d = 3L;
341 java.math.BigInteger pk = p.pow((int)k);
342 m = new BigInteger(pk);
343
344 ModIntegerRing pkm = new ModIntegerRing(pk, false);
345 //ModLongRing pkl = new ModLongRing(pk, false);
346 GenPolynomialRing<ModInteger> pkfac = new GenPolynomialRing<ModInteger>(pkm, pfac);
347 dfac = new GenPolynomialRing<BigInteger>(mi, pfac);
348
349 //GreatestCommonDivisor<BigInteger> ufd = GCDFactory.getProxy(mi);
350 GreatestCommonDivisor<BigInteger> ufd = GCDFactory.getImplementation(mi);
351
352 //ModLong v = pl.fromInteger(3L);
353 ModInteger v = pkm.fromInteger(5L);
354 List<ModInteger> V = new ArrayList<ModInteger>(1);
355 V.add(v);
356 V.add(pkm.fromInteger(3L));
357 if ( pkfac.nvar > 3 ) {
358 V.add(pkm.fromInteger(7L));
359 }
360 //System.out.println("V = " + V);
361
362 GenPolynomial<ModInteger> ap;
363 GenPolynomial<ModInteger> cp;
364 GenPolynomial<ModInteger> rp;
365
366 List<GenPolynomial<BigInteger>> A = new ArrayList<GenPolynomial<BigInteger>>();
367
368 for (int i = 1; i < 2; i++) {
369 a = dfac.random(kl + 7 * i, ll, el + 3, q).abs();
370 b = dfac.random(kl + 7 * i, ll, el + 2, q).abs();
371 c = dfac.random(kl + 7 * i, ll, el + 2, q).abs();
372 //a = dfac.parse(" z + x*y + (y - 1)*(1 + y) ");
373 //b = dfac.parse(" z - x + (y - 2)*(2 + y) ");
374 //c = dfac.parse(" z + x + (y - 2)*(2 + y) ");
375
376 A.add(a);
377 A.add(b);
378 A.add(c);
379 //System.out.println("\nA = " + A);
380 A = ufd.coPrime(A);
381 //System.out.println("coprime(A) = " + A);
382 if ( A.size() == 0 ) {
383 continue;
384 }
385
386 List<GenPolynomial<ModInteger>> Ap = new ArrayList<GenPolynomial<ModInteger>>(A.size());
387 for ( GenPolynomial<BigInteger> ai : A ) {
388 ap = PolyUtil.<ModInteger> fromIntegerCoefficients(pkfac,ai);
389 Ap.add(ap);
390 }
391 //System.out.println("A mod p^k = " + Ap);
392 cp = pkfac.parse(" x y z + x y + x ");
393 //cp = pkfac.parse(" x y + x ");
394 //cp = Ap.get(0).multiply(Ap.get(1));
395 //System.out.println("cp = " + cp);
396
397 GenPolynomial<ModInteger> B = pkfac.getONE();
398 for ( GenPolynomial<ModInteger> bp : Ap ) {
399 B = B.multiply(bp);
400 }
401 //System.out.println("B = " + B);
402 List<GenPolynomial<ModInteger>> Bp = new ArrayList<GenPolynomial<ModInteger>>(A.size());
403 for ( GenPolynomial<ModInteger> bp : Ap ) {
404 GenPolynomial<ModInteger> b = PolyUtil.<ModInteger> basePseudoDivide(B, bp);
405 if ( b.isZERO() ) {
406 System.out.println("b == 0");
407 return;
408 }
409 Bp.add(b);
410 }
411 //System.out.println("B mod p^k = " + Bp);
412
413 try {
414 List<GenPolynomial<ModInteger>> lift;
415 lift = HenselMultUtil.<ModInteger> liftDiophant(Ap, cp, V, d, k); // 5 is max
416 //System.out.println("liftMultiDiophant:");
417 //System.out.println("lift = " + lift);
418
419 GenPolynomialRing<ModInteger> qfac = lift.get(0).ring;
420 assertEquals("pkfac == qfac: " + qfac, pkfac, qfac);
421
422 GenPolynomialRing<ModInteger> cfac = pkfac.contract(1);
423 List<GenPolynomial<ModInteger>> Y = new ArrayList<GenPolynomial<ModInteger>>();
424
425 for ( int j = 0; j < V.size(); j++ ) {
426 ModInteger vp = pkfac.coFac.fromInteger(V.get(j).getSymmetricInteger().getVal());
427 GenPolynomial<ModInteger> ya = pkfac.univariate(pkfac.nvar-2-j);
428 ya = ya.subtract(vp);
429 //ya = Power.<GenPolynomial<ModInteger>>power(pkfac,ya,d+1);
430 //System.out.println("ya = " + ya);
431 Y.add(ya);
432 }
433 //System.out.println("\nY = " + Y);
434 Ideal<ModInteger> Yi = new Ideal<ModInteger>(pkfac,Y);
435 //System.out.println("Yi = " + Yi);
436 Yi = Yi.power((int)d+1);
437 //System.out.println("Yi = " + Yi);
438 ResidueRing<ModInteger> Yr = new ResidueRing<ModInteger>(Yi);
439 //System.out.println("\nYr = " + Yr);
440
441 List<Residue<ModInteger>> Bpr = new ArrayList<Residue<ModInteger>>(A.size());
442 for ( GenPolynomial<ModInteger> tp : Bp ) {
443 Residue<ModInteger> apr = new Residue<ModInteger>(Yr,tp);
444 Bpr.add(apr);
445 }
446 List<Residue<ModInteger>> Spr = new ArrayList<Residue<ModInteger>>(A.size());
447 for ( GenPolynomial<ModInteger> sp : lift ) {
448 Residue<ModInteger> apr = new Residue<ModInteger>(Yr,sp);
449 if ( apr.isZERO() ) {
450 System.out.println("apr == 0");
451 //return;
452 }
453 Spr.add(apr);
454 }
455 //System.out.println("\nBpr = " + Bpr);
456 //System.out.println("Spr = " + Spr);
457
458 Residue<ModInteger> cpr = new Residue<ModInteger>(Yr,cp);
459 Residue<ModInteger> rpr = Yr.getZERO();
460 int j = 0;
461 for ( Residue<ModInteger> r : Bpr ) {
462 rpr = rpr.sum( r.multiply(Spr.get(j++)) );
463 }
464 //System.out.println("cpr = " + cpr);
465 //System.out.println("rpr = " + rpr);
466 assertEquals("sum_i( br sr ) = cr ", cpr,rpr);
467 } catch (ArithmeticException e) {
468 // ok, can happen
469 } catch (NoLiftingException e) {
470 // can now happen: fail("" + e);
471 System.out.println("e = " + e);
472 }
473 }
474 }
475
476 }