Source code

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