|
1
19
20 package com.maverick.crypto.math;
21
22 import java.util.Random  ;
23 import java.util.Stack ;
24
25 public class BigInteger {
26
27 private int signum; private int mag[]; private int nBits = -1; private int nBitLength = -1; private static final long IMASK = 0xffffffffL;
32 private long mQuote = -1L; int firstNonzeroIntNum = -2;
34 private BigInteger() {
35 }
36
37 private BigInteger(int nWords) {
38 signum = 1;
39 mag = new int[nWords];
40 }
41
42 private BigInteger(
43 int signum,
44 int[] mag) {
45 this.signum = signum;
46 if (mag.length > 0) {
47 int i = 0;
48 while (i < mag.length && mag[i] == 0) {
49 i++;
50 }
51 if (i == 0) {
52 this.mag = mag;
53 }
54 else {
55 int[] newMag = new int[mag.length - i];
57 System.arraycopy(mag, i, newMag, 0, newMag.length);
58 this.mag = newMag;
59 if (newMag.length == 0) {
60 this.signum = 0;
61 }
62 }
63 }
64 else {
65 this.mag = mag;
66 this.signum = 0;
67 }
68 }
69
70 public BigInteger(
71 String sval) throws NumberFormatException {
72 this(sval, 10);
73 }
74
75 public BigInteger(
76 String sval,
77 int rdx) throws NumberFormatException {
78 if (sval.length() == 0) {
79 throw new NumberFormatException ("Zero length BigInteger");
80 }
81
82 if (rdx < Character.MIN_RADIX || rdx > Character.MAX_RADIX) {
83 throw new NumberFormatException ("Radix out of range");
84 }
85
86 int index = 0;
87 signum = 1;
88
89 if (sval.charAt(0) == '-') {
90 if (sval.length() == 1) {
91 throw new NumberFormatException ("Zero length BigInteger");
92 }
93
94 signum = -1;
95 index = 1;
96 }
97
98 while (index < sval.length() &&
100 Character.digit(sval.charAt(index), rdx) == 0) {
101 index++;
102 }
103
104 if (index >= sval.length()) {
105 signum = 0;
107 mag = new int[0];
108 return;
109 }
110
111
117 BigInteger b = BigInteger.ZERO;
118 BigInteger r = valueOf(rdx);
119 while (index < sval.length()) {
120 b = b.multiply(r).add(valueOf(Character.digit(sval.charAt(index), rdx)));
122 index++;
123 }
124
125 mag = b.mag;
126 return;
127 }
128
129 public BigInteger(
130 byte[] bval) throws NumberFormatException {
131 if (bval.length == 0) {
132 throw new NumberFormatException ("Zero length BigInteger");
133 }
134
135 signum = 1;
136 if (bval[0] < 0) {
137 int iBval;
139 signum = -1;
140 for (iBval = 0; iBval < bval.length && bval[iBval] == -1; iBval++) {
142 ;
143 }
144 mag = new int[ (bval.length - iBval) / 2 + 1];
145 }
148 else {
149 mag = makeMagnitude(bval);
151 }
152 }
153
154 private int[] makeMagnitude(byte[] bval) {
155 int i;
156 int[] mag;
157 int firstSignificant;
158
159 for (firstSignificant = 0;
161 firstSignificant < bval.length && bval[firstSignificant] == 0;
162 firstSignificant++) {
163 ;
164 }
165
166 if (firstSignificant >= bval.length) {
167 return new int[0];
168 }
169
170 int nInts = (bval.length - firstSignificant + 3) / 4;
171 int bCount = (bval.length - firstSignificant) % 4;
172 if (bCount == 0) {
173 bCount = 4;
174
175 }
176 mag = new int[nInts];
177 int v = 0;
178 int magnitudeIndex = 0;
179 for (i = firstSignificant; i < bval.length; i++) {
180 v <<= 8;
181 v |= bval[i] & 0xff;
182 bCount--;
183 if (bCount <= 0) {
184 mag[magnitudeIndex] = v;
185 magnitudeIndex++;
186 bCount = 4;
187 v = 0;
188 }
189 }
190
191 if (magnitudeIndex < mag.length) {
192 mag[magnitudeIndex] = v;
193 }
194
195 return mag;
196 }
197
198 public BigInteger(
199 int sign,
200 byte[] mag) throws NumberFormatException {
201 if (sign < -1 || sign > 1) {
202 throw new NumberFormatException ("Invalid sign value");
203 }
204
205 if (sign == 0) {
206 this.signum = 0;
207 this.mag = new int[0];
208 return;
209 }
210
211 this.mag = makeMagnitude(mag);
213 this.signum = sign;
214 }
215
216 public BigInteger(
217 int numBits,
218 Random rnd) throws IllegalArgumentException {
219 if (numBits < 0) {
220 throw new IllegalArgumentException ("numBits must be non-negative");
221 }
222
223 int nBytes = (numBits + 7) / 8;
224
225 byte[] b = new byte[nBytes];
226
227 if (nBytes > 0) {
228 nextRndBytes(rnd, b);
229 b[0] &= rndMask[8 * nBytes - numBits];
231 }
232
233 this.mag = makeMagnitude(b);
234 this.signum = 1;
235 this.nBits = -1;
236 this.nBitLength = -1;
237 }
238
239 private static final int BITS_PER_BYTE = 8;
240 private static final int BYTES_PER_INT = 4;
241
242
248 private void nextRndBytes(
249 Random rnd,
250 byte[] bytes) {
251 int numRequested = bytes.length;
252 int numGot = 0, r = 0;
253
254 if (rnd instanceof com.maverick.crypto.security.SecureRandom) {
255 ( (com.maverick.crypto.security.SecureRandom) rnd).nextBytes(bytes);
256 }
257 else {
258 for (; ; ) {
259 for (int i = 0; i < BYTES_PER_INT; i++) {
260 if (numGot == numRequested) {
261 return;
262 }
263
264 r = (i == 0 ? rnd.nextInt() : r >> BITS_PER_BYTE);
265 bytes[numGot++] = (byte) r;
266 }
267 }
268 }
269 }
270
271 private static final byte[] rndMask = {
272 (byte) 255, 127, 63, 31, 15, 7, 3, 1};
273
274 public BigInteger(
275 int bitLength,
276 int certainty,
277 Random rnd) throws ArithmeticException {
278 int nBytes = (bitLength + 7) / 8;
279
280 byte[] b = new byte[nBytes];
281
282 do {
283 if (nBytes > 0) {
284 nextRndBytes(rnd, b);
285 b[0] &= rndMask[8 * nBytes - bitLength];
287 }
288
289 this.mag = makeMagnitude(b);
290 this.signum = 1;
291 this.nBits = -1;
292 this.nBitLength = -1;
293 if (certainty > 0 && bitLength > 2) {
294 this.mag[this.mag.length - 1] |= 1;
295 }
296 }
297 while (this.bitLength() != bitLength
298 || !this.isProbablePrime(certainty));
299 }
300
301 public BigInteger abs() {
302 return (signum >= 0) ? this : this.negate();
303 }
304
305
308 private int[] add(
309 int[] a,
310 int[] b) {
311 int tI = a.length - 1;
312 int vI = b.length - 1;
313 long m = 0;
314
315 while (vI >= 0) {
316 m += ( ( (long) a[tI]) & IMASK) + ( ( (long) b[vI--]) & IMASK);
317 a[tI--] = (int) m;
318 m >>>= 32;
319 }
320
321 while (tI >= 0 && m != 0) {
322 m += ( ( (long) a[tI]) & IMASK);
323 a[tI--] = (int) m;
324 m >>>= 32;
325 }
326
327 return a;
328 }
329
330 public BigInteger add(
331 BigInteger val) throws ArithmeticException {
332 if (val.signum == 0 || val.mag.length == 0) {
333 return this;
334 }
335 if (this.signum == 0 || this.mag.length == 0) {
336 return val;
337 }
338
339 if (val.signum < 0) {
340 if (this.signum > 0) {
341 return this.subtract(val.negate());
342 }
343 }
344 else {
345 if (this.signum < 0) {
346 return val.subtract(this.negate());
347 }
348 }
349
350
352 int[] mag, op;
353
354 if (this.mag.length < val.mag.length) {
355 mag = new int[val.mag.length + 1];
356
357 System.arraycopy(val.mag, 0, mag, 1, val.mag.length);
358 op = this.mag;
359 }
360 else {
361 mag = new int[this.mag.length + 1];
362
363 System.arraycopy(this.mag, 0, mag, 1, this.mag.length);
364 op = val.mag;
365 }
366
367 return new BigInteger(this.signum, add(mag, op));
368 }
369
370 public int bitCount() {
371 if (nBits == -1) {
372 nBits = 0;
373 for (int i = 0; i < mag.length; i++) {
374 nBits += bitCounts[mag[i] & 0xff];
375 nBits += bitCounts[ (mag[i] >> 8) & 0xff];
376 nBits += bitCounts[ (mag[i] >> 16) & 0xff];
377 nBits += bitCounts[ (mag[i] >> 24) & 0xff];
378 }
379 }
380
381 return nBits;
382 }
383
384 private final static byte bitCounts[] = {
385 0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4,
386 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
387 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
388 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
389 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
390 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
391 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
392 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
393 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 5,
394 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
395 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
396 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
397 2, 3, 3, 4, 3, 4, 4, 5, 3, 4, 4, 5, 4, 5, 5, 6,
398 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
399 3, 4, 4, 5, 4, 5, 5, 6, 4, 5, 5, 6, 5, 6, 6, 7,
400 4, 5, 5, 6, 5, 6, 6, 7, 5, 6, 6, 7, 6, 7, 7, 8};
401
402 private int bitLength(
403 int indx,
404 int[] mag) {
405 int bitLength;
406
407 if (mag.length == 0) {
408 return 0;
409 }
410 else {
411 while (indx != mag.length && mag[indx] == 0) {
412 indx++;
413 }
414
415 if (indx == mag.length) {
416 return 0;
417 }
418
419 bitLength = 32 * ( (mag.length - indx) - 1);
421
422 bitLength += bitLen(mag[indx]);
424
425 if (signum < 0) {
426 boolean pow2 =
428 ( (bitCounts[mag[indx] & 0xff]) +
429 (bitCounts[ (mag[indx] >> 8) & 0xff]) +
430 (bitCounts[ (mag[indx] >> 16) & 0xff]) +
431 (bitCounts[ (mag[indx] >> 24) & 0xff])) == 1;
432
433 for (int i = indx + 1; i < mag.length && pow2; i++) {
434 pow2 = (mag[i] == 0);
435 }
436
437 bitLength -= (pow2 ? 1 : 0);
438 }
439 }
440
441 return bitLength;
442 }
443
444 public int bitLength() {
445 if (nBitLength == -1) {
446 if (signum == 0) {
447 nBitLength = 0;
448 }
449 else {
450 nBitLength = bitLength(0, mag);
451 }
452 }
453
454 return nBitLength;
455 }
456
457 static int bitLen(int w) {
461 return
463 (w < 1 << 15 ?
464 (w < 1 << 7 ?
465 (w < 1 << 3 ?
466 (w < 1 << 1 ? (w < 1 << 0 ? (w < 0 ? 32 : 0) : 1) :
467 (w < 1 << 2 ? 2 : 3)) :
468 (w < 1 << 5 ? (w < 1 << 4 ? 4 : 5) : (w < 1 << 6 ? 6 : 7))) :
469 (w < 1 << 11 ?
470 (w < 1 << 9 ? (w < 1 << 8 ? 8 : 9) : (w < 1 << 10 ? 10 : 11)) :
471 (w < 1 << 13 ? (w < 1 << 12 ? 12 : 13) : (w < 1 << 14 ? 14 : 15)))) :
472 (w < 1 << 23 ?
473 (w < 1 << 19 ?
474 (w < 1 << 17 ? (w < 1 << 16 ? 16 : 17) : (w < 1 << 18 ? 18 : 19)) :
475 (w < 1 << 21 ? (w < 1 << 20 ? 20 : 21) : (w < 1 << 22 ? 22 : 23))) :
476 (w < 1 << 27 ?
477 (w < 1 << 25 ? (w < 1 << 24 ? 24 : 25) : (w < 1 << 26 ? 26 : 27)) :
478 (w < 1 << 29 ? (w < 1 << 28 ? 28 : 29) : (w < 1 << 30 ? 30 : 31)))));
479 }
480
481 private final static byte bitLengths[] = {
482 0, 1, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 4, 4, 4, 4,
483 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,
484 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
485 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,
486 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
487 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
488 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
489 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,
490 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
491 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
492 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
493 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
494 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
495 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
496 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,
497 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8};
498
499 public int compareTo(Object o) {
500 return compareTo( (BigInteger) o);
501 }
502
503
507 private int compareTo(
508 int xIndx,
509 int[] x,
510 int yIndx,
511 int[] y) {
512 while (xIndx != x.length && x[xIndx] == 0) {
513 xIndx++;
514 }
515
516 while (yIndx != y.length && y[yIndx] == 0) {
517 yIndx++;
518 }
519
520 if ( (x.length - xIndx) < (y.length - yIndx)) {
521 return -1;
522 }
523
524 if ( (x.length - xIndx) > (y.length - yIndx)) {
525 return 1;
526 }
527
528
530 while (xIndx < x.length) {
531 long v1 = (long) (x[xIndx++]) & IMASK;
532 long v2 = (long) (y[yIndx++]) & IMASK;
533 if (v1 < v2) {
534 return -1;
535 }
536 if (v1 > v2) {
537 return 1;
538 }
539 }
540
541 return 0;
542 }
543
544 public int compareTo(
545 BigInteger val) {
546 if (signum < val.signum) {
547 return -1;
548 }
549 if (signum > val.signum) {
550 return 1;
551 }
552
553 return compareTo(0, mag, 0, val.mag);
554 }
555
556
560 private int[] divide(
561 int[] x,
562 int[] y) {
563 int xyCmp = compareTo(0, x, 0, y);
564 int[] count;
565
566 if (xyCmp > 0) {
567 int[] c;
568
569 int shift = bitLength(0, x) - bitLength(0, y);
570
571 if (shift > 1) {
572 c = shiftLeft(y, shift - 1);
573 count = shiftLeft(ONE.mag, shift - 1);
574 }
575 else {
576 c = new int[x.length];
577 count = new int[1];
578
579 System.arraycopy(y, 0, c, c.length - y.length, y.length);
580 count[0] = 1;
581 }
582
583 int[] iCount = new int[count.length];
584
585 subtract(0, x, 0, c);
586 System.arraycopy(count, 0, iCount, 0, count.length);
587
588 int xStart = 0;
589 int cStart = 0;
590 int iCountStart = 0;
591
592 for (; ; ) {
593 int cmp = compareTo(xStart, x, cStart, c);
594
595 while (cmp >= 0) {
596 subtract(xStart, x, cStart, c);
597 add(count, iCount);
598 cmp = compareTo(xStart, x, cStart, c);
599 }
600
601 xyCmp = compareTo(xStart, x, 0, y);
602
603 if (xyCmp > 0) {
604 if (x[xStart] == 0) {
605 xStart++;
606 }
607
608 shift = bitLength(cStart, c) - bitLength(xStart, x);
609
610 if (shift == 0) {
611 c = shiftRightOne(cStart, c);
612 iCount = shiftRightOne(iCountStart, iCount);
613 }
614 else {
615 c = shiftRight(cStart, c, shift);
616 iCount = shiftRight(iCountStart, iCount, shift);
617 }
618
619 if (c[cStart] == 0) {
620 cStart++;
621 }
622
623 if (iCount[iCountStart] == 0) {
624 iCountStart++;
625 }
626 }
627 else if (xyCmp == 0) {
628 add(count, ONE.mag);
629 for (int i = xStart; i != x.length; i++) {
630 x[i] = 0;
631 }
632 break;
633 }
634 else {
635 break;
636 }
637 }
638 }
639 else if (xyCmp == 0) {
640 count = new int[1];
641
642 count[0] = 1;
643 }
644 else {
645 count = new int[1];
646
647 count[0] = 0;
648 }
649
650 return count;
651 }
652
653 public BigInteger divide(
654 BigInteger val) throws ArithmeticException {
655 if (val.signum == 0) {
656 throw new ArithmeticException ("Divide by zero");
657 }
658
659 if (signum == 0) {
660 return BigInteger.ZERO;
661 }
662
663 if (val.compareTo(BigInteger.ONE) == 0) {
664 return this;
665 }
666
667 int[] mag = new int[this.mag.length];
668 System.arraycopy(this.mag, 0, mag, 0, mag.length);
669
670 return new BigInteger(this.signum * val.signum, divide(mag, val.mag));
671 }
672
673 public BigInteger[] divideAndRemainder(
674 BigInteger val) throws ArithmeticException {
675 if (val.signum == 0) {
676 throw new ArithmeticException ("Divide by zero");
677 }
678
679 BigInteger biggies[] = new BigInteger[2];
680
681 if (signum == 0) {
682 biggies[0] = biggies[1] = BigInteger.ZERO;
683
684 return biggies;
685 }
686
687 if (val.compareTo(BigInteger.ONE) == 0) {
688 biggies[0] = this;
689 biggies[1] = BigInteger.ZERO;
690
691 return biggies;
692 }
693
694 int[] remainder = new int[this.mag.length];
695 System.arraycopy(this.mag, 0, remainder, 0, remainder.length);
696
697 int[] quotient = divide(remainder, val.mag);
698
699 biggies[0] = new BigInteger(this.signum * val.signum, quotient);
700 biggies[1] = new BigInteger(this.signum, remainder);
701
702 return biggies;
703 }
704
705 public boolean equals(
706 Object val) {
707 if (val == this) {
708 return true;
709 }
710
711 if (! (val instanceof BigInteger)) {
712 return false;
713 }
714 BigInteger biggie = (BigInteger) val;
715
716 if (biggie.signum != signum || biggie.mag.length != mag.length) {
717 return false;
718 }
719
720 for (int i = 0; i < mag.length; i++) {
721 if (biggie.mag[i] != mag[i]) {
722 return false;
723 }
724 }
725
726 return true;
727 }
728
729 public BigInteger gcd(
730 BigInteger val) {
731 if (val.signum == 0) {
732 return this.abs();
733 }
734 else if (signum == 0) {
735 return val.abs();
736 }
737
738 BigInteger r;
739 BigInteger u = this;
740 BigInteger v = val;
741
742 while (v.signum != 0) {
743 r = u.mod(v);
744 u = v;
745 v = r;
746 }
747
748 return u;
749 }
750
751 public int hashCode() {
752 return 0;
753 }
754
755 public int intValue() {
756 if (mag.length == 0) {
757 return 0;
758 }
759
760 if (signum < 0) {
761 return -mag[mag.length - 1];
762 }
763 else {
764 return mag[mag.length - 1];
765 }
766 }
767
768
774 public boolean isProbablePrime(
775 int certainty) {
776 if (certainty == 0) {
777 return true;
778 }
779
780 BigInteger n = this.abs();
781
782 if (n.equals(TWO)) {
783 return true;
784 }
785
786 if (n.equals(ONE) || !n.testBit(0)) {
787 return false;
788 }
789
790 if ( (certainty & 0x1) == 1) {
791 certainty = certainty / 2 + 1;
792 }
793 else {
794 certainty /= 2;
795 }
796
797 BigInteger q = n.subtract(ONE);
801 int k = q.getLowestSetBit();
802
803 q = q.shiftRight(k);
804
805 Random rnd = new Random ();
806 for (int i = 0; i <= certainty; i++) {
807 BigInteger x;
808
809 do {
810 x = new BigInteger(n.bitLength(), rnd);
811 }
812 while (x.compareTo(ONE) <= 0 || x.compareTo(n) >= 0);
813
814 int j = 0;
815 BigInteger y = x.modPow(q, n);
816
817 while (! ( (j == 0 && y.equals(ONE)) || y.equals(n.subtract(ONE)))) {
818 if (j > 0 && y.equals(ONE)) {
819 return false;
820 }
821 if (++j == k) {
822 return false;
823 }
824 y = y.modPow(TWO, n);
825 }
826 }
827
828 return true;
829 }
830
831 public long longValue() {
832 long val = 0;
833
834 if (mag.length == 0) {
835 return 0;
836 }
837
838 if (mag.length > 1) {
839 val = ( (long) mag[mag.length - 2] << 32)
840 | (mag[mag.length - 1] & IMASK);
841 }
842 else {
843 val = (mag[mag.length - 1] & IMASK);
844 }
845
846 if (signum < 0) {
847 return -val;
848 }
849 else {
850 return val;
851 }
852 }
853
854 public BigInteger max(
855 BigInteger val) {
856 return (compareTo(val) > 0) ? this : val;
857 }
858
859 public BigInteger min(
860 BigInteger val) {
861 return (compareTo(val) < 0) ? this : val;
862 }
863
864 public BigInteger mod(
865 BigInteger m) throws ArithmeticException {
866 if (m.signum <= 0) {
867 throw new ArithmeticException ("BigInteger: modulus is not positive");
868 }
869
870 BigInteger biggie = this.remainder(m);
871
872 return (biggie.signum >= 0 ? biggie : biggie.add(m));
873 }
874
875 public BigInteger modInverse(
876 BigInteger m) throws ArithmeticException {
877 if (m.signum != 1) {
878 throw new ArithmeticException ("Modulus must be positive");
879 }
880
881 BigInteger x = new BigInteger();
882 BigInteger y = new BigInteger();
883
884 BigInteger gcd = BigInteger.extEuclid(this, m, x, y);
885
886 if (!gcd.equals(BigInteger.ONE)) {
887 throw new ArithmeticException ("Numbers not relatively prime.");
888 }
889
890 if (x.compareTo(BigInteger.ZERO) < 0) {
891 x = x.add(m);
892 }
893
894 return x;
895 }
896
897
914 private static BigInteger extEuclid(
915 BigInteger a,
916 BigInteger b,
917 BigInteger u1Out,
918 BigInteger u2Out) {
919 BigInteger res;
920
921 BigInteger u1 = BigInteger.ONE;
922 BigInteger u3 = a;
923 BigInteger v1 = BigInteger.ZERO;
924 BigInteger v3 = b;
925
926 while (v3.compareTo(BigInteger.ZERO) > 0) {
927 BigInteger q, tn, tv;
928
929 q = u3.divide(v3);
930
931 tn = u1.subtract(v1.multiply(q));
932 u1 = v1;
933 v1 = tn;
934
935 tn = u3.subtract(v3.multiply(q));
936 u3 = v3;
937 v3 = tn;
938 }
939
940 u1Out.signum = u1.signum;
941 u1Out.mag = u1.mag;
942
943 res = u3.subtract(u1.multiply(a)).divide(b);
944 u2Out.signum = res.signum;
945 u2Out.mag = res.mag;
946
947 return u3;
948 }
949
950
953 private void zero(
954 int[] x) {
955 for (int i = 0; i != x.length; i++) {
956 x[i] = 0;
957 }
958 }
959
960 public BigInteger modPow(
961 BigInteger exponent,
962 BigInteger m) throws ArithmeticException {
963 int[] zVal = null;
964 int[] yAccum = null;
965 int[] yVal;
966
967 boolean useMonty = ( (m.mag[m.mag.length - 1] & 1) == 1);
970 long mQ = 0;
971 if (useMonty) {
972 mQ = m.getMQuote();
973
974 BigInteger tmp = this.shiftLeft(32 * m.mag.length).mod(m);
976 zVal = tmp.mag;
977
978 useMonty = (zVal.length == m.mag.length);
979
980 if (useMonty) {
981 yAccum = new int[m.mag.length + 1];
982 }
983 }
984
985 if (!useMonty) {
986 if (mag.length <= m.mag.length) {
987 zVal = new int[m.mag.length];
989
990 System.arraycopy(mag, 0, zVal,
991 zVal.length - mag.length, mag.length);
992 }
993 else {
994 BigInteger tmp = this.remainder(m);
998
999 zVal = new int[m.mag.length];
1001
1002 System.arraycopy(tmp.mag, 0, zVal,
1003 zVal.length - tmp.mag.length, tmp.mag.length);
1004 }
1005
1006 yAccum = new int[m.mag.length * 2];
1007 }
1008
1009 yVal = new int[m.mag.length];
1010
1011 for (int i = 0; i < exponent.mag.length; i++) {
1015 int v = exponent.mag[i];
1016 int bits = 0;
1017
1018 if (i == 0) {
1019 while (v > 0) {
1020 v <<= 1;
1021 bits++;
1022 }
1023
1024 System.arraycopy(zVal, 0, yVal, 0, zVal.length);
1028
1029 v <<= 1;
1030 bits++;
1031 }
1032
1033 while (v != 0) {
1034 if (useMonty) {
1035 multiplyMonty(yAccum, yVal, yVal, m.mag, mQ);
1039 }
1040 else {
1041 square(yAccum, yVal);
1042 remainder(yAccum, m.mag);
1043 System.arraycopy(yAccum, yAccum.length - yVal.length,
1044 yVal, 0, yVal.length);
1045 zero(yAccum);
1046 }
1047 bits++;
1048
1049 if (v < 0) {
1050 if (useMonty) {
1051 multiplyMonty(yAccum, yVal, zVal, m.mag, mQ);
1052 }
1053 else {
1054 multiply(yAccum, yVal, zVal);
1055 remainder(yAccum, m.mag);
1056 System.arraycopy(yAccum, yAccum.length - yVal.length,
1057 yVal, 0, yVal.length);
1058 zero(yAccum);
1059 }
1060 }
1061
1062 v <<= 1;
1063 }
1064
1065 while (bits < 32) {
1066 if (useMonty) {
1067 multiplyMonty(yAccum, yVal, yVal, m.mag, mQ);
1068 }
1069 else {
1070 square(yAccum, yVal);
1071 remainder(yAccum, m.mag);
1072 System.arraycopy(yAccum, yAccum.length - yVal.length,
1073 yVal, 0, yVal.length);
1074 zero(yAccum);
1075 }
1076 bits++;
1077 }
1078 }
1079
1080 if (useMonty) {
1081 zero(zVal);
1083 zVal[zVal.length - 1] = 1;
1084 multiplyMonty(yAccum, yVal, zVal, m.mag, mQ);
1085 }
1086
1087 return new BigInteger(1, yVal);
1088 }
1089
1090
1093 private int[] square(
1094 int[] w,
1095 int[] x) {
1096 long u1, u2, c;
1097
1098 if (w.length != 2 * x.length) {
1099 throw new IllegalArgumentException ("no I don't think so...");
1100 }
1101
1102 for (int i = x.length - 1; i != 0; i--) {
1103 long v = (x[i] & IMASK);
1104
1105 u1 = v * v;
1106 u2 = u1 >>> 32;
1107 u1 = u1 & IMASK;
1108
1109 u1 += (w[2 * i + 1] & IMASK);
1110
1111 w[2 * i + 1] = (int) u1;
1112 c = u2 + (u1 >> 32);
1113
1114 for (int j = i - 1; j >= 0; j--) {
1115 u1 = (x[j] & IMASK) * v;
1116 u2 = u1 >>> 31; u1 = (u1 & 0x7fffffff) << 1; u1 += (w[i + j + 1] & IMASK) + c;
1119
1120 w[i + j + 1] = (int) u1;
1121 c = u2 + (u1 >>> 32);
1122 }
1123 c += w[i] & IMASK;
1124 w[i] = (int) c;
1125 w[i - 1] = (int) (c >> 32);
1126 }
1127
1128 u1 = (x[0] & IMASK);
1129 u1 = u1 * u1;
1130 u2 = u1 >>> 32;
1131 u1 = u1 & IMASK;
1132
1133 u1 += (w[1] & IMASK);
1134
1135 w[1] = (int) u1;
1136 w[0] = (int) (u2 + (u1 >> 32) + w[0]);
1137
1138 return w;
1139 }
1140
1141
1144 private int[] multiply(
1145 int[] x,
1146 int[] y,
1147 int[] z) {
1148 for (int i = z.length - 1; i >= 0; i--) {
1149 long a = z[i] & IMASK;
1150 long value = 0;
1151
1152 for (int j = y.length - 1; j >= 0; j--) {
1153 value += a * (y[j] & IMASK) + (x[i + j + 1] & IMASK);
1154
1155 x[i + j + 1] = (int) value;
1156
1157 value >>>= 32;
1158 }
1159
1160 x[i] = (int) value;
1161 }
1162
1163 return x;
1164 }
1165
1166
1169 private long getMQuote() {
1170 if (mQuote != -1L) { return mQuote;
1172 }
1173 if ( (mag[mag.length - 1] & 1) == 0) {
1174 return -1L; }
1176
1177 byte[] bytes = {
1178 1, 0, 0, 0, 0};
1179 BigInteger b = new BigInteger(1, bytes); mQuote = this.negate().mod(b).modInverse(b).longValue();
1181 return mQuote;
1182 }
1183
1184
1197 public void multiplyMonty(
1198 int[] a,
1199 int[] x,
1200 int[] y,
1201 int[] m,
1202 long mQuote) { int n = m.length;
1204 int nMinus1 = n - 1;
1205 long y_0 = y[n - 1] & IMASK;
1206
1207 for (int i = 0; i <= n; i++) {
1209 a[i] = 0;
1210 }
1211
1212 for (int i = n; i > 0; i--) {
1214
1215 long x_i = x[i - 1] & IMASK;
1216
1217 long u = ( ( ( (a[n] & IMASK) + ( (x_i * y_0) & IMASK)) & IMASK) *
1219 mQuote) & IMASK;
1220
1221 long prod1 = x_i * y_0;
1223 long prod2 = u * (m[n - 1] & IMASK);
1224 long tmp = (a[n] & IMASK) + (prod1 & IMASK) + (prod2 & IMASK);
1225 long carry = (prod1 >>> 32) + (prod2 >>> 32) + (tmp >>> 32);
1226 for (int j = nMinus1; j > 0; j--) {
1227 prod1 = x_i * (y[j - 1] & IMASK);
1228 prod2 = u * (m[j - 1] & IMASK);
1229 tmp = (a[j] & IMASK) + (prod1 & IMASK) +
1230 (prod2 & IMASK) + (carry & IMASK);
1231 carry = (carry >>> 32) + (prod1 >>> 32) +
1232 (prod2 >>> 32) + (tmp >>> 32);
1233 a[j + 1] = (int) tmp; }
1235 carry += (a[0] & IMASK);
1236 a[1] = (int) carry;
1237 a[0] = (int) (carry >>> 32);
1238 }
1239
1240 if (compareTo(0, a, 0, m) >= 0) {
1242 subtract(0, a, 0, m);
1243 }
1244
1245 for (int i = 0; i < n; i++) {
1247 x[i] = a[i + 1];
1248 }
1249 }
1250
1251 public BigInteger multiply(
1252 BigInteger val) {
1253 if (signum == 0 || val.signum == 0) {
1254 return BigInteger.ZERO;
1255 }
1256
1257 int[] res = new int[mag.length + val.mag.length];
1258
1259 return new BigInteger(signum * val.signum, multiply(res, mag, val.mag));
1260 }
1261
1262 public BigInteger negate() {
1263 return new BigInteger( -signum, mag);
1264 }
1265
1266 public BigInteger pow(
1267 int exp) throws ArithmeticException {
1268 if (exp < 0) {
1269 throw new ArithmeticException ("Negative exponent");
1270 }
1271 if (signum == 0) {
1272 return (exp == 0 ? BigInteger.ONE : this);
1273 }
1274
1275 BigInteger y, z;
1276 y = BigInteger.ONE;
1277 z = this;
1278
1279 while (exp != 0) {
1280 if ( (exp & 0x1) == 1) {
1281 y = y.multiply(z);
1282 }
1283 exp >>= 1;
1284 if (exp != 0) {
1285 z = z.multiply(z);
1286 }
1287 }
1288
1289 return y;
1290 }
1291
1292
1295 private int[] remainder(
1296 int[] x,
1297 int[] y) {
1298 int xyCmp = compareTo(0, x, 0, y);
1299
1300 if (xyCmp > 0) {
1301 int[] c;
1302 int shift = bitLength(0, x) - bitLength(0, y);
1303
1304 if (shift > 1) {
1305 c = shiftLeft(y, shift - 1);
1306 }
1307 else {
1308 c = new int[x.length];
1309
1310 System.arraycopy(y, 0, c, c.length - y.length, y.length);
1311 }
1312
1313 subtract(0, x, 0, c);
1314
1315 int xStart = 0;
1316 int cStart = 0;
1317
1318 for (; ; ) {
1319 int cmp = compareTo(xStart, x, cStart, c);
1320
1321 while (cmp >= 0) {
1322 subtract(xStart, x, cStart, c);
1323 cmp = compareTo(xStart, x, cStart, c);
1324 }
1325
1326 xyCmp = compareTo(xStart, x, 0, y);
1327
1328 if (xyCmp > 0) {
1329 if (x[xStart] == 0) {
1330 xStart++;
1331 }
1332
1333 shift = bitLength(cStart, c) - bitLength(xStart, x);
1334
1335 if (shift == 0) {
1336 c = shiftRightOne(cStart, c);
1337 }
1338 else {
1339 c = shiftRight(cStart, c, shift);
1340 }
1341
1342 if (c[cStart] == 0) {
1343 cStart++;
1344 }
1345 }
1346 else if (xyCmp == 0) {
1347 for (int i = xStart; i != x.length; i++) {
1348 x[i] = 0;
1349 }
1350 break;
1351 }
1352 else {
1353 break;
1354 }
1355 }
1356 }
1357 else if (xyCmp == 0) {
1358 for (int i = 0; i != x.length; i++) {
1359 x[i] = 0;
1360 }
1361 }
1362
1363 return x;
1364 }
1365
1366
1374 public BigInteger or(BigInteger val) {
1375 int[] result = new int[Math.max(intLength(), val.intLength())];
1376 for (int i = 0; i < result.length; i++) {
1377 result[i] = (int) (getInt(result.length - i - 1)
1378 | val.getInt(result.length - i - 1));
1379
1380 }
1381 return valueOf(result);
1382 }
1383
1384 private static int[] makePositive(int a[]) {
1385 int keep, j;
1386
1387 for (keep = 0; keep < a.length && a[keep] == -1; keep++) {
1389 ;
1390 }
1391
1392
1394 for (j = keep; j < a.length && a[j] == 0; j++) {
1395 ;
1396 }
1397 int extraInt = (j == a.length ? 1 : 0);
1398 int result[] = new int[a.length - keep + extraInt];
1399
1400
1402 for (int i = keep; i < a.length; i++) {
1403 result[i - keep + extraInt] = ~a[i];
1404
1405 }
1407 for (int i = result.length - 1; ++result[i] == 0; i--) {
1408 ;
1409 }
1410
1411 return result;
1412 }
1413
1414 private static int[] makePositive(byte a[]) {
1415 int keep, k;
1416 int byteLength = a.length;
1417
1418 for (keep = 0; keep < byteLength && a[keep] == -1; keep++) {
1420 ;
1421 }
1422
1423
1425 for (k = keep; k < byteLength && a[k] == 0; k++) {
1426 ;
1427 }
1428
1429 int extraByte = (k == byteLength) ? 1 : 0;
1430 int intLength = ( (byteLength - keep + extraByte) + 3) / 4;
1431 int result[] = new int[intLength];
1432
1433
1435 int b = byteLength - 1;
1436 for (int i = intLength - 1; i >= 0; i--) {
1437 result[i] = a[b--] & 0xff;
1438 int numBytesToTransfer = Math.min(3, b - keep + 1);
1439 if (numBytesToTransfer < 0) {
1440 numBytesToTransfer = 0;
1441 }
1442 for (int j = 8; j <= 8 * numBytesToTransfer; j += 8) {
1443 result[i] |= ( (a[b--] & 0xff) << j);
1444
1445 }
1447 int mask = -1 >>> (8 * (3 - numBytesToTransfer));
1448 result[i] = ~result[i] & mask;
1449 }
1450
1451 for (int i = result.length - 1; i >= 0; i--) {
1453 result[i] = (int) ( (result[i] & 0xffffffffL) + 1);
1454 if (result[i] != 0) {
1455 break;
1456 }
1457 }
1458
1459 return result;
1460 }
1461
1462 private BigInteger(int[] val) {
1463 if (val.length == 0) {
1464 throw new NumberFormatException ("Zero length BigInteger");
1465 }
1466
1467 if (val[0] < 0) {
1468 mag = makePositive(val);
1469 signum = -1;
1470 }
1471 else {
1472 mag = trustedStripLeadingZeroInts(val);
1473 signum = (mag.length == 0 ? 0 : 1);
1474 }
1475 }
1476
1477 private static int[] trustedStripLeadingZeroInts(int val[]) {
1478 int byteLength = val.length;
1479 int keep;
1480
1481 for (keep = 0; keep < val.length && val[keep] == 0; keep++) {
1483 ;
1484 }
1485
1486 if (keep > 0) {
1488 int result[] = new int[val.length - keep];
1489 for (int i = 0; i < val.length - keep; i++) {
1490 result[i] = val[keep + i];
1491 }
1492 return result;
1493 }
1494 return val;
1495 }
1496
1497 private int signInt() {
1498 return (int) (signum < 0 ? -1 : 0);
1499 }
1500
1501 private static BigInteger valueOf(int val[]) {
1502 return (val[0] > 0 ? new BigInteger(val, 1) : new BigInteger(val));
1503 }
1504
1505 private BigInteger(int[] magnitude, int signum) {
1506 this.signum = (magnitude.length == 0 ? 0 : signum);
1507 this.mag = magnitude;
1508 }
1509
1510 private int firstNonzeroIntNum() {
1511
1516 if (firstNonzeroIntNum == -2) {
1517 int i;
1519 for (i = mag.length - 1; i >= 0 && mag[i] == 0; i--) {
1520 ;
1521 }
1522 firstNonzeroIntNum = mag.length - i - 1;
1523 }
1524 return firstNonzeroIntNum;
1525 }
1526
1527 private int intLength() {
1528 return bitLength() / 32 + 1;
1529 }
1530
1531 private int getInt(int n) {
1532 if (n < 0) {
1533 return 0;
1534 }
1535 if (n >= mag.length) {
1536 return signInt();
1537 }
1538
1539 int magInt = mag[mag.length - n - 1];
1540
1541 return (int) (signum >= 0 ? magInt :
1542 (n <= firstNonzeroIntNum() ? -magInt : ~magInt));
1543 }
1544
1545 public BigInteger remainder(
1546 BigInteger val) throws ArithmeticException {
1547 if (val.signum == 0) {
1548 throw new ArithmeticException ("BigInteger: Divide by zero");
1549 }
1550
1551 if (signum == 0) {
1552 return BigInteger.ZERO;
1553 }
1554
1555 int[] res = new int[this.mag.length];
1556
1557 System.arraycopy(this.mag, 0, res, 0, res.length);
1558
1559 return new BigInteger(signum, remainder(res, val.mag));
1560 }
1561
1562
1565 private int[] shiftLeft(
1566 int[] mag,
1567 int n) {
1568 int nInts = n >>> 5;
1569 int nBits = n & 0x1f;
1570 int magLen = mag.length;
1571 int newMag[] = null;
1572
1573 if (nBits == 0) {
1574 newMag = new int[magLen + nInts];
1575 for (int i = 0; i < magLen; i++) {
1576 newMag[i] = mag[i];
1577 }
1578 }
1579 else {
1580 int i = 0;
1581 int nBits2 = 32 - nBits;
1582 int highBits = mag[0] >>> nBits2;
1583
1584 if (highBits != 0) {
1585 newMag = new int[magLen + nInts + 1];
1586 newMag[i++] = highBits;
1587 }
1588 else {
1589 newMag = new int[magLen + nInts];
1590 }
1591
1592 int m = mag[0];
1593 for (int j = 0; j < magLen - 1; j++) {
1594 int next = mag[j + 1];
1595
1596 newMag[i++] = (m << nBits) | (next >>> nBits2);
1597 m = next;
1598 }
1599
1600 newMag[i] = mag[magLen - 1] << nBits;
1601 }
1602
1603 return newMag;
1604 }
1605
1606 public BigInteger shiftLeft(
1607 int n) {
1608 if (signum == 0 || mag.length == 0) {
1609 return ZERO;
1610 }
1611 if (n == 0) {
1612 return this;
1613 }
1614
1615 if (n < 0) {
1616 return shiftRight( -n);
1617 }
1618
1619 return new BigInteger(signum, shiftLeft(mag, n));
1620 }
1621
1622
1625 private int[] shiftRight(
1626 int start,
1627 int[] mag,
1628 int n) {
1629 int nInts = (n >>> 5) + start;
1630 int nBits = n & 0x1f;
1631 int magLen = mag.length;
1632
1633 if (nInts != start) {
1634 int delta = (nInts - start);
1635
1636 for (int i = magLen - 1; i >= nInts; i--) {
1637 mag[i] = mag[i - delta];
1638 }
1639 for (int i = nInts - 1; i >= start; i--) {
1640 mag[i] = 0;
1641 }
1642 }
1643
1644 if (nBits != 0) {
1645 int nBits2 = 32 - nBits;
1646 int m = mag[magLen - 1];
1647
1648 for (int i = magLen - 1; i >= nInts + 1; i--) {
1649 int next = mag[i - 1];
1650
1651 mag[i] = (m >>> nBits) | (next << nBits2);
1652 m = next;
1653 }
1654
1655 mag[nInts] >>>= nBits;
1656 }
1657
1658 return mag;
1659 }
1660
1661
1664 private int[] shiftRightOne(
1665 int start,
1666 int[] mag) {
1667 int magLen = mag.length;
1668
1669 int m = mag[magLen - 1];
1670
1671 for (int i = magLen - 1; i >= start + 1; i--) {
1672 int next = mag[i - 1];
1673
1674 mag[i] = (m >>> 1) | (next << 31);
1675 m = next;
1676 }
1677
1678 mag[start] >>>= 1;
1679
1680 return mag;
1681 }
1682
1683 public BigInteger shiftRight(
1684 int n) {
1685 if (n == 0) {
1686 return this;
1687 }
1688
1689 if (n < 0) {
1690 return shiftLeft( -n);
1691 }
1692
1693 if (n >= bitLength()) {
1694 return (this.signum < 0 ? valueOf( -1) : BigInteger.ZERO);
1695 }
1696
1697 int[] res = new int[this.mag.length];
1698
1699 System.arraycopy(this.mag, 0, res, 0, res.length);
1700
1701 return new BigInteger(this.signum, shiftRight(0, res, n));
1702 }
1703
1704 public int signum() {
1705 return signum;
1706 }
1707
1708
1711 private int[] subtract(
1712 int xStart,
1713 int[] x,
1714 int yStart,
1715 int[] y) {
1716 int iT = x.length - 1;
1717 int iV = y.length - 1;
1718 long m;
1719 int borrow = 0;
1720
1721 do {
1722 m = ( ( (long) x[iT]) & IMASK) - ( ( (long) y[iV--]) & IMASK) + borrow;
1723
1724 x[iT--] = (int) m;
1725
1726 if (m < 0) {
1727 borrow = -1;
1728 }
1729 else {
1730 borrow = 0;
1731 }
1732 }
1733 while (iV >= yStart);
1734
1735 while (iT >= xStart) {
1736 m = ( ( (long) x[iT]) & IMASK) + borrow;
1737 x[iT--] = (int) m;
1738
1739 if (m < 0) {
1740 borrow = -1;
1741 }
1742 else {
1743 break;
1744 }
1745 }
1746
1747 return x;
1748 }
1749
1750 public BigInteger subtract(
1751 BigInteger val) {
1752 if (val.signum == 0 || val.mag.length == 0) {
1753 return this;
1754 }
1755 if (signum == 0 || mag.length == 0) {
1756 return val.negate();
1757 }
1758 if (val.signum < 0) {
1759 if (this.signum > 0) {
1760 return this.add(val.negate());
1761 }
1762 }
1763 else {
1764 if (this.signum < 0) {
1765 return this.add(val.negate());
1766 }
1767 }
1768
1769 BigInteger bigun, littlun;
1770 int compare = compareTo(val);
1771 if (compare == 0) {
1772 return ZERO;
1773 }
1774
1775 if (compare < 0) {
1776 bigun = val;
1777 littlun = this;
1778 }
1779 else {
1780 bigun = this;
1781 littlun = val;
1782 }
1783
1784 int res[] = new int[bigun.mag.length];
1785
1786 System.arraycopy(bigun.mag, 0, res, 0, res.length);
1787
1788 return new BigInteger(this.signum * compare,
1789 subtract(0, res, 0, littlun.mag));
1790 }
1791
1792 public byte[] toByteArray() {
1793 int bitLength = bitLength();
1794 byte[] bytes = new byte[bitLength / 8 + 1];
1795
1796 int bytesCopied = 4;
1797 int mag = 0;
1798 int ofs = this.mag.length - 1;
1799 int carry = 1;
1800 long lMag;
1801 for (int i = bytes.length - 1; i >= 0; i--) {
1802 if (bytesCopied == 4 && ofs >= 0) {
1803 if (signum < 0) {
1804 lMag = ~this.mag[ofs--] & IMASK;
1808 lMag += carry;
1809 if ( (lMag & ~IMASK) != 0) {
1810 carry = 1;
1811 }
1812 else {
1813 carry = 0;
1814 }
1815 mag = (int) (lMag & IMASK);
1816 }
1817 else {
1818 mag = this.mag[ofs--];
1819 }
1820 bytesCopied = 1;
1821 }
1822 else {
1823 mag >>>= 8;
1824 bytesCopied++;
1825 }
1826
1827 bytes[i] = (byte) mag;
1828 }
1829
1830 return bytes;
1831 }
1832
1833 public String toString() {
1834 return toString(10);
1835 }
1836
1837 public String toString(int rdx) {
1838 if (mag == null) {
1839 return "null";
1840 }
1841 else if (signum == 0) {
1842 return "0";
1843 }
1844
1845 String s = new String ();
1846 String h;
1847
1848 if (rdx == 16) {
1849 for (int i = 0; i < mag.length; i++) {
1850 h = "0000000" + Integer.toHexString(mag[i]);
1851 h = h.substring(h.length() - 8);
1852 s = s + h;
1853 }
1854 }
1855 else {
1856 Stack S = new Stack ();
1858 BigInteger base = new BigInteger(Integer.toString(rdx, rdx), rdx);
1859 BigInteger u = new BigInteger(this.abs().toString(16), 16);
1865 BigInteger b;
1866
1867 while (!u.equals(BigInteger.ZERO)) {
1869 b = u.mod(base);
1870 if (b.equals(BigInteger.ZERO)) {
1871 S.push("0");
1872 }
1873 else {
1874 S.push(Integer.toString(b.mag[0], rdx));
1875 }
1876 u = u.divide(base);
1877 }
1878 while (!S.empty()) {
1880 s = s + S.pop();
1881 }
1882 }
1883 while (s.length() > 1 && s.charAt(0) == '0') {
1885 s = s.substring(1);
1886
1887 }
1888 if (s.length() == 0) {
1889 s = "0";
1890 }
1891 else if (signum == -1) {
1892 s = "-" + s;
1893
1894 }
1895 return s;
1896 }
1897
1898 public static final BigInteger ZERO = new BigInteger(0, new byte[0]);
1899 public static final BigInteger ONE = valueOf(1);
1900 private static final BigInteger TWO = valueOf(2);
1901
1902 public static BigInteger valueOf(
1903 long val) {
1904 if (val == 0) {
1905 return BigInteger.ZERO;
1906 }
1907
1908 byte[] b = new byte[8];
1910 for (int i = 0; i < 8; i++) {
1911 b[7 - i] = (byte) val;
1912 val >>= 8;
1913 }
1914
1915 return new BigInteger(b);
1916 }
1917
1918 private int max(int a, int b) {
1919 if (a < b) {
1920 return b;
1921 }
1922 return a;
1923 }
1924
1925 public int getLowestSetBit() {
1926 if (this.equals(ZERO)) {
1927 return -1;
1928 }
1929
1930 int w = mag.length - 1;
1931
1932 while (w >= 0) {
1933 if (mag[w] != 0) {
1934 break;
1935 }
1936
1937 w--;
1938 }
1939
1940 int b = 31;
1941
1942 while (b > 0) {
1943 if ( (mag[w] << b) == 0x80000000) {
1944 break;
1945 }
1946
1947 b--;
1948 }
1949
1950 return ( ( (mag.length - 1) - w) * 32 + (31 - b));
1951 }
1952
1953 public boolean testBit(
1954 int n) throws ArithmeticException {
1955 if (n < 0) {
1956 throw new ArithmeticException ("Bit position must not be negative");
1957 }
1958
1959 if ( (n / 32) >= mag.length) {
1960 return signum < 0;
1961 }
1962
1963 return ( (mag[ (mag.length - 1) - n / 32] >> (n % 32)) & 1) > 0;
1964 }
1965}
1966 |
Popular Tags |
Java API By Example, From Geeks To Geeks.