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