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}