Source code

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