001: /*
002: * Licensed to the Apache Software Foundation (ASF) under one or more
003: * contributor license agreements. See the NOTICE file distributed with
004: * this work for additional information regarding copyright ownership.
005: * The ASF licenses this file to You under the Apache License, Version 2.0
006: * (the "License"); you may not use this file except in compliance with
007: * the License. You may obtain a copy of the License at
008: *
009: * http://www.apache.org/licenses/LICENSE-2.0
010: *
011: * Unless required by applicable law or agreed to in writing, software
012: * distributed under the License is distributed on an "AS IS" BASIS,
013: * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
014: * See the License for the specific language governing permissions and
015: * limitations under the License.
016: */
017:
018: package java.math;
019:
020: import java.io.IOException;
021: import java.io.ObjectInputStream;
022: import java.io.ObjectOutputStream;
023: import java.util.Random;
024: import java.io.Serializable;
025:
026: import org.apache.harmony.math.internal.nls.Messages;
027:
028: public class BigInteger extends Number implements
029: Comparable<BigInteger>, Serializable {
030:
031: private static final long serialVersionUID = -8287574255936472291L;
032:
033: /* Fields used for the internal representation. */
034:
035: /** The magnitude of this in the little-endian representation. */
036: transient int digits[];
037:
038: /** The length of this in measured in ints. Can be less than digits.length(). */
039: transient int numberLength;
040:
041: /** The sign of this. */
042: transient int sign;
043:
044: public static final BigInteger ONE = new BigInteger(1, 1);
045:
046: public static final BigInteger TEN = new BigInteger(1, 10);
047:
048: public static final BigInteger ZERO = new BigInteger(0, 0);
049:
050: /** The {@code BigInteger} constant -1. */
051: static final BigInteger MINUS_ONE = new BigInteger(-1, 1);
052:
053: /** The {@code BigInteger} constant 0 used for comparison. */
054: static final int EQUALS = 0;
055:
056: /** The {@code BigInteger} constant 1 used for comparison. */
057: static final int GREATER = 1;
058:
059: /** The {@code BigInteger} constant -1 used for comparison. */
060: static final int LESS = -1;
061:
062: /** All the {@ BigInteger} numbers in the range [0,10] are cached. */
063: static final BigInteger[] SMALL_VALUES = { ZERO, ONE,
064: new BigInteger(1, 2), new BigInteger(1, 3),
065: new BigInteger(1, 4), new BigInteger(1, 5),
066: new BigInteger(1, 6), new BigInteger(1, 7),
067: new BigInteger(1, 8), new BigInteger(1, 9), TEN };
068:
069: private transient int firstNonzeroDigit = -2;
070:
071: /* Serialized Fields */
072:
073: private int signum;
074:
075: private byte[] magnitude;
076:
077: private transient int hashCode = 0;
078:
079: /* Public Constructors */
080:
081: public BigInteger(int numBits, Random rnd) {
082: if (numBits < 0) {
083: // math.1B=numBits must be non-negative
084: throw new IllegalArgumentException(Messages
085: .getString("math.1B")); //$NON-NLS-1$
086: }
087: if (numBits == 0) {
088: sign = 0;
089: numberLength = 1;
090: digits = new int[] { 0 };
091: } else {
092: sign = 1;
093: numberLength = (numBits + 31) >> 5;
094: digits = new int[numberLength];
095: for (int i = 0; i < numberLength; i++) {
096: digits[i] = rnd.nextInt();
097: }
098: // Using only the necessary bits
099: digits[numberLength - 1] >>>= (-numBits) & 31;
100: cutOffLeadingZeroes();
101: }
102: }
103:
104: public BigInteger(int bitLength, int certainty, Random rnd) {
105: if (bitLength < 2) {
106: // math.1C=bitLength < 2
107: throw new ArithmeticException(Messages.getString("math.1C")); //$NON-NLS-1$
108: }
109: BigInteger me = Primality.consBigInteger(bitLength, certainty,
110: rnd);
111: sign = me.sign;
112: numberLength = me.numberLength;
113: digits = me.digits;
114: }
115:
116: public BigInteger(String val) {
117: this (val, 10);
118: }
119:
120: public BigInteger(String val, int radix) {
121: if (val == null) {
122: throw new NullPointerException();
123: }
124: if ((radix < Character.MIN_RADIX)
125: || (radix > Character.MAX_RADIX)) {
126: // math.11=Radix out of range
127: throw new NumberFormatException(Messages
128: .getString("math.11")); //$NON-NLS-1$
129: }
130: if (val.length() == 0) {
131: // math.12=Zero length BigInteger
132: throw new NumberFormatException(Messages
133: .getString("math.12")); //$NON-NLS-1$
134: }
135: setFromString(this , val, radix);
136: }
137:
138: public BigInteger(int signum, byte[] magnitude) {
139: if (magnitude == null) {
140: throw new NullPointerException();
141: }
142: if ((signum < -1) || (signum > 1)) {
143: // math.13=Invalid signum value
144: throw new NumberFormatException(Messages
145: .getString("math.13")); //$NON-NLS-1$
146: }
147: if (signum == 0) {
148: for (byte element : magnitude) {
149: if (element != 0) {
150: // math.14=signum-magnitude mismatch
151: throw new NumberFormatException(Messages
152: .getString("math.14")); //$NON-NLS-1$
153: }
154: }
155: }
156: if (magnitude.length == 0) {
157: sign = 0;
158: numberLength = 1;
159: digits = new int[] { 0 };
160: } else {
161: sign = signum;
162: putBytesPositiveToIntegers(magnitude);
163: cutOffLeadingZeroes();
164: }
165: }
166:
167: public BigInteger(byte[] val) {
168: if (val.length == 0) {
169: // math.12=Zero length BigInteger
170: throw new NumberFormatException(Messages
171: .getString("math.12")); //$NON-NLS-1$
172: }
173: if (val[0] < 0) {
174: sign = -1;
175: putBytesNegativeToIntegers(val);
176: } else {
177: sign = 1;
178: putBytesPositiveToIntegers(val);
179: }
180: cutOffLeadingZeroes();
181: }
182:
183: /* Package Constructors */
184:
185: /**
186: * Constructs a number which array is of size 1.
187: *
188: * @param sign
189: * the sign of the number
190: * @param value
191: * the only one digit of array
192: */
193: BigInteger(int sign, int value) {
194: this .sign = sign;
195: numberLength = 1;
196: digits = new int[] { value };
197: }
198:
199: /**
200: * Constructs a number without to create new space. This construct should be
201: * used only if the three fields of representation are known.
202: *
203: * @param sign
204: * the sign of the number
205: * @param numberLength
206: * the length of the internal array
207: * @param digits
208: * a reference of some array created before
209: */
210: BigInteger(int sign, int numberLength, int[] digits) {
211: this .sign = sign;
212: this .numberLength = numberLength;
213: this .digits = digits;
214: }
215:
216: /**
217: * Creates a new {@code BigInteger} whose value is equal to the specified
218: * {@code long}.
219: *
220: * @param sign
221: * the sign of the number
222: * @param val
223: * the value of the new {@code BigInteger}.
224: */
225: BigInteger(int sign, long val) {
226: // PRE: (val >= 0) && (sign >= -1) && (sign <= 1)
227: this .sign = sign;
228: if ((val & 0xFFFFFFFF00000000L) == 0) {
229: // It fits in one 'int'
230: numberLength = 1;
231: digits = new int[] { (int) val };
232: } else {
233: numberLength = 2;
234: digits = new int[] { (int) val, (int) (val >> 32) };
235: }
236: }
237:
238: /**
239: * Creates a new {@code BigInteger} with the given sign and magnitude. This
240: * constructor does not create a copy, so any changes to the reference will
241: * affect the new number.
242: *
243: * @param signum
244: * The sign of the number represented by {@code digits}
245: * @param digits
246: * The magnitude of the number
247: */
248: BigInteger(int signum, int digits[]) {
249: if (digits.length == 0) {
250: sign = 0;
251: numberLength = 1;
252: this .digits = new int[] { 0 };
253: } else {
254: sign = signum;
255: numberLength = digits.length;
256: this .digits = digits;
257: cutOffLeadingZeroes();
258: }
259: }
260:
261: public static BigInteger valueOf(long val) {
262: if (val < 0) {
263: if (val != -1) {
264: return new BigInteger(-1, -val);
265: }
266: return MINUS_ONE;
267: } else if (val <= 10) {
268: return SMALL_VALUES[(int) val];
269: } else {// (val > 10)
270: return new BigInteger(1, val);
271: }
272: }
273:
274: public byte[] toByteArray() {
275: if (this .sign == 0) {
276: return new byte[] { 0 };
277: }
278: BigInteger temp = this ;
279: int bitLen = bitLength();
280: int iThis = getFirstNonzeroDigit();
281: int bytesLen = (bitLen >> 3) + 1;
282: /*
283: * Puts the little-endian int array representing the magnitude of this
284: * BigInteger into the big-endian byte array.
285: */
286: byte[] bytes = new byte[bytesLen];
287: int firstByteNumber = 0;
288: int highBytes;
289: int digitIndex = 0;
290: int bytesInInteger = 4;
291: int digit;
292: int hB;
293:
294: if (bytesLen - (numberLength << 2) == 1) {
295: bytes[0] = (byte) ((sign < 0) ? -1 : 0);
296: highBytes = 4;
297: firstByteNumber++;
298: } else {
299: hB = bytesLen & 3;
300: highBytes = (hB == 0) ? 4 : hB;
301: }
302:
303: digitIndex = iThis;
304: bytesLen -= iThis << 2;
305:
306: if (sign < 0) {
307: digit = -temp.digits[digitIndex];
308: digitIndex++;
309: if (digitIndex == numberLength) {
310: bytesInInteger = highBytes;
311: }
312: for (int i = 0; i < bytesInInteger; i++, digit >>= 8) {
313: bytes[--bytesLen] = (byte) digit;
314: }
315: while (bytesLen > firstByteNumber) {
316: digit = ~temp.digits[digitIndex];
317: digitIndex++;
318: if (digitIndex == numberLength) {
319: bytesInInteger = highBytes;
320: }
321: for (int i = 0; i < bytesInInteger; i++, digit >>= 8) {
322: bytes[--bytesLen] = (byte) digit;
323: }
324: }
325: } else {
326: while (bytesLen > firstByteNumber) {
327: digit = temp.digits[digitIndex];
328: digitIndex++;
329: if (digitIndex == numberLength) {
330: bytesInInteger = highBytes;
331: }
332: for (int i = 0; i < bytesInInteger; i++, digit >>= 8) {
333: bytes[--bytesLen] = (byte) digit;
334: }
335: }
336: }
337: return bytes;
338: }
339:
340: /** @see BigInteger#BigInteger(String, int) */
341: private static void setFromString(BigInteger bi, String val,
342: int radix) {
343: int sign;
344: int[] digits;
345: int numberLength;
346: int stringLength = val.length();
347: int startChar;
348: int endChar = stringLength;
349:
350: if (val.charAt(0) == '-') {
351: sign = -1;
352: startChar = 1;
353: stringLength--;
354: } else {
355: sign = 1;
356: startChar = 0;
357: }
358: /*
359: * We use the following algorithm: split a string into portions of n
360: * characters and convert each portion to an integer according to the
361: * radix. Then convert an exp(radix, n) based number to binary using the
362: * multiplication method. See D. Knuth, The Art of Computer Programming,
363: * vol. 2.
364: */
365:
366: int charsPerInt = Conversion.digitFitInInt[radix];
367: int bigRadixDigitsLength = stringLength / charsPerInt;
368: int topChars = stringLength % charsPerInt;
369:
370: if (topChars != 0) {
371: bigRadixDigitsLength++;
372: }
373: digits = new int[bigRadixDigitsLength];
374: // Get the maximal power of radix that fits in int
375: int bigRadix = Conversion.bigRadices[radix - 2];
376: // Parse an input string and accumulate the BigInteger's magnitude
377: int digitIndex = 0; // index of digits array
378: int substrEnd = startChar
379: + ((topChars == 0) ? charsPerInt : topChars);
380: int newDigit;
381:
382: for (int substrStart = startChar; substrStart < endChar; substrStart = substrEnd, substrEnd = substrStart
383: + charsPerInt) {
384: int bigRadixDigit = Integer.parseInt(val.substring(
385: substrStart, substrEnd), radix);
386: newDigit = Multiplication.multiplyByInt(digits, digitIndex,
387: bigRadix);
388: newDigit += Elementary.inplaceAdd(digits, digitIndex,
389: bigRadixDigit);
390: digits[digitIndex++] = newDigit;
391: }
392: numberLength = digitIndex;
393: bi.sign = sign;
394: bi.numberLength = numberLength;
395: bi.digits = digits;
396: bi.cutOffLeadingZeroes();
397: }
398:
399: public BigInteger abs() {
400: return ((sign < 0) ? new BigInteger(1, numberLength, digits)
401: : this );
402: }
403:
404: public BigInteger negate() {
405: return ((sign == 0) ? this : new BigInteger(-sign,
406: numberLength, digits));
407: }
408:
409: public BigInteger add(BigInteger val) {
410: return Elementary.add(this , val);
411: }
412:
413: public BigInteger subtract(BigInteger val) {
414: return Elementary.subtract(this , val);
415: }
416:
417: public int signum() {
418: return sign;
419: }
420:
421: public BigInteger shiftRight(int n) {
422: if ((n == 0) || (sign == 0)) {
423: return this ;
424: }
425: return ((n > 0) ? BitLevel.shiftRight(this , n) : BitLevel
426: .shiftLeft(this , -n));
427: }
428:
429: public BigInteger shiftLeft(int n) {
430: if ((n == 0) || (sign == 0)) {
431: return this ;
432: }
433: return ((n > 0) ? BitLevel.shiftLeft(this , n) : BitLevel
434: .shiftRight(this , -n));
435: }
436:
437: public int bitLength() {
438: return BitLevel.bitLength(this );
439: }
440:
441: public boolean testBit(int n) {
442: if (n == 0) {
443: return ((digits[0] & 1) != 0);
444: }
445: if (n < 0) {
446: // math.15=Negative bit address
447: throw new ArithmeticException(Messages.getString("math.15")); //$NON-NLS-1$
448: }
449: int intCount = n >> 5;
450: if (intCount >= numberLength) {
451: return (sign < 0);
452: }
453: int digit = digits[intCount];
454: n = (1 << (n & 31)); // int with 1 set to the needed position
455: if (sign < 0) {
456: int firstNonZeroDigit = getFirstNonzeroDigit();
457: if (intCount < firstNonZeroDigit) {
458: return false;
459: } else if (firstNonZeroDigit == intCount) {
460: digit = -digit;
461: } else {
462: digit = ~digit;
463: }
464: }
465: return ((digit & n) != 0);
466: }
467:
468: public BigInteger setBit(int n) {
469: if (!testBit(n)) {
470: return BitLevel.flipBit(this , n);
471: }
472: return this ;
473: }
474:
475: public BigInteger clearBit(int n) {
476: if (testBit(n)) {
477: return BitLevel.flipBit(this , n);
478: }
479: return this ;
480: }
481:
482: public BigInteger flipBit(int n) {
483: if (n < 0) {
484: // math.15=Negative bit address
485: throw new ArithmeticException(Messages.getString("math.15")); //$NON-NLS-1$
486: }
487: return BitLevel.flipBit(this , n);
488: }
489:
490: public int getLowestSetBit() {
491: if (sign == 0) {
492: return -1;
493: }
494: // (sign != 0) implies that exists some non zero digit
495: int i = getFirstNonzeroDigit();
496: return ((i << 5) + Integer.numberOfTrailingZeros(digits[i]));
497: }
498:
499: public int bitCount() {
500: return BitLevel.bitCount(this );
501: }
502:
503: public BigInteger not() {
504: return Logical.not(this );
505: }
506:
507: public BigInteger and(BigInteger val) {
508: return Logical.and(this , val);
509: }
510:
511: public BigInteger or(BigInteger val) {
512: return Logical.or(this , val);
513: }
514:
515: public BigInteger xor(BigInteger val) {
516: return Logical.xor(this , val);
517: }
518:
519: public BigInteger andNot(BigInteger val) {
520: return Logical.andNot(this , val);
521: }
522:
523: @Override
524: public int intValue() {
525: return (sign * digits[0]);
526: }
527:
528: @Override
529: public long longValue() {
530: long value = (numberLength > 1) ? (((long) digits[1]) << 32)
531: | (digits[0] & 0xFFFFFFFFL) : (digits[0] & 0xFFFFFFFFL);
532: return (sign * value);
533: }
534:
535: @Override
536: public float floatValue() {
537: return (float) doubleValue();
538: }
539:
540: @Override
541: public double doubleValue() {
542: return Conversion.bigInteger2Double(this );
543: }
544:
545: public int compareTo(BigInteger val) {
546: if (sign > val.sign) {
547: return GREATER;
548: }
549: if (sign < val.sign) {
550: return LESS;
551: }
552: if (numberLength > val.numberLength) {
553: return sign;
554: }
555: if (numberLength < val.numberLength) {
556: return -val.sign;
557: }
558: // Equal sign and equal numberLength
559: return (sign * Elementary.compareArrays(digits, val.digits,
560: numberLength));
561: }
562:
563: public BigInteger min(BigInteger val) {
564: return ((this .compareTo(val) == LESS) ? this : val);
565: }
566:
567: public BigInteger max(BigInteger val) {
568: return ((this .compareTo(val) == GREATER) ? this : val);
569: }
570:
571: @Override
572: public int hashCode() {
573: if (hashCode != 0) {
574: return hashCode;
575: }
576: for (int i = 0; i < digits.length; i++) {
577: hashCode = (hashCode * 33 + (digits[i] & 0xffffffff));
578: }
579: hashCode = hashCode * sign;
580: return hashCode;
581: }
582:
583: @Override
584: public boolean equals(Object x) {
585: if (this == x) {
586: return true;
587: }
588: if (x instanceof BigInteger) {
589: BigInteger x1 = (BigInteger) x;
590: return sign == x1.sign && numberLength == x1.numberLength
591: && equalsArrays(x1.digits);
592: }
593: return false;
594: }
595:
596: boolean equalsArrays(final int[] b) {
597: int i;
598: for (i = numberLength - 1; (i >= 0) && (digits[i] == b[i]); i--) {
599: // Empty
600: }
601: return i < 0;
602: }
603:
604: @Override
605: public String toString() {
606: return Conversion.toDecimalScaledString(this , 0);
607: }
608:
609: public String toString(int radix) {
610: return Conversion.bigInteger2String(this , radix);
611: }
612:
613: public BigInteger gcd(BigInteger val) {
614: BigInteger val1 = this .abs();
615: BigInteger val2 = val.abs();
616: // To avoid a possible division by zero
617: if (val1.signum() == 0) {
618: return val2;
619: } else if (val2.signum() == 0) {
620: return val1;
621: }
622:
623: // Optimization for small operands
624: // (op2.bitLength() < 64) and (op1.bitLength() < 64)
625: if (((val1.numberLength == 1) || ((val1.numberLength == 2) && (val1.digits[1] > 0)))
626: && (val2.numberLength == 1 || (val2.numberLength == 2 && val2.digits[1] > 0))) {
627: return BigInteger.valueOf(Division.gcdBinary(val1
628: .longValue(), val2.longValue()));
629: }
630:
631: return Division.gcdBinary(val1.copy(), val2.copy());
632:
633: }
634:
635: public BigInteger multiply(BigInteger val) {
636: // This let us to throw NullPointerException when val == null
637: if (val.sign == 0) {
638: return ZERO;
639: }
640: if (sign == 0) {
641: return ZERO;
642: }
643: return Multiplication.multiply(this , val);
644: }
645:
646: public BigInteger pow(int exp) {
647: if (exp < 0) {
648: // math.16=Negative exponent
649: throw new ArithmeticException(Messages.getString("math.16")); //$NON-NLS-1$
650: }
651: if (exp == 0) {
652: return ONE;
653: } else if (exp == 1 || equals(ONE) || equals(ZERO)) {
654: return this ;
655: }
656:
657: // if even take out 2^x factor which we can
658: // calculate by shifting.
659: if (!testBit(0)) {
660: int x = 1;
661: BigInteger factor = BigInteger.ONE.shiftLeft(exp);
662: while (!testBit(x)) {
663: factor = factor.shiftLeft(exp);
664: x++;
665: }
666: return factor.multiply(this .shiftRight(x).pow(exp));
667: }
668: return Multiplication.pow(this , exp);
669: }
670:
671: public BigInteger[] divideAndRemainder(BigInteger divisor) {
672: int divisorSign = divisor.sign;
673: if (divisorSign == 0) {
674: // math.17=BigInteger divide by zero
675: throw new ArithmeticException(Messages.getString("math.17")); //$NON-NLS-1$
676: }
677: int divisorLen = divisor.numberLength;
678: int[] divisorDigits = divisor.digits;
679: if (divisorLen == 1) {
680: return Division.divideAndRemainderByInteger(this ,
681: divisorDigits[0], divisorSign);
682: }
683: // res[0] is a quotient and res[1] is a remainder:
684: int[] this Digits = digits;
685: int this Len = numberLength;
686: int cmp = (this Len != divisorLen) ? ((this Len > divisorLen) ? 1
687: : -1) : Elementary.compareArrays(this Digits,
688: divisorDigits, this Len);
689: if (cmp < 0) {
690: return new BigInteger[] { ZERO, this };
691: }
692: int this Sign = sign;
693: int quotientLength = this Len - divisorLen + 1;
694: int remainderLength = divisorLen;
695: int quotientSign = ((this Sign == divisorSign) ? 1 : -1);
696: int quotientDigits[] = new int[quotientLength];
697: int remainderDigits[] = Division.divide(quotientDigits,
698: quotientLength, this Digits, this Len, divisorDigits,
699: divisorLen);
700: BigInteger result0 = new BigInteger(quotientSign,
701: quotientLength, quotientDigits);
702: BigInteger result1 = new BigInteger(this Sign, remainderLength,
703: remainderDigits);
704: result0.cutOffLeadingZeroes();
705: result1.cutOffLeadingZeroes();
706: return new BigInteger[] { result0, result1 };
707: }
708:
709: public BigInteger divide(BigInteger divisor) {
710: if (divisor.sign == 0) {
711: // math.17=BigInteger divide by zero
712: throw new ArithmeticException(Messages.getString("math.17")); //$NON-NLS-1$
713: }
714: int divisorSign = divisor.sign;
715: if (divisor.isOne()) {
716: return ((divisor.sign > 0) ? this : this .negate());
717: }
718: int this Sign = sign;
719: int this Len = numberLength;
720: int divisorLen = divisor.numberLength;
721: if (this Len + divisorLen == 2) {
722: long val = (digits[0] & 0xFFFFFFFFL)
723: / (divisor.digits[0] & 0xFFFFFFFFL);
724: if (this Sign != divisorSign) {
725: val = -val;
726: }
727: return valueOf(val);
728: }
729: int cmp = ((this Len != divisorLen) ? ((this Len > divisorLen) ? 1
730: : -1)
731: : Elementary.compareArrays(digits, divisor.digits,
732: this Len));
733: if (cmp == EQUALS) {
734: return ((this Sign == divisorSign) ? ONE : MINUS_ONE);
735: }
736: if (cmp == LESS) {
737: return ZERO;
738: }
739: int resLength = this Len - divisorLen + 1;
740: int resDigits[] = new int[resLength];
741: int resSign = ((this Sign == divisorSign) ? 1 : -1);
742: if (divisorLen == 1) {
743: Division.divideArrayByInt(resDigits, digits, this Len,
744: divisor.digits[0]);
745: } else {
746: Division.divide(resDigits, resLength, digits, this Len,
747: divisor.digits, divisorLen);
748: }
749: BigInteger result = new BigInteger(resSign, resLength,
750: resDigits);
751: result.cutOffLeadingZeroes();
752: return result;
753: }
754:
755: public BigInteger remainder(BigInteger divisor) {
756: if (divisor.sign == 0) {
757: // math.17=BigInteger divide by zero
758: throw new ArithmeticException(Messages.getString("math.17")); //$NON-NLS-1$
759: }
760: int this Len = numberLength;
761: int divisorLen = divisor.numberLength;
762: if (((this Len != divisorLen) ? ((this Len > divisorLen) ? 1 : -1)
763: : Elementary.compareArrays(digits, divisor.digits,
764: this Len)) == LESS) {
765: return this ;
766: }
767: int resLength = divisorLen;
768: int resDigits[] = new int[resLength];
769: if (resLength == 1) {
770: resDigits[0] = Division.remainderArrayByInt(digits,
771: this Len, divisor.digits[0]);
772: } else {
773: int qLen = this Len - divisorLen + 1;
774: resDigits = Division.divide(null, qLen, digits, this Len,
775: divisor.digits, divisorLen);
776: }
777: BigInteger result = new BigInteger(sign, resLength, resDigits);
778: result.cutOffLeadingZeroes();
779: return result;
780: }
781:
782: public BigInteger modInverse(BigInteger m) {
783: if (m.sign <= 0) {
784: // math.18=BigInteger: modulus not positive
785: throw new ArithmeticException(Messages.getString("math.18")); //$NON-NLS-1$
786: }
787: // If both are even, no inverse exists
788: if (!(testBit(0) || m.testBit(0))) {
789: // math.19=BigInteger not invertible.
790: throw new ArithmeticException(Messages.getString("math.19")); //$NON-NLS-1$
791: }
792: if (m.isOne()) {
793: return ZERO;
794: }
795:
796: // From now on: (m > 1)
797: BigInteger res = Division.modInverseMontgomery(abs().mod(m), m);
798: if (res.sign == 0) {
799: // math.19=BigInteger not invertible.
800: throw new ArithmeticException(Messages.getString("math.19")); //$NON-NLS-1$
801: }
802:
803: res = ((sign < 0) ? m.subtract(res) : res);
804: return res;
805:
806: }
807:
808: public BigInteger modPow(BigInteger exponent, BigInteger m) {
809: if (m.sign <= 0) {
810: // math.18=BigInteger: modulus not positive
811: throw new ArithmeticException(Messages.getString("math.18")); //$NON-NLS-1$
812: }
813: BigInteger base = this ;
814:
815: if (m.isOne() | (exponent.sign > 0 & base.sign == 0)) {
816: return BigInteger.ZERO;
817: }
818: if (base.sign == 0 && exponent.sign == 0) {
819: return BigInteger.ONE;
820: }
821: if (exponent.sign < 0) {
822: base = modInverse(m);
823: exponent = exponent.negate();
824: }
825: // From now on: (m > 0) and (exponent >= 0)
826: BigInteger res = (m.testBit(0)) ? Division.oddModPow(
827: base.abs(), exponent, m) : Division.evenModPow(base
828: .abs(), exponent, m);
829: if ((base.sign < 0) && exponent.testBit(0)) {
830: // -b^e mod m == ((-1 mod m) * (b^e mod m)) mod m
831: res = m.subtract(BigInteger.ONE).multiply(res).mod(m);
832: }
833: // else exponent is even, so base^exp is positive
834: return res;
835: }
836:
837: public BigInteger mod(BigInteger m) {
838: if (m.sign <= 0) {
839: // math.18=BigInteger: modulus not positive
840: throw new ArithmeticException(Messages.getString("math.18")); //$NON-NLS-1$
841: }
842: BigInteger rem = remainder(m);
843: return ((rem.sign < 0) ? rem.add(m) : rem);
844: }
845:
846: public boolean isProbablePrime(int certainty) {
847: return Primality.isProbablePrime(abs(), certainty);
848: }
849:
850: public BigInteger nextProbablePrime() {
851: if (sign < 0) {
852: // math.1A=start < 0: {0}
853: throw new ArithmeticException(Messages.getString(
854: "math.1A", this )); //$NON-NLS-1$
855: }
856: return Primality.nextProbablePrime(this );
857: }
858:
859: public static BigInteger probablePrime(int bitLength, Random rnd) {
860: return new BigInteger(bitLength, 100, rnd);
861: }
862:
863: /* Private Methods */
864:
865: /** Decreases {@code numberLength} if there are zero high elements. */
866: final void cutOffLeadingZeroes() {
867: while ((numberLength > 0) && (digits[--numberLength] == 0)) {
868: // Empty
869: }
870: if (digits[numberLength++] == 0) {
871: sign = 0;
872: }
873: }
874:
875: /** Tests if {@code this.abs()} is equals to {@code ONE} */
876: boolean isOne() {
877: return ((numberLength == 1) && (digits[0] == 1));
878: }
879:
880: /**
881: * Puts a big-endian byte array into a little-endian int array.
882: */
883: private void putBytesPositiveToIntegers(byte[] byteValues) {
884: int bytesLen = byteValues.length;
885: int highBytes = bytesLen & 3;
886: numberLength = (bytesLen >> 2) + ((highBytes == 0) ? 0 : 1);
887: digits = new int[numberLength];
888: int i = 0;
889: // Put bytes to the int array starting from the end of the byte array
890: while (bytesLen > highBytes) {
891: digits[i++] = (byteValues[--bytesLen] & 0xFF)
892: | (byteValues[--bytesLen] & 0xFF) << 8
893: | (byteValues[--bytesLen] & 0xFF) << 16
894: | (byteValues[--bytesLen] & 0xFF) << 24;
895: }
896: // Put the first bytes in the highest element of the int array
897: for (int j = 0; j < bytesLen; j++) {
898: digits[i] = (digits[i] << 8) | (byteValues[j] & 0xFF);
899: }
900: }
901:
902: /**
903: * Puts a big-endian byte array into a little-endian applying two
904: * complement.
905: */
906: private void putBytesNegativeToIntegers(byte[] byteValues) {
907: int bytesLen = byteValues.length;
908: int highBytes = bytesLen & 3;
909: numberLength = (bytesLen >> 2) + ((highBytes == 0) ? 0 : 1);
910: digits = new int[numberLength];
911: int i = 0;
912: // Setting the sign
913: digits[numberLength - 1] = -1;
914: // Put bytes to the int array starting from the end of the byte array
915: while (bytesLen > highBytes) {
916: digits[i] = (byteValues[--bytesLen] & 0xFF)
917: | (byteValues[--bytesLen] & 0xFF) << 8
918: | (byteValues[--bytesLen] & 0xFF) << 16
919: | (byteValues[--bytesLen] & 0xFF) << 24;
920: if (digits[i] != 0) {
921: digits[i] = -digits[i];
922: firstNonzeroDigit = i;
923: i++;
924: while (bytesLen > highBytes) {
925: digits[i] = (byteValues[--bytesLen] & 0xFF)
926: | (byteValues[--bytesLen] & 0xFF) << 8
927: | (byteValues[--bytesLen] & 0xFF) << 16
928: | (byteValues[--bytesLen] & 0xFF) << 24;
929: digits[i] = ~digits[i];
930: i++;
931: }
932: break;
933: }
934: i++;
935: }
936: if (highBytes != 0) {
937: // Put the first bytes in the highest element of the int array
938: if (firstNonzeroDigit != -2) {
939: for (int j = 0; j < bytesLen; j++) {
940: digits[i] = (digits[i] << 8)
941: | (byteValues[j] & 0xFF);
942: }
943: digits[i] = ~digits[i];
944: } else {
945: for (int j = 0; j < bytesLen; j++) {
946: digits[i] = (digits[i] << 8)
947: | (byteValues[j] & 0xFF);
948: }
949: digits[i] = -digits[i];
950: }
951: }
952: }
953:
954: int getFirstNonzeroDigit() {
955: if (firstNonzeroDigit == -2) {
956: int i;
957: if (this .sign == 0) {
958: i = -1;
959: } else {
960: for (i = 0; digits[i] == 0; i++) {
961: // Empty
962: }
963: }
964: firstNonzeroDigit = i;
965: }
966: return firstNonzeroDigit;
967: }
968:
969: /*
970: * Returns a copy of the current instance to achieve immutability
971: */
972: BigInteger copy() {
973: int[] copyDigits = new int[numberLength];
974: System.arraycopy(digits, 0, copyDigits, 0, numberLength);
975: return new BigInteger(sign, numberLength, copyDigits);
976: }
977:
978: private void readObject(ObjectInputStream in) throws IOException,
979: ClassNotFoundException {
980: in.defaultReadObject();
981: sign = signum;
982: putBytesPositiveToIntegers(magnitude);
983: cutOffLeadingZeroes();
984: }
985:
986: private void writeObject(ObjectOutputStream out) throws IOException {
987: signum = signum();
988: magnitude = abs().toByteArray();
989: out.defaultWriteObject();
990: }
991:
992: void unCache() {
993: firstNonzeroDigit = -2;
994: }
995: }
|