001/*
002 * $Id: ModIntegerTest.java 4125 2012-08-19 19:05:22Z kredel $
003 */
004
005package edu.jas.arith;
006
007
008import java.io.StringReader;
009
010import junit.framework.Test;
011import junit.framework.TestCase;
012import junit.framework.TestSuite;
013
014import edu.jas.kern.PrettyPrint;
015import edu.jas.structure.NotInvertibleException;
016
017
018/**
019 * ModInteger and PrimeList tests with JUnit.
020 * @author Heinz Kredel.
021 */
022
023public class ModIntegerTest extends TestCase {
024
025
026    /**
027     * main.
028     */
029    public static void main(String[] args) {
030        junit.textui.TestRunner.run(suite());
031    }
032
033
034    /**
035     * Constructs a <CODE>ModIntegerTest</CODE> object.
036     * @param name String
037     */
038    public ModIntegerTest(String name) {
039        super(name);
040    }
041
042
043    /**
044     */
045    public static Test suite() {
046        TestSuite suite = new TestSuite(ModIntegerTest.class);
047        return suite;
048    }
049
050
051    ModIntegerRing zm;
052
053
054    ModIntegerRing z1;
055
056
057    ModIntegerRing z2;
058
059
060    ModInteger a;
061
062
063    ModInteger b;
064
065
066    ModInteger c;
067
068
069    ModInteger d;
070
071
072    ModInteger e;
073
074
075    @Override
076    protected void setUp() {
077        zm = z1 = z2 = null;
078        a = b = c = d = e = null;
079    }
080
081
082    @Override
083    protected void tearDown() {
084        zm = z1 = z2 = null;
085        a = b = c = d = e = null;
086    }
087
088
089    protected static java.math.BigInteger getPrime1() {
090        long prime = 2; //2^60-93; // 2^30-35; //19; knuth (2,390)
091        for (int i = 1; i < 60; i++) {
092            prime *= 2;
093        }
094        prime -= 93;
095        //prime = 37;
096        //System.out.println("p1 = " + prime);
097        return new java.math.BigInteger("" + prime);
098    }
099
100
101    protected static java.math.BigInteger getPrime2() {
102        long prime = 2; //2^60-93; // 2^30-35; //19; knuth (2,390)
103        for (int i = 1; i < 30; i++) {
104            prime *= 2;
105        }
106        prime -= 35;
107        //prime = 19;
108        //System.out.println("p2 = " + prime);
109        return new java.math.BigInteger("" + prime);
110    }
111
112
113    /**
114     * Test static initialization and constants.
115     * 
116     */
117    public void testConstants() {
118        zm = new ModIntegerRing(5);
119        d = new ModInteger(zm, 11);
120        a = zm.getZERO();
121        b = zm.getONE();
122        c = ModInteger.MIDIF(b, 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    /**
132     * Test constructor and toString.
133     * 
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     */
187    public void testRandom() {
188        zm = new ModIntegerRing(19);
189        a = zm.random(500);
190        b = a.copy();
191        c = ModInteger.MIDIF(b, a);
192
193        assertEquals("a-b = 0", c, zm.getZERO());
194
195        d = new ModInteger(new ModIntegerRing(b.getModul()), b.getVal());
196        assertEquals("sign(a-a) = 0", 0, b.compareTo(d));
197    }
198
199
200    /**
201     * Test addition.
202     * 
203     */
204    public void testAddition() {
205        zm = new ModIntegerRing(19);
206
207        a = zm.random(100);
208        b = ModInteger.MISUM(a, a);
209        c = ModInteger.MIDIF(b, a);
210
211        assertEquals("a+a-a = a", c, a);
212        assertEquals("a+a-a = a", 0, ModInteger.MICOMP(c, a));
213
214        d = ModInteger.MISUM(a, zm.getZERO());
215        assertEquals("a+0 = a", d, a);
216        d = ModInteger.MIDIF(a, zm.getZERO());
217        assertEquals("a-0 = a", d, a);
218        d = ModInteger.MIDIF(a, a);
219        assertEquals("a-a = 0", d, zm.getZERO());
220
221    }
222
223
224    /**
225     * Test multiplication.
226     * 
227     */
228    public void testMultiplication() {
229        zm = new ModIntegerRing(5);
230        d = new ModInteger(zm, 11);
231
232        a = zm.random(100);
233        if (a.isZERO()) {
234            a = d;
235        }
236        b = ModInteger.MIPROD(a, a);
237        c = ModInteger.MIQ(b, a);
238
239        assertEquals("a*a/a = a", c, a);
240        assertEquals("a*a/a = a", 0, c.compareTo(a));
241
242        d = ModInteger.MIPROD(a, zm.getONE());
243        assertEquals("a*1 = a", d, a);
244        d = ModInteger.MIQ(a, zm.getONE());
245        assertEquals("a/1 = a", d, a);
246
247        a = zm.random(100);
248        if (a.isZERO()) {
249            a = d;
250        }
251        b = ModInteger.MIINV(a);
252        c = ModInteger.MIPROD(a, b);
253
254        assertTrue("a*1/a = 1", c.isONE());
255
256        try {
257            a = zm.getZERO().inverse();
258            fail("0 invertible");
259        } catch (NotInvertibleException expected) {
260            // ok
261        }
262
263        zm = new ModIntegerRing(5 * 3);
264        a = new ModInteger(zm, 5);
265        assertFalse("5 !unit mod 15", a.isUnit());
266
267        try {
268            b = a.inverse();
269            fail("5 invertible");
270        } catch (ModularNotInvertibleException expected) {
271            //ok
272            //expected.printStackTrace();
273            assertTrue("f  = 15 ", expected.f.equals(new BigInteger(15)));
274            assertTrue("f1 =  5 ", expected.f1.equals(new BigInteger(5)));
275            assertTrue("f2 =  3 ", expected.f2.equals(new BigInteger(3)));
276            assertTrue("f  =  f1*f2 ", expected.f.equals(expected.f1.multiply(expected.f2)));
277        } catch (NotInvertibleException e) {
278            //e.printStackTrace();
279            fail("wrong exception " + e);
280        }
281    }
282
283
284    /**
285     * Test chinese remainder.
286     * 
287     */
288    public void testChineseRemainder() {
289        zm = new ModIntegerRing(19 * 13);
290        a = zm.random(9);
291        //System.out.println("a = " + a);
292        z1 = new ModIntegerRing(19);
293        b = new ModInteger(z1, a.getVal().longValue());
294        //System.out.println("b = " + b);
295        z2 = new ModIntegerRing(13);
296        c = new ModInteger(z2, a.getVal().longValue());
297        //System.out.println("c = " + c);
298        d = new ModInteger(z2, 19);
299        d = d.inverse();
300        //System.out.println("d = " + d);
301
302        e = zm.chineseRemainder(b, d, c);
303        //System.out.println("e = " + e);
304
305        assertEquals("cra(a mod 19,a mod 13) = a", a, e);
306
307
308        java.math.BigInteger p1 = getPrime1();
309        java.math.BigInteger p2 = getPrime2();
310        java.math.BigInteger p1p2 = p1.multiply(p2);
311        //System.out.println("p1p2 = " + p1p2);
312        //System.out.println("prime p1 ? = " + p1.isProbablePrime(66));
313        //System.out.println("prime p2 ? = " + p2.isProbablePrime(33));
314        //System.out.println("prime p1p1 ? = " + p1p2.isProbablePrime(3));
315        zm = new ModIntegerRing(p1p2);
316        z1 = new ModIntegerRing(p1);
317        z2 = new ModIntegerRing(p2);
318
319        for (int i = 0; i < 5; i++) {
320            a = zm.random((59 + 29) / 2); //60+30 );
321            //System.out.println("a = " + a);
322            b = new ModInteger(z1, a.getVal());
323            //System.out.println("b = " + b);
324            c = new ModInteger(z2, a.getVal());
325            //System.out.println("c = " + c);
326            ModInteger di = new ModInteger(z2, p1);
327            d = di.inverse();
328            //System.out.println("d = " + d);
329
330            e = zm.chineseRemainder(b, d, c);
331            //System.out.println("e = " + e);
332
333            assertEquals("cra(a mod p1,a mod p2) = a", a, e);
334        }
335    }
336
337
338    /**
339     * Test prime list.
340     * 
341     */
342    public void testPrime() {
343        PrimeList primes = new PrimeList();
344        //System.out.println("primes = " + primes);
345
346        //assertTrue("all primes ", primes.checkPrimes() );
347
348        int i = 0;
349        //System.out.println("primes = ");
350        for (java.math.BigInteger p : primes) {
351            assertFalse("p != null", p == null);
352            //System.out.print("" + p);
353            if (i++ > 50) {
354                break;
355            }
356            //System.out.print(", ");
357        }
358        //System.out.println();
359
360        //System.out.println("primes = " + primes);
361
362        assertTrue("all primes ", primes.checkPrimes());
363    }
364
365
366    /**
367     * Test Mersenne prime list.
368     * 
369     */
370    public void testMersennePrime() {
371        PrimeList primes = new PrimeList(PrimeList.Range.mersenne);
372        //System.out.println("primes = " + primes);
373
374        //assertTrue("all primes ", primes.checkPrimes() );
375
376        int i = 1;
377        //System.out.println("primes = ");
378        for (java.math.BigInteger p : primes) {
379            assertFalse("p != null", p == null);
380            //System.out.println(i + " = " + p);
381            if (i++ > 23) {
382                break;
383            }
384            //System.out.print(", ");
385        }
386        //System.out.println();
387
388        //System.out.println("primes = " + primes);
389
390        assertTrue("all primes ", primes.checkPrimes(15));
391    }
392
393
394    /**
395     * Test iterator.
396     */
397    public void testIterator() {
398        int m = 5 * 2;
399        zm = new ModIntegerRing(m);
400        ModInteger j = null;
401        for (ModInteger i : zm) {
402            //System.out.println("i = " + i);
403            j = i;
404        }
405        ModInteger end = new ModInteger(zm, m - 1);
406        assertTrue("j == m-1 ", j.equals(end));
407    }
408
409}