< prev index next >

src/java.base/share/classes/java/math/MutableBigInteger.java

Print this page
rev 12150 : 8046943: JEP 246: Leverage CPU Instructions for GHASH and RSA
Summary: Add montgomeryMultiply intrinsic
Reviewed-by: kvn


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);


< prev index next >