2734 BigInteger result;
2735 if (m.testBit(0)) { // odd modulus
2736 result = base.oddModPow(exponent, m);
2737 } else {
2738 /*
2739 * Even modulus. Tear it into an "odd part" (m1) and power of two
2740 * (m2), exponentiate mod m1, manually exponentiate mod m2, and
2741 * use Chinese Remainder Theorem to combine results.
2742 */
2743
2744 // Tear m apart into odd part (m1) and power of 2 (m2)
2745 int p = m.getLowestSetBit(); // Max pow of 2 that divides m
2746
2747 BigInteger m1 = m.shiftRight(p); // m/2**p
2748 BigInteger m2 = ONE.shiftLeft(p); // 2**p
2749
2750 // Calculate new base from m1
2751 BigInteger base2 = (this.signum < 0 || this.compareTo(m1) >= 0
2752 ? this.mod(m1) : this);
2753
2754 // Caculate (base ** exponent) mod m1.
2755 BigInteger a1 = (m1.equals(ONE) ? ZERO :
2756 base2.oddModPow(exponent, m1));
2757
2758 // Calculate (this ** exponent) mod m2
2759 BigInteger a2 = base.modPow2(exponent, p);
2760
2761 // Combine results using Chinese Remainder Theorem
2762 BigInteger y1 = m2.modInverse(m1);
2763 BigInteger y2 = m1.modInverse(m2);
2764
2765 if (m.mag.length < MAX_MAG_LENGTH / 2) {
2766 result = a1.multiply(m2).multiply(y1).add(a2.multiply(m1).multiply(y2)).mod(m);
2767 } else {
2768 MutableBigInteger t1 = new MutableBigInteger();
2769 new MutableBigInteger(a1.multiply(m2)).multiply(new MutableBigInteger(y1), t1);
2770 MutableBigInteger t2 = new MutableBigInteger();
2771 new MutableBigInteger(a2.multiply(m1)).multiply(new MutableBigInteger(y2), t2);
2772 t1.add(t2);
2773 MutableBigInteger q = new MutableBigInteger();
2774 result = t1.divide(new MutableBigInteger(m), q).toBigInteger();
2888 * end of the exponent is unimportant, but it is filled with zero here.)
2889 * When the most-significant bit of this buffer becomes set, i.e.
2890 * (buf & tblmask) != 0, we have to decide what pattern to multiply
2891 * by, and when to do it. We decide, remember to do it in future
2892 * after a suitable number of squarings have passed (e.g. a pattern
2893 * of "100" in the buffer requires that we multiply by n^1 immediately;
2894 * a pattern of "110" calls for multiplying by n^3 after one more
2895 * squaring), clear the buffer, and continue.
2896 *
2897 * When we start, there is one more optimization: the result buffer
2898 * is implcitly one, so squaring it or multiplying by it can be
2899 * optimized away. Further, if we start with a pattern like "100"
2900 * in the lookahead window, rather than placing n into the buffer
2901 * and then starting to square it, we have already computed n^2
2902 * to compute the odd-powers table, so we can place that into
2903 * the buffer and save a squaring.
2904 *
2905 * This means that if you have a k-bit window, to compute n^z,
2906 * where z is the high k bits of the exponent, 1/2 of the time
2907 * it requires no squarings. 1/4 of the time, it requires 1
2908 * squaring, ... 1/2^(k-1) of the time, it reqires k-2 squarings.
2909 * And the remaining 1/2^(k-1) of the time, the top k bits are a
2910 * 1 followed by k-1 0 bits, so it again only requires k-2
2911 * squarings, not k-1. The average of these is 1. Add that
2912 * to the one squaring we have to do to compute the table,
2913 * and you'll see that a k-bit window saves k-2 squarings
2914 * as well as reducing the multiplies. (It actually doesn't
2915 * hurt in the case k = 1, either.)
2916 */
2917 // Special case for exponent of one
2918 if (y.equals(ONE))
2919 return this;
2920
2921 // Special case for base of zero
2922 if (signum == 0)
2923 return ZERO;
2924
2925 int[] base = mag.clone();
2926 int[] exp = y.mag;
2927 int[] mod = z.mag;
2928 int modLen = mod.length;
|
2734 BigInteger result;
2735 if (m.testBit(0)) { // odd modulus
2736 result = base.oddModPow(exponent, m);
2737 } else {
2738 /*
2739 * Even modulus. Tear it into an "odd part" (m1) and power of two
2740 * (m2), exponentiate mod m1, manually exponentiate mod m2, and
2741 * use Chinese Remainder Theorem to combine results.
2742 */
2743
2744 // Tear m apart into odd part (m1) and power of 2 (m2)
2745 int p = m.getLowestSetBit(); // Max pow of 2 that divides m
2746
2747 BigInteger m1 = m.shiftRight(p); // m/2**p
2748 BigInteger m2 = ONE.shiftLeft(p); // 2**p
2749
2750 // Calculate new base from m1
2751 BigInteger base2 = (this.signum < 0 || this.compareTo(m1) >= 0
2752 ? this.mod(m1) : this);
2753
2754 // Calculate (base ** exponent) mod m1.
2755 BigInteger a1 = (m1.equals(ONE) ? ZERO :
2756 base2.oddModPow(exponent, m1));
2757
2758 // Calculate (this ** exponent) mod m2
2759 BigInteger a2 = base.modPow2(exponent, p);
2760
2761 // Combine results using Chinese Remainder Theorem
2762 BigInteger y1 = m2.modInverse(m1);
2763 BigInteger y2 = m1.modInverse(m2);
2764
2765 if (m.mag.length < MAX_MAG_LENGTH / 2) {
2766 result = a1.multiply(m2).multiply(y1).add(a2.multiply(m1).multiply(y2)).mod(m);
2767 } else {
2768 MutableBigInteger t1 = new MutableBigInteger();
2769 new MutableBigInteger(a1.multiply(m2)).multiply(new MutableBigInteger(y1), t1);
2770 MutableBigInteger t2 = new MutableBigInteger();
2771 new MutableBigInteger(a2.multiply(m1)).multiply(new MutableBigInteger(y2), t2);
2772 t1.add(t2);
2773 MutableBigInteger q = new MutableBigInteger();
2774 result = t1.divide(new MutableBigInteger(m), q).toBigInteger();
2888 * end of the exponent is unimportant, but it is filled with zero here.)
2889 * When the most-significant bit of this buffer becomes set, i.e.
2890 * (buf & tblmask) != 0, we have to decide what pattern to multiply
2891 * by, and when to do it. We decide, remember to do it in future
2892 * after a suitable number of squarings have passed (e.g. a pattern
2893 * of "100" in the buffer requires that we multiply by n^1 immediately;
2894 * a pattern of "110" calls for multiplying by n^3 after one more
2895 * squaring), clear the buffer, and continue.
2896 *
2897 * When we start, there is one more optimization: the result buffer
2898 * is implcitly one, so squaring it or multiplying by it can be
2899 * optimized away. Further, if we start with a pattern like "100"
2900 * in the lookahead window, rather than placing n into the buffer
2901 * and then starting to square it, we have already computed n^2
2902 * to compute the odd-powers table, so we can place that into
2903 * the buffer and save a squaring.
2904 *
2905 * This means that if you have a k-bit window, to compute n^z,
2906 * where z is the high k bits of the exponent, 1/2 of the time
2907 * it requires no squarings. 1/4 of the time, it requires 1
2908 * squaring, ... 1/2^(k-1) of the time, it requires k-2 squarings.
2909 * And the remaining 1/2^(k-1) of the time, the top k bits are a
2910 * 1 followed by k-1 0 bits, so it again only requires k-2
2911 * squarings, not k-1. The average of these is 1. Add that
2912 * to the one squaring we have to do to compute the table,
2913 * and you'll see that a k-bit window saves k-2 squarings
2914 * as well as reducing the multiplies. (It actually doesn't
2915 * hurt in the case k = 1, either.)
2916 */
2917 // Special case for exponent of one
2918 if (y.equals(ONE))
2919 return this;
2920
2921 // Special case for base of zero
2922 if (signum == 0)
2923 return ZERO;
2924
2925 int[] base = mag.clone();
2926 int[] exp = y.mag;
2927 int[] mod = z.mag;
2928 int modLen = mod.length;
|