2048 result.value[1] = (int)tLong;
2049 result.intLen = 2;
2050 result.normalize();
2051 return result;
2052 }
2053
2054 /**
2055 * Returns the multiplicative inverse of val mod 2^32. Assumes val is odd.
2056 */
2057 static int inverseMod32(int val) {
2058 // Newton's iteration!
2059 int t = val;
2060 t *= 2 - val*t;
2061 t *= 2 - val*t;
2062 t *= 2 - val*t;
2063 t *= 2 - val*t;
2064 return t;
2065 }
2066
2067 /**
2068 * Calculate the multiplicative inverse of 2^k mod mod, where mod is odd.
2069 */
2070 static MutableBigInteger modInverseBP2(MutableBigInteger mod, int k) {
2071 // Copy the mod to protect original
2072 return fixup(new MutableBigInteger(1), new MutableBigInteger(mod), k);
2073 }
2074
2075 /**
2076 * Calculate the multiplicative inverse of this mod mod, where mod is odd.
2077 * This and mod are not changed by the calculation.
2078 *
2079 * This method implements an algorithm due to Richard Schroeppel, that uses
2080 * the same intermediate representation as Montgomery Reduction
2081 * ("Montgomery Form"). The algorithm is described in an unpublished
2082 * manuscript entitled "Fast Modular Reciprocals."
2083 */
2084 private MutableBigInteger modInverse(MutableBigInteger mod) {
2085 MutableBigInteger p = new MutableBigInteger(mod);
2086 MutableBigInteger f = new MutableBigInteger(this);
2087 MutableBigInteger g = new MutableBigInteger(p);
|
2048 result.value[1] = (int)tLong;
2049 result.intLen = 2;
2050 result.normalize();
2051 return result;
2052 }
2053
2054 /**
2055 * Returns the multiplicative inverse of val mod 2^32. Assumes val is odd.
2056 */
2057 static int inverseMod32(int val) {
2058 // Newton's iteration!
2059 int t = val;
2060 t *= 2 - val*t;
2061 t *= 2 - val*t;
2062 t *= 2 - val*t;
2063 t *= 2 - val*t;
2064 return t;
2065 }
2066
2067 /**
2068 * Returns the multiplicative inverse of val mod 2^64. Assumes val is odd.
2069 */
2070 static long inverseMod64(long val) {
2071 // Newton's iteration!
2072 long t = val;
2073 t *= 2 - val*t;
2074 t *= 2 - val*t;
2075 t *= 2 - val*t;
2076 t *= 2 - val*t;
2077 t *= 2 - val*t;
2078 assert(t * val == 1);
2079 return t;
2080 }
2081
2082 /**
2083 * Calculate the multiplicative inverse of 2^k mod mod, where mod is odd.
2084 */
2085 static MutableBigInteger modInverseBP2(MutableBigInteger mod, int k) {
2086 // Copy the mod to protect original
2087 return fixup(new MutableBigInteger(1), new MutableBigInteger(mod), k);
2088 }
2089
2090 /**
2091 * Calculate the multiplicative inverse of this mod mod, where mod is odd.
2092 * This and mod are not changed by the calculation.
2093 *
2094 * This method implements an algorithm due to Richard Schroeppel, that uses
2095 * the same intermediate representation as Montgomery Reduction
2096 * ("Montgomery Form"). The algorithm is described in an unpublished
2097 * manuscript entitled "Fast Modular Reciprocals."
2098 */
2099 private MutableBigInteger modInverse(MutableBigInteger mod) {
2100 MutableBigInteger p = new MutableBigInteger(mod);
2101 MutableBigInteger f = new MutableBigInteger(this);
2102 MutableBigInteger g = new MutableBigInteger(p);
|