1 /* 2 * Copyright (c) 1998, 2020, Oracle and/or its affiliates. All rights reserved. 3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. 4 * 5 * This code is free software; you can redistribute it and/or modify it 6 * under the terms of the GNU General Public License version 2 only, as 7 * published by the Free Software Foundation. 8 * 9 * This code is distributed in the hope that it will be useful, but WITHOUT 10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or 11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 12 * version 2 for more details (a copy is included in the LICENSE file that 13 * accompanied this code). 14 * 15 * You should have received a copy of the GNU General Public License version 16 * 2 along with this work; if not, write to the Free Software Foundation, 17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. 18 * 19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA 20 * or visit www.oracle.com if you need additional information or have any 21 * questions. 22 */ 23 24 /* 25 * @test 26 * @library /test/lib 27 * @build jdk.test.lib.RandomFactory 28 * @run main BigIntegerTest 29 * @bug 4181191 4161971 4227146 4194389 4823171 4624738 4812225 4837946 4026465 8074460 8078672 8032027 8229845 30 * @summary tests methods in BigInteger (use -Dseed=X to set PRNG seed) 31 * @run main/timeout=400 BigIntegerTest 32 * @author madbot 33 * @key randomness 34 */ 35 package test.java.math.BigInteger; 36 37 import android.platform.test.annotations.LargeTest; 38 39 import java.io.ByteArrayInputStream; 40 import java.io.ByteArrayOutputStream; 41 import java.io.ObjectInputStream; 42 import java.io.ObjectOutputStream; 43 import java.math.BigDecimal; 44 import java.math.BigInteger; 45 import java.util.Random; 46 import java.util.function.Function; 47 import java.util.stream.Collectors; 48 import java.util.stream.DoubleStream; 49 import java.util.stream.IntStream; 50 import java.util.stream.LongStream; 51 import java.util.stream.Stream; 52 53 import org.testng.Assert; 54 import org.testng.annotations.Test; 55 56 /** 57 * This is a simple test class created to ensure that the results 58 * generated by BigInteger adhere to certain identities. Passing 59 * this test is a strong assurance that the BigInteger operations 60 * are working correctly. 61 * 62 * Four arguments may be specified which give the number of 63 * decimal digits you desire in the four batches of test numbers. 64 * 65 * The tests are performed on arrays of random numbers which are 66 * generated by a Random class as well as special cases which 67 * throw in boundary numbers such as 0, 1, maximum sized, etc. 68 * 69 */ 70 71 // Android-changed: Replace error counting with asserts. 72 public class BigIntegerTest { 73 // 74 // Bit large number thresholds based on the int thresholds 75 // defined in BigInteger itself: 76 // 77 // KARATSUBA_THRESHOLD = 80 ints = 2560 bits 78 // TOOM_COOK_THRESHOLD = 240 ints = 7680 bits 79 // KARATSUBA_SQUARE_THRESHOLD = 128 ints = 4096 bits 80 // TOOM_COOK_SQUARE_THRESHOLD = 216 ints = 6912 bits 81 // 82 // SCHOENHAGE_BASE_CONVERSION_THRESHOLD = 20 ints = 640 bits 83 // 84 // BURNIKEL_ZIEGLER_THRESHOLD = 80 ints = 2560 bits 85 // 86 static final int BITS_KARATSUBA = 2560; 87 static final int BITS_TOOM_COOK = 7680; 88 static final int BITS_KARATSUBA_SQUARE = 4096; 89 static final int BITS_TOOM_COOK_SQUARE = 6912; 90 static final int BITS_SCHOENHAGE_BASE = 640; 91 static final int BITS_BURNIKEL_ZIEGLER = 2560; 92 static final int BITS_BURNIKEL_ZIEGLER_OFFSET = 1280; 93 94 static final int ORDER_SMALL = 60; 95 static final int ORDER_MEDIUM = 100; 96 // #bits for testing Karatsuba 97 static final int ORDER_KARATSUBA = 2760; 98 // #bits for testing Toom-Cook and Burnikel-Ziegler 99 static final int ORDER_TOOM_COOK = 8000; 100 // #bits for testing Karatsuba squaring 101 static final int ORDER_KARATSUBA_SQUARE = 4200; 102 // #bits for testing Toom-Cook squaring 103 static final int ORDER_TOOM_COOK_SQUARE = 7000; 104 105 static final int SIZE = 1000; // numbers per batch 106 107 private static Random random = new Random(); 108 109 static boolean failure = false; 110 constructor()111 private static void constructor() { 112 // --- guard condition tests for array indexing --- 113 114 int arrayLength = 23; 115 int halfLength = arrayLength/2; 116 byte[] array = new byte[arrayLength]; 117 random.nextBytes(array); 118 119 int[][] offLen = new int[][] { // offset, length, num exceptions 120 {-1, arrayLength, 1}, // negative offset 121 {0, arrayLength, 0}, // OK 122 {1, arrayLength, 1}, // length overflow 123 {arrayLength - 1, 1, 0}, // OK 124 {arrayLength, 1, 1}, // offset overflow 125 {0, -1, 1}, // negative length 126 {halfLength, arrayLength - halfLength + 1, 1} // length overflow 127 }; 128 129 // two's complement 130 for (int[] ol : offLen) { 131 try { 132 BigInteger bi = new BigInteger(array, ol[0], ol[1]); 133 if (ol[2] == 1) { 134 Assert.fail("IndexOutOfBoundsException did not occur for " 135 + " two's complement constructor with parameters offset " 136 + ol[0] + " and length " + ol[1]); 137 } 138 } catch (IndexOutOfBoundsException e) { 139 if (ol[2] == 0) { 140 Assert.fail("Unexpected IndexOutOfBoundsException did occur for " 141 + " two's complement constructor with parameters offset " 142 + ol[0] + " and length " + ol[1]); 143 } 144 } 145 } 146 147 // sign-magnitude 148 for (int[] ol : offLen) { 149 try { 150 BigInteger bi = new BigInteger(1, array, ol[0], ol[1]); 151 if (ol[2] == 1) { 152 Assert.fail("IndexOutOfBoundsException did not occur for " 153 + " sign-magnitude constructor with parameters offset " 154 + ol[0] + " and length " + ol[1]); 155 } 156 } catch (IndexOutOfBoundsException e) { 157 if (ol[2] == 0) { 158 Assert.fail("Unexpected IndexOutOfBoundsException did occur for " 159 + " two's complement constructor with parameters offset " 160 + ol[0] + " and length " + ol[1]); 161 } 162 } 163 } 164 165 // --- tests for creation of zero-valued BigIntegers --- 166 167 byte[] magZeroLength = new byte[0]; 168 for (int signum = -1; signum <= 1; signum++) { 169 BigInteger bi = new BigInteger(signum, magZeroLength); 170 Assert.assertEquals(bi.compareTo(BigInteger.ZERO), 0, 171 "A: Zero length BigInteger != 0 for signum " + signum); 172 } 173 174 for (int signum = -1; signum <= 1; signum++) { 175 BigInteger bi = new BigInteger(signum, magZeroLength, 0, 0); 176 Assert.assertEquals(bi.compareTo(BigInteger.ZERO), 0, 177 "B: Zero length BigInteger != 0 for signum " + signum); 178 } 179 180 byte[] magNonZeroLength = new byte[42]; 181 random.nextBytes(magNonZeroLength); 182 for (int signum = -1; signum <= 1; signum++) { 183 BigInteger bi = new BigInteger(signum, magNonZeroLength, 0, 0); 184 Assert.assertEquals(bi.compareTo(BigInteger.ZERO), 0, 185 "C: Zero length BigInteger != 0 for signum " + signum); 186 } 187 188 // --- tests for accurate creation of non-zero BigIntegers --- 189 190 for (int i = 0; i < SIZE; i++) { 191 // create reference value via a different code path from those tested 192 BigInteger reference = new BigInteger(2 + random.nextInt(336), 4, random); 193 194 byte[] refArray = reference.toByteArray(); 195 int refLen = refArray.length; 196 int factor = random.nextInt(5); 197 int objLen = refArray.length + factor*random.nextInt(refArray.length) + 1; 198 int offset = random.nextInt(objLen - refLen); 199 byte[] objArray = new byte[objLen]; 200 System.arraycopy(refArray, 0, objArray, offset, refLen); 201 202 BigInteger twosComp = new BigInteger(objArray, offset, refLen); 203 Assert.assertEquals(twosComp.compareTo(reference), 0, 204 "Two's-complement BigInteger not equal for offset " + 205 offset + " and length " + refLen); 206 207 boolean isNegative = random.nextBoolean(); 208 BigInteger signMag = new BigInteger(isNegative ? -1 : 1, objArray, offset, refLen); 209 Assert.assertEquals(signMag.compareTo(isNegative ? reference.negate() : reference), 0, 210 "Sign-magnitude BigInteger not equal for offset " + 211 offset + " and length " + refLen); 212 } 213 } 214 pow(int order)215 private static void pow(int order) { 216 for (int i=0; i<SIZE; i++) { 217 // Test identity x^power == x*x*x ... *x 218 int power = random.nextInt(6) + 2; 219 BigInteger x = fetchNumber(order); 220 BigInteger y = x.pow(power); 221 BigInteger z = x; 222 223 for (int j=1; j<power; j++) 224 z = z.multiply(x); 225 226 Assert.assertEquals(y, z); 227 } 228 } 229 square(int order)230 private static void square(int order) { 231 for (int i=0; i<SIZE; i++) { 232 // Test identity x^2 == x*x 233 BigInteger x = fetchNumber(order); 234 BigInteger xx = x.multiply(x); 235 BigInteger x2 = x.pow(2); 236 237 Assert.assertEquals(x2, xx); 238 } 239 } 240 checkResult(BigInteger expected, BigInteger actual, String failureMessage)241 private static void checkResult(BigInteger expected, BigInteger actual, String failureMessage) { 242 Assert.assertEquals(expected.compareTo(actual), 0, 243 failureMessage + " - expected: " + expected + ", actual: " + actual); 244 } 245 squareRootSmall()246 private static void squareRootSmall() { 247 // A negative value should cause an exception. 248 BigInteger n = BigInteger.ONE.negate(); 249 BigInteger s; 250 try { 251 s = n.sqrt(); 252 // If sqrt() does not throw an exception that is a failure. 253 Assert.fail("sqrt() of negative number did not throw an exception"); 254 } catch (ArithmeticException expected) { 255 // A negative value should cause an exception and is not a failure. 256 } 257 258 // A zero value should return BigInteger.ZERO. 259 checkResult(BigInteger.ZERO, BigInteger.ZERO.sqrt(), "sqrt(0) != BigInteger.ZERO"); 260 261 // 1 <= value < 4 should return BigInteger.ONE. 262 long[] smalls = new long[] {1, 2, 3}; 263 for (long small : smalls) { 264 checkResult(BigInteger.ONE, BigInteger.valueOf(small).sqrt(), "sqrt("+small+") != 1"); 265 } 266 } 267 squareRoot()268 private static void squareRoot() { 269 squareRootSmall(); 270 271 272 Function<BigInteger, Void> f = (n) -> { 273 // square root of n^2 -> n 274 BigInteger n2 = n.pow(2); 275 checkResult(n, n2.sqrt(), "sqrt() n^2 -> n"); 276 277 // square root of n^2 + 1 -> n 278 BigInteger n2up = n2.add(BigInteger.ONE); 279 checkResult(n, n2up.sqrt(), "sqrt() n^2 + 1 -> n"); 280 281 // square root of (n + 1)^2 - 1 -> n 282 BigInteger up = n.add(BigInteger.ONE).pow(2).subtract(BigInteger.ONE); 283 checkResult(n, up.sqrt(), "sqrt() (n + 1)^2 - 1 -> n"); 284 285 // sqrt(n)^2 <= n 286 BigInteger s = n.sqrt(); 287 Assert.assertFalse(s.multiply(s).compareTo(n) > 0, 288 "sqrt(n)^2 > n for n = " + n); 289 290 // (sqrt(n) + 1)^2 > n 291 Assert.assertFalse(s.add(BigInteger.ONE).pow(2).compareTo(n) <= 0, 292 "(sqrt(n) + 1)^2 <= n for n = " + n); 293 return null; 294 }; 295 296 Stream.Builder<BigInteger> sb = Stream.builder(); 297 int maxExponent = Double.MAX_EXPONENT + 1; 298 for (int i = 1; i <= maxExponent; i++) { 299 BigInteger p2 = BigInteger.ONE.shiftLeft(i); 300 sb.add(p2.subtract(BigInteger.ONE)); 301 sb.add(p2); 302 sb.add(p2.add(BigInteger.ONE)); 303 } 304 sb.add((new BigDecimal(Double.MAX_VALUE)).toBigInteger()); 305 sb.add((new BigDecimal(Double.MAX_VALUE)).toBigInteger().add(BigInteger.ONE)); 306 // "squareRoot for 2^N and 2^N - 1, 1 <= N <= Double.MAX_EXPONENT" 307 sb.build().map(f).collect(Collectors.toList()); 308 309 IntStream ints = random.ints(SIZE, 4, Integer.MAX_VALUE); 310 ints.mapToObj(BigInteger::valueOf).map(f).collect(Collectors.toList()); 311 312 LongStream longs = random.longs(SIZE, (long)Integer.MAX_VALUE + 1L, 313 Long.MAX_VALUE); 314 longs.mapToObj(BigInteger::valueOf).map(f).collect(Collectors.toList()); 315 316 DoubleStream doubles = random.doubles(SIZE, 317 (double) Long.MAX_VALUE + 1.0, Math.sqrt(Double.MAX_VALUE)); 318 doubles.mapToObj(x -> BigDecimal.valueOf(x).toBigInteger()).map(f).collect(Collectors.toList()); 319 } 320 squareRootAndRemainder()321 private static void squareRootAndRemainder() { 322 Function<BigInteger, Void> g = (n) -> { 323 BigInteger n2 = n.pow(2); 324 325 // square root of n^2 -> n 326 BigInteger[] actual = n2.sqrtAndRemainder(); 327 checkResult(n, actual[0], "sqrtAndRemainder()[0]"); 328 checkResult(BigInteger.ZERO, actual[1], "sqrtAndRemainder()[1]"); 329 330 // square root of n^2 + 1 -> n 331 BigInteger n2up = n2.add(BigInteger.ONE); 332 actual = n2up.sqrtAndRemainder(); 333 checkResult(n, actual[0], "sqrtAndRemainder()[0]"); 334 checkResult(BigInteger.ONE, actual[1], "sqrtAndRemainder()[1]"); 335 336 // square root of (n + 1)^2 - 1 -> n 337 BigInteger up = n.add(BigInteger.ONE).pow(2).subtract(BigInteger.ONE); 338 actual = up.sqrtAndRemainder(); 339 checkResult(n, actual[0], "sqrtAndRemainder()[0]"); 340 BigInteger r = up.subtract(n2); 341 checkResult(r, actual[1], "sqrtAndRemainder()[1]"); 342 return null; 343 }; 344 345 IntStream bits = random.ints(SIZE, 3, Short.MAX_VALUE); 346 bits.mapToObj(BigInteger::valueOf).map(g).collect(Collectors.toList()); 347 } 348 arithmetic(int order)349 private static void arithmetic(int order) { 350 for (int i=0; i<SIZE; i++) { 351 BigInteger x = fetchNumber(order); 352 while(x.compareTo(BigInteger.ZERO) != 1) 353 x = fetchNumber(order); 354 BigInteger y = fetchNumber(order/2); 355 while(x.compareTo(y) == -1) 356 y = fetchNumber(order/2); 357 if (y.equals(BigInteger.ZERO)) 358 y = y.add(BigInteger.ONE); 359 360 // Test identity ((x/y))*y + x%y - x == 0 361 // using separate divide() and remainder() 362 BigInteger baz = x.divide(y); 363 baz = baz.multiply(y); 364 baz = baz.add(x.remainder(y)); 365 baz = baz.subtract(x); 366 Assert.assertEquals(baz, BigInteger.ZERO); 367 } 368 369 for (int i=0; i<100; i++) { 370 BigInteger x = fetchNumber(order); 371 while(x.compareTo(BigInteger.ZERO) != 1) 372 x = fetchNumber(order); 373 BigInteger y = fetchNumber(order/2); 374 while(x.compareTo(y) == -1) 375 y = fetchNumber(order/2); 376 if (y.equals(BigInteger.ZERO)) 377 y = y.add(BigInteger.ONE); 378 379 // Test identity ((x/y))*y + x%y - x == 0 380 // using divideAndRemainder() 381 BigInteger baz[] = x.divideAndRemainder(y); 382 baz[0] = baz[0].multiply(y); 383 baz[0] = baz[0].add(baz[1]); 384 baz[0] = baz[0].subtract(x); 385 Assert.assertEquals(baz[0], BigInteger.ZERO); 386 } 387 } 388 389 /** 390 * Sanity test for Karatsuba and 3-way Toom-Cook multiplication. 391 * For each of the Karatsuba and 3-way Toom-Cook multiplication thresholds, 392 * construct two factors each with a mag array one element shorter than the 393 * threshold, and with the most significant bit set and the rest of the bits 394 * random. Each of these numbers will therefore be below the threshold but 395 * if shifted left be above the threshold. Call the numbers 'u' and 'v' and 396 * define random shifts 'a' and 'b' in the range [1,32]. Then we have the 397 * identity 398 * <pre> 399 * (u << a)*(v << b) = (u*v) << (a + b) 400 * </pre> 401 * For Karatsuba multiplication, the right hand expression will be evaluated 402 * using the standard naive algorithm, and the left hand expression using 403 * the Karatsuba algorithm. For 3-way Toom-Cook multiplication, the right 404 * hand expression will be evaluated using Karatsuba multiplication, and the 405 * left hand expression using 3-way Toom-Cook multiplication. 406 */ multiplyLarge()407 private static void multiplyLarge() { 408 BigInteger base = BigInteger.ONE.shiftLeft(BITS_KARATSUBA - 32 - 1); 409 for (int i=0; i<SIZE; i++) { 410 BigInteger x = fetchNumber(BITS_KARATSUBA - 32 - 1); 411 BigInteger u = base.add(x); 412 int a = 1 + random.nextInt(31); 413 BigInteger w = u.shiftLeft(a); 414 415 BigInteger y = fetchNumber(BITS_KARATSUBA - 32 - 1); 416 BigInteger v = base.add(y); 417 int b = 1 + random.nextInt(32); 418 BigInteger z = v.shiftLeft(b); 419 420 BigInteger multiplyResult = u.multiply(v).shiftLeft(a + b); 421 BigInteger karatsubaMultiplyResult = w.multiply(z); 422 423 Assert.assertEquals(karatsubaMultiplyResult, multiplyResult); 424 } 425 426 base = base.shiftLeft(BITS_TOOM_COOK - BITS_KARATSUBA); 427 for (int i=0; i<SIZE; i++) { 428 BigInteger x = fetchNumber(BITS_TOOM_COOK - 32 - 1); 429 BigInteger u = base.add(x); 430 BigInteger u2 = u.shiftLeft(1); 431 BigInteger y = fetchNumber(BITS_TOOM_COOK - 32 - 1); 432 BigInteger v = base.add(y); 433 BigInteger v2 = v.shiftLeft(1); 434 435 BigInteger multiplyResult = u.multiply(v).shiftLeft(2); 436 BigInteger toomCookMultiplyResult = u2.multiply(v2); 437 438 Assert.assertEquals(toomCookMultiplyResult, multiplyResult); 439 } 440 } 441 442 /** 443 * Sanity test for Karatsuba and 3-way Toom-Cook squaring. 444 * This test is analogous to {@link AbstractMethodError#multiplyLarge} 445 * with both factors being equal. The squaring methods will not be tested 446 * unless the <code>bigInteger.multiply(bigInteger)</code> tests whether 447 * the parameter is the same instance on which the method is being invoked 448 * and calls <code>square()</code> accordingly. 449 */ squareLarge()450 private static void squareLarge() { 451 BigInteger base = BigInteger.ONE.shiftLeft(BITS_KARATSUBA_SQUARE - 32 - 1); 452 for (int i=0; i<SIZE; i++) { 453 BigInteger x = fetchNumber(BITS_KARATSUBA_SQUARE - 32 - 1); 454 BigInteger u = base.add(x); 455 int a = 1 + random.nextInt(31); 456 BigInteger w = u.shiftLeft(a); 457 458 BigInteger squareResult = u.multiply(u).shiftLeft(2*a); 459 BigInteger karatsubaSquareResult = w.multiply(w); 460 461 Assert.assertEquals(karatsubaSquareResult, squareResult); 462 } 463 464 base = base.shiftLeft(BITS_TOOM_COOK_SQUARE - BITS_KARATSUBA_SQUARE); 465 for (int i=0; i<SIZE; i++) { 466 BigInteger x = fetchNumber(BITS_TOOM_COOK_SQUARE - 32 - 1); 467 BigInteger u = base.add(x); 468 int a = 1 + random.nextInt(31); 469 BigInteger w = u.shiftLeft(a); 470 471 BigInteger squareResult = u.multiply(u).shiftLeft(2*a); 472 BigInteger toomCookSquareResult = w.multiply(w); 473 474 Assert.assertEquals(toomCookSquareResult, squareResult); 475 } 476 } 477 478 /** 479 * Sanity test for Burnikel-Ziegler division. The Burnikel-Ziegler division 480 * algorithm is used when each of the dividend and the divisor has at least 481 * a specified number of ints in its representation. This test is based on 482 * the observation that if {@code w = u*pow(2,a)} and {@code z = v*pow(2,b)} 483 * where {@code abs(u) > abs(v)} and {@code a > b && b > 0}, then if 484 * {@code w/z = q1*z + r1} and {@code u/v = q2*v + r2}, then 485 * {@code q1 = q2*pow(2,a-b)} and {@code r1 = r2*pow(2,b)}. The test 486 * ensures that {@code v} is just under the B-Z threshold, that {@code z} is 487 * over the threshold and {@code w} is much larger than {@code z}. This 488 * implies that {@code u/v} uses the standard division algorithm and 489 * {@code w/z} uses the B-Z algorithm. The results of the two algorithms 490 * are then compared using the observation described in the foregoing and 491 * if they are not equal a failure is logged. 492 */ divideLarge()493 private static void divideLarge() { 494 BigInteger base = BigInteger.ONE.shiftLeft(BITS_BURNIKEL_ZIEGLER + BITS_BURNIKEL_ZIEGLER_OFFSET - 33); 495 for (int i=0; i<SIZE; i++) { 496 BigInteger addend = new BigInteger(BITS_BURNIKEL_ZIEGLER + BITS_BURNIKEL_ZIEGLER_OFFSET - 34, random); 497 BigInteger v = base.add(addend); 498 499 BigInteger u = v.multiply(BigInteger.valueOf(2 + random.nextInt(Short.MAX_VALUE - 1))); 500 501 if(random.nextBoolean()) { 502 u = u.negate(); 503 } 504 if(random.nextBoolean()) { 505 v = v.negate(); 506 } 507 508 int a = BITS_BURNIKEL_ZIEGLER_OFFSET + random.nextInt(16); 509 int b = 1 + random.nextInt(16); 510 BigInteger w = u.multiply(BigInteger.ONE.shiftLeft(a)); 511 BigInteger z = v.multiply(BigInteger.ONE.shiftLeft(b)); 512 513 BigInteger[] divideResult = u.divideAndRemainder(v); 514 divideResult[0] = divideResult[0].multiply(BigInteger.ONE.shiftLeft(a - b)); 515 divideResult[1] = divideResult[1].multiply(BigInteger.ONE.shiftLeft(b)); 516 BigInteger[] bzResult = w.divideAndRemainder(z); 517 518 Assert.assertEquals(divideResult[0].compareTo(bzResult[0]), 0); 519 Assert.assertEquals(divideResult[1].compareTo(bzResult[1]), 0); 520 } 521 } 522 bitCount()523 private static void bitCount() { 524 for (int i=0; i<SIZE*10; i++) { 525 int x = random.nextInt(); 526 BigInteger bigX = BigInteger.valueOf((long)x); 527 int bit = (x < 0 ? 0 : 1); 528 int tmp = x, bitCount = 0; 529 for (int j=0; j<32; j++) { 530 bitCount += ((tmp & 1) == bit ? 1 : 0); 531 tmp >>= 1; 532 } 533 534 Assert.assertEquals (bigX.bitCount(), bitCount); 535 } 536 } 537 bitLength()538 private static void bitLength() { 539 for (int i=0; i<SIZE*10; i++) { 540 int x = random.nextInt(); 541 BigInteger bigX = BigInteger.valueOf((long)x); 542 int signBit = (x < 0 ? 0x80000000 : 0); 543 int tmp = x, bitLength, j; 544 for (j=0; j<32 && (tmp & 0x80000000)==signBit; j++) 545 tmp <<= 1; 546 bitLength = 32 - j; 547 548 Assert.assertEquals(bigX.bitLength(), bitLength); 549 } 550 } 551 bitOps(int order)552 private static void bitOps(int order) { 553 for (int i=0; i<SIZE*5; i++) { 554 BigInteger x = fetchNumber(order); 555 BigInteger y; 556 557 // Test setBit and clearBit (and testBit) 558 if (x.signum() < 0) { 559 y = BigInteger.valueOf(-1); 560 for (int j=0; j<x.bitLength(); j++) 561 if (!x.testBit(j)) 562 y = y.clearBit(j); 563 } else { 564 y = BigInteger.ZERO; 565 for (int j=0; j<x.bitLength(); j++) 566 if (x.testBit(j)) 567 y = y.setBit(j); 568 } 569 Assert.assertEquals(y, x); 570 571 // Test flipBit (and testBit) 572 y = BigInteger.valueOf(x.signum()<0 ? -1 : 0); 573 for (int j=0; j<x.bitLength(); j++) 574 if (x.signum()<0 ^ x.testBit(j)) 575 y = y.flipBit(j); 576 Assert.assertEquals(y, x); 577 } 578 579 for (int i=0; i<SIZE*5; i++) { 580 BigInteger x = fetchNumber(order); 581 582 // Test getLowestSetBit() 583 int k = x.getLowestSetBit(); 584 if (x.signum() == 0) { 585 Assert.assertEquals(k, -1); 586 } else { 587 BigInteger z = x.and(x.negate()); 588 int j; 589 for (j=0; j<z.bitLength() && !z.testBit(j); j++) 590 ; 591 Assert.assertEquals(k, j); 592 } 593 } 594 } 595 bitwise(int order)596 private static void bitwise(int order) { 597 598 // Test identity x^y == x|y &~ x&y 599 for (int i=0; i<SIZE; i++) { 600 BigInteger x = fetchNumber(order); 601 BigInteger y = fetchNumber(order); 602 BigInteger z = x.xor(y); 603 BigInteger w = x.or(y).andNot(x.and(y)); 604 Assert.assertEquals(z, w, "Test identity x^y == x|y &~ x&y"); 605 } 606 607 // Test identity x &~ y == ~(~x | y) 608 for (int i=0; i<SIZE; i++) { 609 BigInteger x = fetchNumber(order); 610 BigInteger y = fetchNumber(order); 611 BigInteger z = x.andNot(y); 612 BigInteger w = x.not().or(y).not(); 613 Assert.assertEquals(z, w, "Test identity x &~ y == ~(~x | y)"); 614 } 615 } 616 shift(int order)617 private static void shift(int order) { 618 for (int i=0; i<100; i++) { 619 BigInteger x = fetchNumber(order); 620 int n = Math.abs(random.nextInt()%200); 621 622 Assert.assertEquals(x.shiftLeft(n), x.multiply(BigInteger.valueOf(2L).pow(n))); 623 624 BigInteger y[] =x.divideAndRemainder(BigInteger.valueOf(2L).pow(n)); 625 BigInteger z = (x.signum()<0 && y[1].signum()!=0 626 ? y[0].subtract(BigInteger.ONE) 627 : y[0]); 628 629 BigInteger b = x.shiftRight(n); 630 631 Assert.assertEquals(z, b); 632 633 Assert.assertEquals(x.shiftLeft(n).shiftRight(n), x); 634 } 635 } 636 divideAndRemainder(int order)637 private static void divideAndRemainder(int order) { 638 for (int i=0; i<SIZE; i++) { 639 BigInteger x = fetchNumber(order).abs(); 640 while(x.compareTo(BigInteger.valueOf(3L)) != 1) 641 x = fetchNumber(order).abs(); 642 BigInteger z = x.divide(BigInteger.valueOf(2L)); 643 BigInteger y[] = x.divideAndRemainder(x); 644 645 Assert.assertEquals(y[0], BigInteger.ONE); 646 Assert.assertEquals(y[1], BigInteger.ZERO); 647 648 y = x.divideAndRemainder(z); 649 Assert.assertEquals(y[0], BigInteger.valueOf(2)); 650 } 651 } 652 653 // BEGIN Android-changed: Fix slow BigInteger string conversion test splitting into multiple. stringConv_generic()654 private static void stringConv_generic() { 655 // Generic string conversion. 656 for (int i=0; i<100; i++) { 657 byte xBytes[] = new byte[Math.abs(random.nextInt())%200+1]; 658 random.nextBytes(xBytes); 659 BigInteger x = new BigInteger(xBytes); 660 661 for (int radix=Character.MIN_RADIX; radix < Character.MAX_RADIX; radix++) { 662 String result = x.toString(radix); 663 BigInteger test = new BigInteger(result, radix); 664 Assert.assertEquals(test, x, 665 "BigInteger toString: "+x+" Test: "+test+" radix: " + radix); 666 } 667 } 668 } 669 stringConv_schoenhage(int k, int samples)670 private static void stringConv_schoenhage(int k, int samples) { 671 // String conversion straddling the Schoenhage algorithm crossover 672 // threshold, and at twice and four times the threshold. 673 int factor = 1 << k; 674 int upper = factor * BITS_SCHOENHAGE_BASE + 33; 675 int lower = upper - 35; 676 677 for (int bits = upper; bits >= lower; bits--) { 678 for (int i = 0; i < samples; i++) { 679 BigInteger x = BigInteger.ONE.shiftLeft(bits - 1).or(new BigInteger(bits - 2, random)); 680 681 for (int radix = Character.MIN_RADIX; radix < Character.MAX_RADIX; radix++) { 682 String result = x.toString(radix); 683 BigInteger test = new BigInteger(result, radix); 684 Assert.assertEquals(test, x, 685 "BigInteger toString: "+x+" Test: "+test+" radix: " + radix); 686 } 687 } 688 } 689 } 690 stringConv_trailingZeros()691 private static void stringConv_trailingZeros() { 692 // Check value with many trailing zeros. 693 String val = "123456789" 694 + "0".repeat(200); 695 BigInteger b = new BigInteger(val); 696 String s = b.toString(); 697 Assert.assertEquals( 698 val, s, String.format("Expected length %d but got %d%n", val.length(), s.length())); 699 } 700 // END Android-changed: Fix slow BigInteger string conversion test splitting into multiple. 701 byteArrayConv(int order)702 private static void byteArrayConv(int order) { 703 for (int i=0; i<SIZE; i++) { 704 BigInteger x = fetchNumber(order); 705 while (x.equals(BigInteger.ZERO)) 706 x = fetchNumber(order); 707 BigInteger y = new BigInteger(x.toByteArray()); 708 Assert.assertEquals(y, x, "orig is " + x + ", new is " + y); 709 } 710 } 711 modInv(int order)712 private static void modInv(int order) { 713 for (int i=0; i<SIZE; i++) { 714 BigInteger x = fetchNumber(order); 715 while(x.equals(BigInteger.ZERO)) 716 x = fetchNumber(order); 717 BigInteger m = fetchNumber(order).abs(); 718 while(m.compareTo(BigInteger.ONE) != 1) 719 m = fetchNumber(order).abs(); 720 721 try { 722 BigInteger inv = x.modInverse(m); 723 BigInteger prod = inv.multiply(x).remainder(m); 724 725 if (prod.signum() == -1) 726 prod = prod.add(m); 727 728 Assert.assertEquals(prod, BigInteger.ONE); 729 } catch(ArithmeticException ignored) { 730 } 731 } 732 } 733 modExp(int order1, int order2)734 private static void modExp(int order1, int order2) { 735 for (int i=0; i<SIZE/10; i++) { 736 BigInteger m = fetchNumber(order1).abs(); 737 while(m.compareTo(BigInteger.ONE) != 1) 738 m = fetchNumber(order1).abs(); 739 BigInteger base = fetchNumber(order2); 740 BigInteger exp = fetchNumber(8).abs(); 741 742 BigInteger z = base.modPow(exp, m); 743 BigInteger w = base.pow(exp.intValue()).mod(m); 744 745 Assert.assertEquals(z, w, "z is "+z+" w is "+w+" mod is "+m+" base is "+base+" exp is "+exp); 746 } 747 } 748 749 // This test is based on Fermat's theorem 750 // which is not ideal because base must not be multiple of modulus 751 // and modulus must be a prime or pseudoprime (Carmichael number) modExp2(int order)752 private static void modExp2(int order) { 753 for (int i=0; i<10; i++) { 754 BigInteger m = new BigInteger(100, 5, random); 755 while(m.compareTo(BigInteger.ONE) != 1) 756 m = new BigInteger(100, 5, random); 757 BigInteger exp = m.subtract(BigInteger.ONE); 758 BigInteger base = fetchNumber(order).abs(); 759 while(base.compareTo(m) != -1) 760 base = fetchNumber(order).abs(); 761 while(base.equals(BigInteger.ZERO)) 762 base = fetchNumber(order).abs(); 763 764 BigInteger one = base.modPow(exp, m); 765 Assert.assertEquals(one, BigInteger.ONE, "m is "+m+" base is "+base+" exp is "+exp); 766 } 767 } 768 769 private static final int[] mersenne_powers = { 770 521, 607, 1279, 2203, 2281, 3217, 4253, 4423, 9689, 9941, 11213, 19937, 771 21701, 23209, 44497, 86243, 110503, 132049, 216091, 756839, 859433, 772 1257787, 1398269, 2976221, 3021377, 6972593, 13466917 }; 773 774 private static final long[] carmichaels = { 775 561,1105,1729,2465,2821,6601,8911,10585,15841,29341,41041,46657,52633, 776 62745,63973,75361,101101,115921,126217,162401,172081,188461,252601, 777 278545,294409,314821,334153,340561,399001,410041,449065,488881,512461, 778 225593397919L }; 779 780 // Note: testing the larger ones takes too long. 781 private static final int NUM_MERSENNES_TO_TEST = 7; 782 // Note: this constant used for computed Carmichaels, not the array above 783 private static final int NUM_CARMICHAELS_TO_TEST = 5; 784 785 private static final String[] customer_primes = { 786 "120000000000000000000000000000000019", 787 "633825300114114700748351603131", 788 "1461501637330902918203684832716283019651637554291", 789 "779626057591079617852292862756047675913380626199", 790 "857591696176672809403750477631580323575362410491", 791 "910409242326391377348778281801166102059139832131", 792 "929857869954035706722619989283358182285540127919", 793 "961301750640481375785983980066592002055764391999", 794 "1267617700951005189537696547196156120148404630231", 795 "1326015641149969955786344600146607663033642528339" }; 796 797 private static final BigInteger ZERO = BigInteger.ZERO; 798 private static final BigInteger ONE = BigInteger.ONE; 799 private static final BigInteger TWO = new BigInteger("2"); 800 private static final BigInteger SIX = new BigInteger("6"); 801 private static final BigInteger TWELVE = new BigInteger("12"); 802 private static final BigInteger EIGHTEEN = new BigInteger("18"); 803 prime()804 private static void prime() { 805 BigInteger p1, p2, c1; 806 807 // Test consistency 808 for(int i=0; i<10; i++) { 809 p1 = BigInteger.probablePrime(100, random); 810 Assert.assertTrue(p1.isProbablePrime(100), p1.toString(16)); 811 } 812 813 // Test some known Mersenne primes (2^n)-1 814 // The array holds the exponents, not the numbers being tested 815 for (int i=0; i<NUM_MERSENNES_TO_TEST; i++) { 816 p1 = new BigInteger("2"); 817 p1 = p1.pow(mersenne_powers[i]); 818 p1 = p1.subtract(BigInteger.ONE); 819 Assert.assertTrue(p1.isProbablePrime(100), "Mersenne prime "+i+ " failed."); 820 } 821 822 // Test some primes reported by customers as failing in the past 823 for (int i=0; i<customer_primes.length; i++) { 824 p1 = new BigInteger(customer_primes[i]); 825 Assert.assertTrue(p1.isProbablePrime(100), "Customer prime "+i+ " failed."); 826 } 827 828 // Test some known Carmichael numbers. 829 for (int i=0; i<carmichaels.length; i++) { 830 c1 = BigInteger.valueOf(carmichaels[i]); 831 Assert.assertFalse(c1.isProbablePrime(100), "Carmichael "+i+ " reported as prime."); 832 } 833 834 // Test some computed Carmichael numbers. 835 // Numbers of the form (6k+1)(12k+1)(18k+1) are Carmichael numbers if 836 // each of the factors is prime 837 int found = 0; 838 BigInteger f1 = new BigInteger(40, 100, random); 839 while (found < NUM_CARMICHAELS_TO_TEST) { 840 BigInteger k = null; 841 BigInteger f2, f3; 842 f1 = f1.nextProbablePrime(); 843 BigInteger[] result = f1.subtract(ONE).divideAndRemainder(SIX); 844 if (result[1].equals(ZERO)) { 845 k = result[0]; 846 f2 = k.multiply(TWELVE).add(ONE); 847 if (f2.isProbablePrime(100)) { 848 f3 = k.multiply(EIGHTEEN).add(ONE); 849 if (f3.isProbablePrime(100)) { 850 c1 = f1.multiply(f2).multiply(f3); 851 Assert.assertFalse(c1.isProbablePrime(100), "Computed Carmichael " 852 +c1.toString(16)); 853 found++; 854 } 855 } 856 } 857 f1 = f1.add(TWO); 858 } 859 860 // Test some composites that are products of 2 primes 861 for (int i=0; i<50; i++) { 862 p1 = BigInteger.probablePrime(100, random); 863 p2 = BigInteger.probablePrime(100, random); 864 c1 = p1.multiply(p2); 865 Assert.assertFalse(c1.isProbablePrime(100), 866 "Composite failed "+c1.toString(16)); 867 } 868 869 for (int i=0; i<4; i++) { 870 p1 = BigInteger.probablePrime(600, random); 871 p2 = BigInteger.probablePrime(600, random); 872 c1 = p1.multiply(p2); 873 Assert.assertFalse(c1.isProbablePrime(100), 874 "Composite failed "+c1.toString(16)); 875 } 876 } 877 878 private static final long[] primesTo100 = { 879 2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97 880 }; 881 882 private static final long[] aPrimeSequence = { 883 1999999003L, 1999999013L, 1999999049L, 1999999061L, 1999999081L, 884 1999999087L, 1999999093L, 1999999097L, 1999999117L, 1999999121L, 885 1999999151L, 1999999171L, 1999999207L, 1999999219L, 1999999271L, 886 1999999321L, 1999999373L, 1999999423L, 1999999439L, 1999999499L, 887 1999999553L, 1999999559L, 1999999571L, 1999999609L, 1999999613L, 888 1999999621L, 1999999643L, 1999999649L, 1999999657L, 1999999747L, 889 1999999763L, 1999999777L, 1999999811L, 1999999817L, 1999999829L, 890 1999999853L, 1999999861L, 1999999871L, 1999999873 891 }; 892 nextProbablePrime()893 private static void nextProbablePrime() throws Exception { 894 BigInteger p1, p2, p3; 895 p1 = p2 = p3 = ZERO; 896 897 // First test nextProbablePrime on the low range starting at zero 898 for (long l : primesTo100) { 899 p1 = p1.nextProbablePrime(); 900 Assert.assertEquals(p1.longValue(), l, 901 "low range primes failed: p1 is " + p1 + ", expected " + l); 902 } 903 904 // Test nextProbablePrime on a relatively small, known prime sequence 905 p1 = BigInteger.valueOf(aPrimeSequence[0]); 906 for (int i=1; i<aPrimeSequence.length; i++) { 907 p1 = p1.nextProbablePrime(); 908 Assert.assertEquals(p1.longValue(), aPrimeSequence[i], "prime sequence failed"); 909 } 910 911 // Next, pick some large primes, use nextProbablePrime to find the 912 // next one, and make sure there are no primes in between 913 for (int i=0; i<100; i+=10) { 914 p1 = BigInteger.probablePrime(50 + i, random); 915 p2 = p1.add(ONE); 916 p3 = p1.nextProbablePrime(); 917 while(p2.compareTo(p3) < 0) { 918 Assert.assertFalse(p2.isProbablePrime(100), 919 "nextProbablePrime failed along range "+p1.toString(16)+" to "+p3.toString(16)); 920 p2 = p2.add(ONE); 921 } 922 } 923 } 924 925 // Android-changed: Replace File streams with ByteArray serialize()926 public static void serialize() throws Exception { 927 String[] bitPatterns = { 928 "ffffffff00000000ffffffff00000000ffffffff00000000", 929 "ffffffffffffffffffffffff000000000000000000000000", 930 "ffffffff0000000000000000000000000000000000000000", 931 "10000000ffffffffffffffffffffffffffffffffffffffff", 932 "100000000000000000000000000000000000000000000000", 933 "aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa", 934 "-ffffffff00000000ffffffff00000000ffffffff00000000", 935 "-ffffffffffffffffffffffff000000000000000000000000", 936 "-ffffffff0000000000000000000000000000000000000000", 937 "-10000000ffffffffffffffffffffffffffffffffffffffff", 938 "-100000000000000000000000000000000000000000000000", 939 "-aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa" 940 }; 941 942 for (String bitPattern : bitPatterns) { 943 BigInteger b1 = new BigInteger(bitPattern, 16); 944 BigInteger b2 = null; 945 946 try (ByteArrayOutputStream fos = new ByteArrayOutputStream()) { 947 try (ObjectOutputStream oos = new ObjectOutputStream(fos)) { 948 oos.writeObject(b1); 949 oos.flush(); 950 } 951 952 try (ByteArrayInputStream fis = new ByteArrayInputStream(fos.toByteArray()); 953 ObjectInputStream ois = new ObjectInputStream(fis)) { 954 b2 = (BigInteger) ois.readObject(); 955 } 956 957 Assert.assertEquals(b1, b2, "Serialized failed for hex " + b1.toString(16)); 958 Assert.assertEquals(b1.or(b2), b1, "Serialized failed for hex " + b1.toString(16)); 959 } 960 } 961 962 for(int i=0; i<10; i++) { 963 BigInteger b1 = fetchNumber(random.nextInt(100)); 964 BigInteger b2 = null; 965 966 try (ByteArrayOutputStream fos = new ByteArrayOutputStream()) { 967 try (ObjectOutputStream oos = new ObjectOutputStream(fos)) { 968 oos.writeObject(b1); 969 oos.flush(); 970 } 971 972 try (ByteArrayInputStream fis = new ByteArrayInputStream(fos.toByteArray()); 973 ObjectInputStream ois = new ObjectInputStream(fis)) 974 { 975 b2 = (BigInteger)ois.readObject(); 976 } 977 } 978 979 Assert.assertEquals(b1, b2, "Serialized failed for hex " + b1.toString(16)); 980 Assert.assertEquals(b1.or(b2), b1, "Serialized failed for hex " + b1.toString(16)); 981 } 982 } 983 984 private static final int ORDER_1 = ORDER_MEDIUM; 985 private static final int ORDER_2 = ORDER_SMALL; 986 private static final int ORDER_3 = ORDER_KARATSUBA; 987 private static final int ORDER_4 = ORDER_TOOM_COOK; 988 989 @Test testConstructor()990 public void testConstructor() { 991 constructor(); 992 } 993 994 @Test testPrime()995 public void testPrime() { 996 prime(); 997 } 998 999 @Test testNextProbablePrime()1000 public void testNextProbablePrime() throws Exception { 1001 nextProbablePrime(); 1002 } 1003 1004 @Test testArithmetic()1005 public void testArithmetic() { 1006 arithmetic(ORDER_1); // small numbers 1007 arithmetic(ORDER_3); // Karatsuba range 1008 arithmetic(ORDER_4); // Toom-Cook / Burnikel-Ziegler range 1009 } 1010 1011 @Test testDivideAndReminder()1012 public void testDivideAndReminder() { 1013 divideAndRemainder(ORDER_1); // small numbers 1014 divideAndRemainder(ORDER_3); // Karatsuba range 1015 divideAndRemainder(ORDER_4); // Toom-Cook / Burnikel-Ziegler range 1016 } 1017 1018 @Test testPow()1019 public void testPow() { 1020 pow(ORDER_1); 1021 pow(ORDER_3); 1022 pow(ORDER_4); 1023 } 1024 1025 @Test testSquare()1026 public void testSquare() { 1027 square(ORDER_MEDIUM); 1028 square(ORDER_KARATSUBA_SQUARE); 1029 square(ORDER_TOOM_COOK_SQUARE); 1030 } 1031 1032 @Test testSquareRoot()1033 public void testSquareRoot() { 1034 squareRoot(); 1035 } 1036 1037 @Test testSquareRootAndReminder()1038 public void testSquareRootAndReminder() { 1039 squareRootAndRemainder(); 1040 } 1041 1042 @Test testBitCount()1043 public void testBitCount() { 1044 bitCount(); 1045 } 1046 1047 @Test testBitLength()1048 public void testBitLength() { 1049 bitLength(); 1050 } 1051 1052 @Test testBitOps()1053 public void testBitOps() { 1054 bitOps(ORDER_1); 1055 } 1056 1057 @Test testBitwise()1058 public void testBitwise() { 1059 bitwise(ORDER_1); 1060 } 1061 1062 @Test testShift()1063 public void testShift() { 1064 shift(ORDER_1); 1065 } 1066 1067 @Test testByteArrayConv()1068 public void testByteArrayConv() { 1069 byteArrayConv(ORDER_1); 1070 } 1071 1072 @Test testModInv()1073 public void testModInv() { 1074 modInv(ORDER_1); // small numbers 1075 modInv(ORDER_3); // Karatsuba range 1076 modInv(ORDER_4); // Toom-Cook / Burnikel-Ziegler range 1077 } 1078 1079 @Test testModExp()1080 public void testModExp() { 1081 modExp(ORDER_1, ORDER_2); 1082 modExp2(ORDER_1); 1083 } 1084 1085 @Test testStringConv_generic()1086 public void testStringConv_generic() { 1087 stringConv_generic(); 1088 } 1089 1090 // String conversion straddling the Schoenhage algorithm crossover 1091 // threshold. 1092 @LargeTest 1093 @Test testStringConv_schoenhage_threshold_pow0()1094 public void testStringConv_schoenhage_threshold_pow0() { 1095 stringConv_schoenhage(0, 50); 1096 } 1097 1098 // String conversion straddling the Schoenhage algorithm crossover 1099 // at twice times the threshold. 1100 @LargeTest 1101 @Test testStringConv_schoenhage_threshold_pow1()1102 public void testStringConv_schoenhage_threshold_pow1() { 1103 stringConv_schoenhage(1, 50); 1104 } 1105 1106 // String conversion straddling the Schoenhage algorithm crossover 1107 // at four times the threshold. 1108 @LargeTest 1109 @Test testStringConv_schoenhage_threshold_pow2()1110 public void testStringConv_schoenhage_threshold_pow2() { 1111 stringConv_schoenhage(2, 15); 1112 } 1113 1114 @Test testStringConv_trailingZeros()1115 public void testStringConv_trailingZeros() { 1116 stringConv_trailingZeros(); 1117 } 1118 1119 @Test testSerialize()1120 public void testSerialize() throws Exception { 1121 serialize(); 1122 } 1123 1124 @Test testMultiplyLarge()1125 public void testMultiplyLarge() { 1126 multiplyLarge(); 1127 } 1128 1129 @Test testSquareLarge()1130 public void testSquareLarge() { 1131 squareLarge(); 1132 } 1133 1134 @Test testDivideLarge()1135 public void testDivideLarge() { 1136 divideLarge(); 1137 } 1138 1139 /* 1140 * Get a random or boundary-case number. This is designed to provide 1141 * a lot of numbers that will find failure points, such as max sized 1142 * numbers, empty BigIntegers, etc. 1143 * 1144 * If order is less than 2, order is changed to 2. 1145 */ fetchNumber(int order)1146 private static BigInteger fetchNumber(int order) { 1147 boolean negative = random.nextBoolean(); 1148 int numType = random.nextInt(7); 1149 BigInteger result = null; 1150 if (order < 2) order = 2; 1151 1152 switch (numType) { 1153 case 0: // Empty 1154 result = BigInteger.ZERO; 1155 break; 1156 1157 case 1: // One 1158 result = BigInteger.ONE; 1159 break; 1160 1161 case 2: // All bits set in number 1162 int numBytes = (order+7)/8; 1163 byte[] fullBits = new byte[numBytes]; 1164 for(int i=0; i<numBytes; i++) 1165 fullBits[i] = (byte)0xff; 1166 int excessBits = 8*numBytes - order; 1167 fullBits[0] &= (1 << (8-excessBits)) - 1; 1168 result = new BigInteger(1, fullBits); 1169 break; 1170 1171 case 3: // One bit in number 1172 result = BigInteger.ONE.shiftLeft(random.nextInt(order)); 1173 break; 1174 1175 case 4: // Random bit density 1176 byte[] val = new byte[(order+7)/8]; 1177 int iterations = random.nextInt(order); 1178 for (int i=0; i<iterations; i++) { 1179 int bitIdx = random.nextInt(order); 1180 val[bitIdx/8] |= 1 << (bitIdx%8); 1181 } 1182 result = new BigInteger(1, val); 1183 break; 1184 case 5: // Runs of consecutive ones and zeros 1185 result = ZERO; 1186 int remaining = order; 1187 int bit = random.nextInt(2); 1188 while (remaining > 0) { 1189 int runLength = Math.min(remaining, random.nextInt(order)); 1190 result = result.shiftLeft(runLength); 1191 if (bit > 0) 1192 result = result.add(ONE.shiftLeft(runLength).subtract(ONE)); 1193 remaining -= runLength; 1194 bit = 1 - bit; 1195 } 1196 break; 1197 1198 default: // random bits 1199 result = new BigInteger(order, random); 1200 } 1201 1202 if (negative) 1203 result = result.negate(); 1204 1205 return result; 1206 } 1207 1208 } 1209