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}