001/*
002 * $Id$
003 */
004
005package edu.jas.arith;
006
007
008import java.io.StringReader;
009import java.util.ArrayList;
010import java.util.List;
011
012import edu.jas.kern.PrettyPrint;
013import edu.jas.structure.NotInvertibleException;
014
015import junit.framework.Test;
016import junit.framework.TestCase;
017import junit.framework.TestSuite;
018
019
020/**
021 * ModLong tests with JUnit.
022 * @author Heinz Kredel
023 */
024
025public class ModLongTest extends TestCase {
026
027
028    /**
029     * main.
030     */
031    public static void main(String[] args) {
032        junit.textui.TestRunner.run(suite());
033    }
034
035
036    /**
037     * Constructs a <CODE>ModLongTest</CODE> object.
038     * @param name String
039     */
040    public ModLongTest(String name) {
041        super(name);
042    }
043
044
045    /**
046     */
047    public static Test suite() {
048        TestSuite suite = new TestSuite(ModLongTest.class);
049        return suite;
050    }
051
052
053    ModLongRing zm, z1, z2;
054
055
056    ModLong a, b, c, d, e;
057
058
059    @Override
060    protected void setUp() {
061        zm = z1 = z2 = null;
062        a = b = c = d = e = null;
063    }
064
065
066    @Override
067    protected void tearDown() {
068        zm = z1 = z2 = null;
069        a = b = c = d = e = null;
070    }
071
072
073    protected static java.math.BigInteger getPrime1() {
074        long prime = 2; //2^60-93; // 2^30-35; //19; knuth (2,390)
075        for (int i = 1; i < 30; i++) {
076            prime *= 2;
077        }
078        //prime -= 93;
079        prime -= 35;
080        //System.out.println("p1 = " + prime);
081        return new java.math.BigInteger("" + prime);
082    }
083
084
085    protected static java.math.BigInteger getPrime2() {
086        long prime = 2; //2^60-93; // 2^30-35; //19; knuth (2,390)
087        for (int i = 1; i < 60; i++) {
088            prime *= 2;
089        }
090        prime -= 93;
091        //System.out.println("p2 = " + prime);
092        return new java.math.BigInteger("" + prime);
093    }
094
095
096    protected static java.math.BigInteger getPrime3() {
097        int prime = 2; //2^15-135; //2^60-93; // 2^30-35; //19; knuth (2,390)
098        for (int i = 1; i < 15; i++) {
099            prime *= 2;
100        }
101        prime -= 135;
102        //System.out.println("p1 = " + prime);
103        return new java.math.BigInteger("" + prime);
104    }
105
106    
107    protected static java.math.BigInteger getPrime4() {
108        int prime = 37;
109        //System.out.println("p2 = " + prime);
110        return new java.math.BigInteger("" + prime);
111    }
112
113    
114    /**
115     * Test static initialization and constants.
116     */
117    public void testConstants() {
118        zm = new ModLongRing(5);
119        d = new ModLong(zm, 11);
120        a = zm.getZERO();
121        b = zm.getONE();
122        c = b.subtract(b);
123
124        assertEquals("1-1 = 0", c, a);
125        assertTrue("1-1 = 0", c.isZERO());
126        assertTrue("1 = 1", b.isONE());
127    }
128
129
130    /**
131     * Test bitLength.
132     */
133    public void testBitLength() {
134        zm = new ModLongRing(163);
135        a = zm.getZERO();
136        b = zm.getONE();
137        c = zm.random(30);
138        //System.out.println("c = " + c);
139        //System.out.println("len(c) = " + c.bitLength());
140
141        assertEquals("len(0) = 1", 1L, a.bitLength());
142        assertEquals("len(1) = 2", 2, b.bitLength());
143        assertEquals("len(-1) = len(mod)", BigInteger.bitLength(zm.modul), b.negate().bitLength());
144        assertTrue("len(random) >= 1", 1 <= c.bitLength());
145    }
146
147
148    /**
149     * Test constructor and toString.
150     */
151    public void testConstructor() {
152        zm = new ModLongRing("5");
153        a = new ModLong(zm, "64");
154        b = new ModLong(zm, "34");
155
156        assertEquals("64(5) = 34(5)", a, b);
157
158        zm = new ModLongRing("7");
159        a = new ModLong(zm, "-4");
160        b = new ModLong(zm, "3");
161
162        assertEquals("-4(7) = 3(7)", a, b);
163
164        String s = "61111111111111111";
165        zm = new ModLongRing("10");
166        a = new ModLong(zm, s);
167        String t = a.toString();
168
169        if (PrettyPrint.isTrue()) {
170            String st = "1";
171            assertEquals("stringConstr = toString", st, t);
172        } else {
173            String st = "1 mod(10)";
174            assertEquals("stringConstr = toString", st, t);
175        }
176
177        zm = new ModLongRing(7);
178        a = new ModLong(zm, 1);
179        b = new ModLong(zm, -1);
180        c = b.sum(a);
181
182        assertTrue("1 = 1", a.isONE());
183        assertTrue("1 = 1", b.isUnit());
184        assertEquals("1+(-1) = 0", c, zm.getZERO());
185
186        zm = new ModLongRing(5);
187        a = new ModLong(zm, 3);
188        b = new ModLong(zm, 0);
189        c = zm.parse(" 13 ");
190        assertEquals("3(5) = 3(5)", a, c);
191
192        StringReader sr = new StringReader("  13\n w ");
193        c = zm.parse(sr);
194        assertEquals("3(5) = 3(5)", a, c);
195        //System.out.println("c = " + c);
196    }
197
198
199    /**
200     * Test random modular integers.
201     */
202    public void testRandom() {
203        zm = new ModLongRing(19);
204        a = zm.random(500);
205        b = a.copy();
206        c = b.subtract(a);
207
208        assertEquals("a-b = 0", c, zm.getZERO());
209
210        d = new ModLong(new ModLongRing(b.getModul()), b.getVal());
211        assertEquals("sign(a-a) = 0", 0, b.compareTo(d));
212    }
213
214
215    /**
216     * Test addition.
217     * 
218     */
219    public void testAddition() {
220        zm = new ModLongRing(19);
221
222        a = zm.random(100);
223        b = a.sum(a);
224        c = b.subtract(a);
225
226        assertEquals("a+a-a = a", c, a);
227        assertEquals("a+a-a = a", 0, c.compareTo(a));
228
229        d = a.sum(zm.getZERO());
230        assertEquals("a+0 = a", d, a);
231        d = a.subtract(zm.getZERO());
232        assertEquals("a-0 = a", d, a);
233        d = a.subtract(a);
234        assertEquals("a-a = 0", d, zm.getZERO());
235
236    }
237
238
239    /**
240     * Test multiplication.
241     */
242    @SuppressWarnings("unchecked")
243    public void testMultiplication() {
244        zm = new ModLongRing(5);
245        d = new ModLong(zm, 11);
246
247        a = zm.random(100);
248        if (a.isZERO()) {
249            a = d;
250        }
251        b = a.multiply(a);
252        c = b.divide(a);
253
254        assertEquals("a*a/a = a", c, a);
255        assertEquals("a*a/a = a", 0, c.compareTo(a));
256
257        d = a.multiply(zm.getONE());
258        assertEquals("a*1 = a", d, a);
259        d = a.divide(zm.getONE());
260        assertEquals("a/1 = a", d, a);
261
262        a = zm.random(100);
263        if (a.isZERO()) {
264            a = d;
265        }
266        b = a.inverse();
267        c = a.multiply(b);
268
269        assertTrue("a*1/a = 1", c.isONE());
270
271        try {
272            a = zm.getZERO().inverse();
273            fail("0 invertible");
274        } catch (NotInvertibleException expected) {
275            //ok
276        }
277
278        zm = new ModLongRing(5 * 3);
279        a = new ModLong(zm, 5);
280        assertFalse("5 !unit mod 15", a.isUnit());
281
282        try {
283            b = a.inverse();
284            fail("5 invertible");
285        } catch (ModularNotInvertibleException expected) {
286            //ok
287            //expected.printStackTrace();
288            assertTrue("f  = 15 ", expected.f.equals(new BigInteger(15)));
289            assertTrue("f1 =  5 ", expected.f1.equals(new BigInteger(5)));
290            assertTrue("f2 =  3 ", expected.f2.equals(new BigInteger(3)));
291            assertTrue("f  =  f1*f2 ", expected.f.equals(expected.f1.multiply(expected.f2)));
292        } catch (NotInvertibleException e) {
293            //e.printStackTrace();
294            fail("wrong exception " + e);
295        }
296    }
297
298
299    /**
300     * Test chinese remainder.
301     */
302    public void testChineseRemainder() {
303        zm = new ModLongRing(19 * 13);
304        a = zm.random(9);
305        //System.out.println("a = " + a);
306        z1 = new ModLongRing(19);
307        b = new ModLong(z1, a.getVal());
308        //System.out.println("b = " + b);
309        z2 = new ModLongRing(13);
310        c = new ModLong(z2, a.getVal());
311        //System.out.println("c = " + c);
312        d = new ModLong(z2, 19);
313        d = d.inverse();
314        //System.out.println("d = " + d);
315
316        e = zm.chineseRemainder(b, d, c);
317        //System.out.println("e = " + e);
318
319        assertEquals("cra(a mod 19,a mod 13) = a", a, e);
320
321        java.math.BigInteger p1 = getPrime2();
322        try {
323            z1 = new ModLongRing(p1);
324            fail("p1 too large");
325        } catch (IllegalArgumentException e) {
326            //pass
327        }
328        p1 = getPrime3();
329        java.math.BigInteger p2 = new java.math.BigInteger("19"); 
330        java.math.BigInteger p1p2 = p1.multiply(p2);
331        //System.out.println("p1p2 = " + p1p2);
332        //System.out.println("prime p1 ? = " + p1.isProbablePrime(66));
333        //System.out.println("prime p2 ? = " + p2.isProbablePrime(33));
334        //System.out.println("prime p1p1 ? = " + p1p2.isProbablePrime(3));
335        zm = new ModLongRing(p1p2);
336        z1 = new ModLongRing(p1);
337        z2 = new ModLongRing(p2);
338
339        for (int i = 0; i < 5; i++) {
340            a = zm.random((59 + 29) / 2); //60+30 );
341            //System.out.println("a = " + a);
342            b = new ModLong(z1, a.getVal());
343            //System.out.println("b = " + b);
344            c = new ModLong(z2, a.getVal());
345            //System.out.println("c = " + c);
346            ModLong di = new ModLong(z2, p1);
347            d = di.inverse();
348            //System.out.println("d = " + d);
349
350            e = zm.chineseRemainder(b, d, c);
351            //System.out.println("e = " + e);
352
353            assertEquals("cra(a mod p1,a mod p2) = a ", a, e);
354        }
355    }
356
357
358    /**
359     * Test chinese remainder of lists.
360     */
361    public void testChineseRemainderLists() {
362        zm = new ModLongRing(19 * 13);
363        z1 = new ModLongRing(19);
364        z2 = new ModLongRing(13);
365
366        List<ModLong> L1 = new ArrayList<ModLong>();
367        List<ModLong> L2 = new ArrayList<ModLong>();
368        List<ModLong> L;
369
370        for (int i = 0; i < 7; i++) {
371            a = zm.random(9);
372            //System.out.println("a = " + a);
373            b = new ModLong(z1, a.getVal());
374            //System.out.println("b = " + b);
375            c = new ModLong(z2, a.getVal());
376            //System.out.println("c = " + c);
377            L1.add(b);
378            L2.add(c);
379        }
380        //System.out.println("L1 = " + L1);
381        //System.out.println("L2 = " + L2);
382
383        L = ModLongRing.chineseRemainder(z1.getONE(), z2.getONE(), L1, L2);
384        //System.out.println("L = " + L);
385        assertEquals("19 * 13) = a.modul: ", zm, L.get(0).ring);
386
387        for (ModLong d : L) {
388            b = new ModLong(z1, d.getVal());
389            //System.out.println("b = " + b);
390            c = new ModLong(z2, d.getVal());
391            //System.out.println("c = " + c);
392            assertTrue("cra(a mod 19, a mod 13) = a: ", L1.contains(b));
393            assertTrue("cra(a mod 19, a mod 13) = a: ", L2.contains(c));
394        }
395    }
396
397
398    /**
399     * Test timing ModLong to ModInteger.
400     */
401    public void testTiming() {
402        zm = new ModLongRing(getPrime1());
403        a = zm.random(9);
404        //System.out.println("a = " + a);
405        b = zm.random(9);
406        //System.out.println("b = " + b);
407        c = zm.getONE();
408        //System.out.println("c = " + c);
409
410        ModIntegerRing ZM = new ModIntegerRing(zm.modul);
411        ModInteger A = new ModInteger(ZM, a.getVal());
412        ModInteger B = new ModInteger(ZM, b.getVal());
413        ModInteger C = ZM.getONE();
414
415        int run = 1000; //000;
416        long t = System.currentTimeMillis();
417        for (int i = 0; i < run; i++) {
418            if (c.isZERO()) {
419                c = zm.getONE();
420            }
421            c = a.sum(b.divide(c));
422        }
423        t = System.currentTimeMillis() - t;
424        //System.out.println("long time = " + t);
425
426        ModInteger D = new ModInteger(ZM, c.getVal());
427        t = System.currentTimeMillis();
428        for (int i = 0; i < run; i++) {
429            if (C.isZERO()) {
430                C = ZM.getONE();
431            }
432            C = A.sum(B.divide(C));
433        }
434        t = System.currentTimeMillis() - t;
435        //System.out.println("BigInteger time = " + t);
436
437        assertEquals("C == D ", C, D);
438    }
439
440
441    /**
442     * Test iterator.
443     */
444    public void testIterator() {
445        int m = 5 * 2;
446        zm = new ModLongRing(m);
447        ModLong j = null;
448        for (ModLong i : zm) {
449            //System.out.println("i = " + i);
450            j = i;
451        }
452        ModLong end = new ModLong(zm, m - 1);
453        assertTrue("j == m-1 ", j.equals(end));
454    }
455
456}