Source code

001/*
002 * $Id: HenselMultUtilTest.java 5862 2018-07-20 10:56:22Z 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
015
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        
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, bi, ci, di, ei;
083
084
085    GenPolynomial<BigInteger> a, b, c, d, e;
086
087
088    int rl = 2;
089
090
091    int kl = 5;
092
093
094    int ll = 5;
095
096
097    int el = 3;
098
099
100    float q = 0.3f;
101
102
103    @Override
104    protected void setUp() {
105        a = b = c = d = e = null;
106        ai = bi = ci = di = ei = null;
107        dfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl, tord);
108        cfac = new GenPolynomialRing<BigInteger>(new BigInteger(1), rl - 1, tord);
109        rfac = new GenPolynomialRing<GenPolynomial<BigInteger>>(cfac, 1, tord);
110    }
111
112
113    @Override
114    protected void tearDown() {
115        a = b = c = d = e = null;
116        ai = bi = ci = di = ei = null;
117        dfac = null;
118        cfac = null;
119        rfac = null;
120        ComputerThreads.terminate();
121    }
122
123
124    protected static java.math.BigInteger getPrime1() {
125        return PrimeList.getLongPrime(60, 93);
126    }
127
128
129    protected static java.math.BigInteger getPrime2() {
130        return PrimeList.getLongPrime(30, 35);
131    }
132
133
134    /**
135     * Test multivariate diophant lifting.
136     */
137    public void testDiophantLifting() {
138        java.math.BigInteger p;
139        //p = getPrime1();
140        p = new java.math.BigInteger("19");
141        //p = new java.math.BigInteger("5");
142        BigInteger m = new BigInteger(p);
143
144        ModIntegerRing pm = new ModIntegerRing(p, false);
145        //ModLongRing pl = new ModLongRing(p, false);
146        //GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(pm, 2, tord, new String[]{ "x", "y" });
147        GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(pm, 3, tord, new String[] {
148                "x", "y", "z" });
149        //GenPolynomialRing<BigInteger> ifac = new GenPolynomialRing<BigInteger>(new BigInteger(),pfac);
150
151        BigInteger mi = m;
152        long k = 5L;
153        long d = 3L;
154        java.math.BigInteger pk = p.pow((int) k);
155        //m = new BigInteger(pk);
156
157        ModIntegerRing pkm = new ModIntegerRing(pk, false);
158        //ModLongRing pkl = new ModLongRing(pk, false);
159        GenPolynomialRing<ModInteger> pkfac = new GenPolynomialRing<ModInteger>(pkm, pfac);
160        dfac = new GenPolynomialRing<BigInteger>(mi, pfac);
161
162        //GreatestCommonDivisor<BigInteger> ufd = GCDFactory.getProxy(mi);
163        GreatestCommonDivisor<BigInteger> ufd = GCDFactory.getImplementation(mi);
164
165        //ModLong v = pl.fromInteger(3L);
166        ModInteger v = pkm.fromInteger(5L);
167        List<ModInteger> V = new ArrayList<ModInteger>(1);
168        V.add(v);
169        V.add(pkm.fromInteger(3L));
170        //System.out.println("V = " + V);
171
172        GenPolynomial<ModInteger> ap;
173        GenPolynomial<ModInteger> bp;
174        GenPolynomial<ModInteger> cp;
175        //GenPolynomial<ModInteger> dp;
176        GenPolynomial<ModInteger> sp;
177        GenPolynomial<ModInteger> tp;
178        GenPolynomial<ModInteger> rp;
179
180        for (int i = 1; i < 2; i++) {
181            a = dfac.random(kl + 7 * i, ll, el + 3, q).abs();
182            b = dfac.random(kl + 7 * i, ll, el + 2, q).abs();
183            //a = dfac.parse(" y^2 + 2 x y - 3 y + x^2 - 3 x - 4 ");
184            //b = dfac.parse(" y^2 + 2 x y + 5 y + x^2 + 5 x + 4 ");
185            //a = dfac.parse(" (x - 4 + y)*( x + y + 1 ) ");
186            //b = dfac.parse(" (x + 4 + y)*( x + y + 1 ) ");
187            //a = dfac.parse(" (x - 4 + y) ");
188            ///a = dfac.parse(" (x - 13 + y) ");
189            ///b = dfac.parse(" (x + 4 + y) ");
190            //a = dfac.parse(" (x - 1)*(1 + x) ");
191            //b = dfac.parse(" (x - 2)*(3 + x) ");
192            //a = dfac.parse(" (x - 1)*(y + x) ");
193            //b = dfac.parse(" (x - 2)*(y - x) ");
194            //a = dfac.parse(" (x - 1)*(y + 1) ");
195            //b = dfac.parse(" (x - 2)*(y - 1) ");
196            //a = dfac.parse(" (x - 1)*(y^2 + 1) ");
197            //b = dfac.parse(" (x - 2)*(y^2 - 1) ");
198            //a = dfac.parse(" z + (y - 1)*(1 + y) ");
199            //b = dfac.parse(" z + (y - 2)*(2 + y) ");
200            //a = dfac.parse(" (y - 1)*(1 + y) ");
201            //b = dfac.parse(" (y - 2)*(2 + y) ");
202            ///a = dfac.parse(" (y - 3) "); //2 // tp = 47045880 = -1
203            ///b = dfac.parse(" (y - 1) "); // sp = 1
204            //a = dfac.parse(" (y - 4) "); // tp = 15681960
205            //b = dfac.parse(" (y - 1) "); // sp = 31363921
206            //a = dfac.parse(" (x - 3) "); // tp = 15681960,  1238049
207            //b = dfac.parse(" (x - 1) "); // sp = 31363921, -1238049
208            //a = dfac.parse(" ( y^2 + x^3 - 2 x ) ");
209            //b = dfac.parse(" ( y - x^2 + 3 ) ");
210
211            c = ufd.gcd(a, b);
212            //System.out.println("\na     = " + a);
213            //System.out.println("b     = " + b);
214            //System.out.println("c     = " + c);
215
216            if (!c.isUnit()) {
217                continue;
218            }
219            //c = dfac.parse(" x y z ");
220            //System.out.println("c     = " + c);
221
222            ap = PolyUtil.<ModInteger> fromIntegerCoefficients(pkfac, a);
223            bp = PolyUtil.<ModInteger> fromIntegerCoefficients(pkfac, b);
224            cp = PolyUtil.<ModInteger> fromIntegerCoefficients(pkfac, c);
225            //if (ap.degree(0) < 1 || bp.degree(0) < 1) {
226            //    continue;
227            //}
228            //System.out.println("\nap     = " + ap);
229            //System.out.println("bp     = " + bp);
230            //System.out.println("cp     = " + cp);
231
232            List<GenPolynomial<ModInteger>> lift;
233            try {
234                lift = HenselMultUtil.<ModInteger> liftDiophant(ap, bp, cp, V, d, k); // 5 is max
235                sp = lift.get(0);
236                tp = lift.get(1);
237                //System.out.println("liftMultiDiophant:");
238                //System.out.println("sp     = " + sp);
239                //System.out.println("tp     = " + tp);
240                //System.out.println("isDiophantLift: " +  HenselUtil.<ModInteger> isDiophantLift(bp,ap,sp,tp,cp) );
241
242                GenPolynomialRing<ModInteger> qfac = sp.ring;
243                //System.out.println("qfac   = " + qfac.toScript());
244                assertEquals("pkfac == qfac: " + qfac, pkfac, qfac);
245
246                rp = bp.multiply(sp).sum(ap.multiply(tp)); // order
247                assertFalse("rp != null: " + rp, rp == null);
248                //System.out.println("\nrp     = " + rp);
249
250                //not true: System.out.println("a s + b t = c: " + cp.equals(rp));
251                //assertEquals("a s + b t = c ", dp,rp);
252
253                //GenPolynomialRing<ModInteger> cfac = pkfac.contract(1);
254                ModInteger vp = pkfac.coFac.fromInteger(V.get(0).getSymmetricInteger().getVal());
255                GenPolynomial<ModInteger> ya = pkfac.univariate(1);
256                ya = ya.subtract(vp);
257                ya = Power.<GenPolynomial<ModInteger>> power(pkfac, ya, d + 1);
258                //System.out.println("ya     = " + ya);
259                List<GenPolynomial<ModInteger>> Y = new ArrayList<GenPolynomial<ModInteger>>();
260                Y.add(ya);
261                vp = pkfac.coFac.fromInteger(V.get(1).getSymmetricInteger().getVal());
262                GenPolynomial<ModInteger> za = pkfac.univariate(0);
263                za = za.subtract(vp);
264                za = Power.<GenPolynomial<ModInteger>> power(pkfac, za, d + 1);
265                //System.out.println("za     = " + za);
266                Y.add(za);
267                //System.out.println("\nY      = " + Y);
268                Ideal<ModInteger> Yi = new Ideal<ModInteger>(pkfac, Y);
269                //System.out.println("Yi     = " + Yi);
270                ResidueRing<ModInteger> Yr = new ResidueRing<ModInteger>(Yi);
271                //System.out.println("Yr     = " + Yr);
272
273                Residue<ModInteger> apr = new Residue<ModInteger>(Yr, ap);
274                Residue<ModInteger> bpr = new Residue<ModInteger>(Yr, bp);
275                Residue<ModInteger> cpr = new Residue<ModInteger>(Yr, cp);
276                Residue<ModInteger> spr = new Residue<ModInteger>(Yr, sp);
277                Residue<ModInteger> tpr = new Residue<ModInteger>(Yr, tp);
278                Residue<ModInteger> rpr = bpr.multiply(spr).sum(apr.multiply(tpr)); // order
279                //System.out.println("\napr     = " + apr);
280                //System.out.println("bpr     = " + bpr);
281                //System.out.println("cpr     = " + cpr);
282                //System.out.println("spr     = " + spr);
283                //System.out.println("tpr     = " + tpr);
284                //System.out.println("rpr     = " + rpr);
285                //System.out.println("ar sr + br tr = cr: " + cpr.equals(rpr) + "\n");
286                assertEquals("ar sr + br tr = cr ", cpr, rpr);
287            } catch (NoLiftingException e) {
288                // can happen: fail("" + e);
289                System.out.println("e = " + e);
290            }
291        }
292    }
293
294
295    /**
296     * Test multivariate diophant lifting list.
297     */
298    public void testDiophantLiftingList() {
299        java.math.BigInteger p;
300        //p = getPrime1();
301        p = new java.math.BigInteger("19");
302        //p = new java.math.BigInteger("5");
303        BigInteger m = new BigInteger(p);
304
305        ModIntegerRing pm = new ModIntegerRing(p, false);
306        //ModLongRing pl = new ModLongRing(p, false);
307        //GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(pm, 2, tord, new String[]{ "x", "y" });
308        GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(pm, 3, tord, new String[] {
309                "x", "y", "z" });
310        //GenPolynomialRing<ModInteger> pfac = new GenPolynomialRing<ModInteger>(pm, 4, tord, new String[]{ "w", "x", "y", "z" });
311        //GenPolynomialRing<BigInteger> ifac = new GenPolynomialRing<BigInteger>(new BigInteger(),pfac);
312
313        BigInteger mi = m;
314        long k = 5L;
315        long d = 3L;
316        java.math.BigInteger pk = p.pow((int) k);
317        //m = new BigInteger(pk);
318
319        ModIntegerRing pkm = new ModIntegerRing(pk, false);
320        //ModLongRing pkl = new ModLongRing(pk, false);
321        GenPolynomialRing<ModInteger> pkfac = new GenPolynomialRing<ModInteger>(pkm, pfac);
322        dfac = new GenPolynomialRing<BigInteger>(mi, pfac);
323
324        //GreatestCommonDivisor<BigInteger> ufd = GCDFactory.getProxy(mi);
325        GreatestCommonDivisor<BigInteger> ufd = GCDFactory.getImplementation(mi);
326
327        //ModLong v = pl.fromInteger(3L);
328        ModInteger v = pkm.fromInteger(5L);
329        List<ModInteger> V = new ArrayList<ModInteger>(1);
330        V.add(v);
331        V.add(pkm.fromInteger(3L));
332        if (pkfac.nvar > 3) {
333            V.add(pkm.fromInteger(7L));
334        }
335        //System.out.println("V = " + V);
336
337        GenPolynomial<ModInteger> ap;
338        GenPolynomial<ModInteger> cp;
339        //GenPolynomial<ModInteger> rp;
340
341        List<GenPolynomial<BigInteger>> A = new ArrayList<GenPolynomial<BigInteger>>();
342
343        for (int i = 1; i < 2; i++) {
344            a = dfac.random(kl + 7 * i, ll, el + 3, q).abs();
345            b = dfac.random(kl + 7 * i, ll, el + 2, q).abs();
346            c = dfac.random(kl + 7 * i, ll, el + 2, q).abs();
347            //a = dfac.parse(" z + x*y + (y - 1)*(1 + y) ");
348            //b = dfac.parse(" z - x + (y - 2)*(2 + y) ");
349            //c = dfac.parse(" z + x + (y - 2)*(2 + y) ");
350
351            A.add(a);
352            A.add(b);
353            A.add(c);
354            //System.out.println("\nA          = " + A);
355            A = ufd.coPrime(A);
356            //System.out.println("coprime(A) = " + A);
357            if (A.size() == 0) {
358                continue;
359            }
360
361            List<GenPolynomial<ModInteger>> Ap = new ArrayList<GenPolynomial<ModInteger>>(A.size());
362            for (GenPolynomial<BigInteger> ai : A) {
363                ap = PolyUtil.<ModInteger> fromIntegerCoefficients(pkfac, ai);
364                Ap.add(ap);
365            }
366            //System.out.println("A mod p^k  = " + Ap);
367            cp = pkfac.parse(" x y z + x y + x ");
368            //cp = pkfac.parse(" x y + x ");
369            //cp = Ap.get(0).multiply(Ap.get(1));
370            //System.out.println("cp         = " + cp);
371
372            GenPolynomial<ModInteger> B = pkfac.getONE();
373            for (GenPolynomial<ModInteger> bp : Ap) {
374                B = B.multiply(bp);
375            }
376            //System.out.println("B          = " + B);
377            List<GenPolynomial<ModInteger>> Bp = new ArrayList<GenPolynomial<ModInteger>>(A.size());
378            for (GenPolynomial<ModInteger> bp : Ap) {
379                GenPolynomial<ModInteger> b = PolyUtil.<ModInteger> basePseudoDivide(B, bp);
380                if (b.isZERO()) {
381                    System.out.println("b == 0");
382                    return;
383                }
384                Bp.add(b);
385            }
386            //System.out.println("B mod p^k  = " + Bp);
387
388            try {
389                List<GenPolynomial<ModInteger>> lift;
390                lift = HenselMultUtil.<ModInteger> liftDiophant(Ap, cp, V, d, k); // 5 is max
391                //System.out.println("liftMultiDiophant:");
392                //System.out.println("lift   = " + lift);
393
394                GenPolynomialRing<ModInteger> qfac = lift.get(0).ring;
395                assertEquals("pkfac == qfac: " + qfac, pkfac, qfac);
396
397                //GenPolynomialRing<ModInteger> cfac = pkfac.contract(1);
398                List<GenPolynomial<ModInteger>> Y = new ArrayList<GenPolynomial<ModInteger>>();
399
400                for (int j = 0; j < V.size(); j++) {
401                    ModInteger vp = pkfac.coFac.fromInteger(V.get(j).getSymmetricInteger().getVal());
402                    GenPolynomial<ModInteger> ya = pkfac.univariate(pkfac.nvar - 2 - j);
403                    ya = ya.subtract(vp);
404                    //ya = Power.<GenPolynomial<ModInteger>>power(pkfac,ya,d+1);
405                    //System.out.println("ya     = " + ya);
406                    Y.add(ya);
407                }
408                //System.out.println("\nY      = " + Y);
409                Ideal<ModInteger> Yi = new Ideal<ModInteger>(pkfac, Y);
410                //System.out.println("Yi     = " + Yi);
411                Yi = Yi.power((int) d + 1);
412                //System.out.println("Yi     = " + Yi);
413                ResidueRing<ModInteger> Yr = new ResidueRing<ModInteger>(Yi);
414                //System.out.println("\nYr     = " + Yr);
415
416                List<Residue<ModInteger>> Bpr = new ArrayList<Residue<ModInteger>>(A.size());
417                for (GenPolynomial<ModInteger> tp : Bp) {
418                    Residue<ModInteger> apr = new Residue<ModInteger>(Yr, tp);
419                    Bpr.add(apr);
420                }
421                List<Residue<ModInteger>> Spr = new ArrayList<Residue<ModInteger>>(A.size());
422                for (GenPolynomial<ModInteger> sp : lift) {
423                    Residue<ModInteger> apr = new Residue<ModInteger>(Yr, sp);
424                    if (apr.isZERO()) {
425                        System.out.println("apr == 0: " + sp);
426                        //return;
427                    }
428                    Spr.add(apr);
429                }
430                //System.out.println("\nBpr     = " + Bpr);
431                //System.out.println("Spr     = " + Spr);
432
433                Residue<ModInteger> cpr = new Residue<ModInteger>(Yr, cp);
434                Residue<ModInteger> rpr = Yr.getZERO();
435                int j = 0;
436                for (Residue<ModInteger> r : Bpr) {
437                    rpr = rpr.sum(r.multiply(Spr.get(j++)));
438                }
439                //System.out.println("cpr     = " + cpr);
440                //System.out.println("rpr     = " + rpr);
441                assertEquals("sum_i( br sr ) = cr ", cpr, rpr);
442            } catch (ArithmeticException e) {
443                // ok, can happen
444            } catch (NoLiftingException e) {
445                // can now happen: fail("" + e);
446                System.out.println("e = " + e);
447            }
448        }
449    }
450
451}