Fri, 04 Mar 2016 16:15:48 +0300
8130150: Implement BigInteger.montgomeryMultiply intrinsic
Reviewed-by: kvn, mdoerr
1 //
2 // Copyright (c) 2000, 2015, Oracle and/or its affiliates. All rights reserved.
3 // Copyright (c) 2015, Red Hat Inc. All rights reserved.
4 // DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
5 //
6 // This code is free software; you can redistribute it and/or modify it
7 // under the terms of the GNU General Public License version 2 only, as
8 // published by the Free Software Foundation.
9 //
10 // This code is distributed in the hope that it will be useful, but WITHOUT
11 // ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
12 // FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
13 // version 2 for more details (a copy is included in the LICENSE file that
14 // accompanied this code).
15 //
16 // You should have received a copy of the GNU General Public License version
17 // 2 along with this work; if not, write to the Free Software Foundation,
18 // Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
19 //
20 // Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
21 // or visit www.oracle.com if you need additional information or have any
22 // questions.
23 //
24 //
26 import java.lang.invoke.MethodHandle;
27 import java.lang.invoke.MethodHandles;
28 import java.lang.invoke.MethodType;
29 import java.lang.reflect.Constructor;
30 import java.lang.reflect.Field;
31 import java.lang.reflect.Method;
32 import java.math.BigInteger;
33 import java.util.Arrays;
34 import java.util.Random;
36 /**
37 * @test
38 * @bug 8130150
39 * @library /testlibrary
40 * @requires (os.simpleArch == "x64") & (os.family != "windows")
41 * @summary Verify that the Montgomery multiply intrinsic works and correctly checks its arguments.
42 */
44 public class MontgomeryMultiplyTest {
46 static final MethodHandles.Lookup lookup = MethodHandles.lookup();
48 static final MethodHandle montgomeryMultiplyHandle, montgomerySquareHandle;
49 static final MethodHandle bigIntegerConstructorHandle;
50 static final Field bigIntegerMagField;
52 static {
53 // Use reflection to gain access to the methods we want to test.
54 try {
55 Method m = BigInteger.class.getDeclaredMethod("montgomeryMultiply",
56 /*a*/int[].class, /*b*/int[].class, /*n*/int[].class, /*len*/int.class,
57 /*inv*/long.class, /*product*/int[].class);
58 m.setAccessible(true);
59 montgomeryMultiplyHandle = lookup.unreflect(m);
61 m = BigInteger.class.getDeclaredMethod("montgomerySquare",
62 /*a*/int[].class, /*n*/int[].class, /*len*/int.class,
63 /*inv*/long.class, /*product*/int[].class);
64 m.setAccessible(true);
65 montgomerySquareHandle = lookup.unreflect(m);
67 Constructor c
68 = BigInteger.class.getDeclaredConstructor(int.class, int[].class);
69 c.setAccessible(true);
70 bigIntegerConstructorHandle = lookup.unreflectConstructor(c);
72 bigIntegerMagField = BigInteger.class.getDeclaredField("mag");
73 bigIntegerMagField.setAccessible(true);
75 } catch (Throwable ex) {
76 throw new RuntimeException(ex);
77 }
78 }
80 // Invoke either BigInteger.montgomeryMultiply or BigInteger.montgomerySquare.
81 int[] montgomeryMultiply(int[] a, int[] b, int[] n, int len, long inv,
82 int[] product) throws Throwable {
83 int[] result =
84 (a == b) ? (int[]) montgomerySquareHandle.invokeExact(a, n, len, inv, product)
85 : (int[]) montgomeryMultiplyHandle.invokeExact(a, b, n, len, inv, product);
86 return Arrays.copyOf(result, len);
87 }
89 // Invoke the private constructor BigInteger(int[]).
90 BigInteger newBigInteger(int[] val) throws Throwable {
91 return (BigInteger) bigIntegerConstructorHandle.invokeExact(1, val);
92 }
94 // Get the private field BigInteger.mag
95 int[] mag(BigInteger n) {
96 try {
97 return (int[]) bigIntegerMagField.get(n);
98 } catch (Exception ex) {
99 throw new RuntimeException(ex);
100 }
101 }
103 // Montgomery multiplication
104 // Calculate a * b * r^-1 mod n)
105 //
106 // R is a power of the word size
107 // N' = R^-1 mod N
108 //
109 // T := ab
110 // m := (T mod R)N' mod R [so 0 <= m < R]
111 // t := (T + mN)/R
112 // if t >= N then return t - N else return t
113 //
114 BigInteger montgomeryMultiply(BigInteger a, BigInteger b, BigInteger N,
115 int len, BigInteger n_prime)
116 throws Throwable {
117 BigInteger T = a.multiply(b);
118 BigInteger R = BigInteger.ONE.shiftLeft(len*32);
119 BigInteger mask = R.subtract(BigInteger.ONE);
120 BigInteger m = (T.and(mask)).multiply(n_prime);
121 m = m.and(mask); // i.e. m.mod(R)
122 T = T.add(m.multiply(N));
123 T = T.shiftRight(len*32); // i.e. T.divide(R)
124 if (T.compareTo(N) > 0) {
125 T = T.subtract(N);
126 }
127 return T;
128 }
130 // Call the Montgomery multiply intrinsic.
131 BigInteger montgomeryMultiply(int[] a_words, int[] b_words, int[] n_words,
132 int len, BigInteger inv)
133 throws Throwable {
134 BigInteger t = montgomeryMultiply(
135 newBigInteger(a_words),
136 newBigInteger(b_words),
137 newBigInteger(n_words),
138 len, inv);
139 return t;
140 }
142 // Check that the Montgomery multiply intrinsic returns the same
143 // result as the longhand calculation.
144 void check(int[] a_words, int[] b_words, int[] n_words, int len, BigInteger inv)
145 throws Throwable {
146 BigInteger n = newBigInteger(n_words);
147 BigInteger slow = montgomeryMultiply(a_words, b_words, n_words, len, inv);
148 BigInteger fast
149 = newBigInteger(montgomeryMultiply
150 (a_words, b_words, n_words, len, inv.longValue(), null));
151 // The intrinsic may not return the same value as the longhand
152 // calculation but they must have the same residue mod N.
153 if (!slow.mod(n).equals(fast.mod(n))) {
154 throw new RuntimeException();
155 }
156 }
158 Random rnd = new Random(0);
160 // Return a random value of length <= bits in an array of even length
161 int[] random_val(int bits) {
162 int len = (bits+63)/64; // i.e. length in longs
163 int[] val = new int[len*2];
164 for (int i = 0; i < val.length; i++)
165 val[i] = rnd.nextInt();
166 int leadingZeros = 64 - (bits & 64);
167 if (leadingZeros >= 32) {
168 val[0] = 0;
169 val[1] &= ~(-1l << (leadingZeros & 31));
170 } else {
171 val[0] &= ~(-1l << leadingZeros);
172 }
173 return val;
174 }
176 void testOneLength(int lenInBits, int lenInInts) throws Throwable {
177 BigInteger mod = new BigInteger(lenInBits, 2, rnd);
178 BigInteger r = BigInteger.ONE.shiftLeft(lenInInts * 32);
179 BigInteger n_prime = mod.modInverse(r).negate();
181 // Make n.length even, padding with a zero if necessary
182 int[] n = mag(mod);
183 if (n.length < lenInInts) {
184 int[] x = new int[lenInInts];
185 System.arraycopy(n, 0, x, lenInInts-n.length, n.length);
186 n = x;
187 }
189 for (int i = 0; i < 10000; i++) {
190 // multiply
191 check(random_val(lenInBits), random_val(lenInBits), n, lenInInts, n_prime);
192 // square
193 int[] tmp = random_val(lenInBits);
194 check(tmp, tmp, n, lenInInts, n_prime);
195 }
196 }
198 // Test the Montgomery multiply intrinsic with a bunch of random
199 // values of varying lengths. Do this for long enough that the
200 // caller of the intrinsic is C2-compiled.
201 void testResultValues() throws Throwable {
202 // Test a couple of interesting edge cases.
203 testOneLength(1024, 32);
204 testOneLength(1025, 34);
205 for (int j = 10; j > 0; j--) {
206 // Construct a random prime whose length in words is even
207 int lenInBits = rnd.nextInt(2048) + 64;
208 int lenInInts = (lenInBits + 63)/64*2;
209 testOneLength(lenInBits, lenInInts);
210 }
211 }
213 // Range checks
214 void testOneMontgomeryMultiplyCheck(int[] a, int[] b, int[] n, int len, long inv,
215 int[] product, Class klass) {
216 try {
217 montgomeryMultiply(a, b, n, len, inv, product);
218 } catch (Throwable ex) {
219 if (klass.isAssignableFrom(ex.getClass()))
220 return;
221 throw new RuntimeException(klass + " expected, " + ex + " was thrown");
222 }
223 throw new RuntimeException(klass + " expected, was not thrown");
224 }
226 void testOneMontgomeryMultiplyCheck(int[] a, int[] b, BigInteger n, int len, BigInteger inv,
227 Class klass) {
228 testOneMontgomeryMultiplyCheck(a, b, mag(n), len, inv.longValue(), null, klass);
229 }
231 void testOneMontgomeryMultiplyCheck(int[] a, int[] b, BigInteger n, int len, BigInteger inv,
232 int[] product, Class klass) {
233 testOneMontgomeryMultiplyCheck(a, b, mag(n), len, inv.longValue(), product, klass);
234 }
236 void testMontgomeryMultiplyChecks() {
237 int[] blah = random_val(40);
238 int[] small = random_val(39);
239 BigInteger mod = new BigInteger(40*32 , 2, rnd);
240 BigInteger r = BigInteger.ONE.shiftLeft(40*32);
241 BigInteger n_prime = mod.modInverse(r).negate();
243 // Length out of range: square
244 testOneMontgomeryMultiplyCheck(blah, blah, mod, 41, n_prime, IllegalArgumentException.class);
245 testOneMontgomeryMultiplyCheck(blah, blah, mod, 0, n_prime, IllegalArgumentException.class);
246 testOneMontgomeryMultiplyCheck(blah, blah, mod, -1, n_prime, IllegalArgumentException.class);
247 // As above, but for multiply
248 testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 41, n_prime, IllegalArgumentException.class);
249 testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 0, n_prime, IllegalArgumentException.class);
250 testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 0, n_prime, IllegalArgumentException.class);
252 // Length odd
253 testOneMontgomeryMultiplyCheck(small, small, mod, 39, n_prime, IllegalArgumentException.class);
254 testOneMontgomeryMultiplyCheck(small, small, mod, 0, n_prime, IllegalArgumentException.class);
255 testOneMontgomeryMultiplyCheck(small, small, mod, -1, n_prime, IllegalArgumentException.class);
256 // As above, but for multiply
257 testOneMontgomeryMultiplyCheck(small, small.clone(), mod, 39, n_prime, IllegalArgumentException.class);
258 testOneMontgomeryMultiplyCheck(small, small.clone(), mod, 0, n_prime, IllegalArgumentException.class);
259 testOneMontgomeryMultiplyCheck(small, small.clone(), mod, -1, n_prime, IllegalArgumentException.class);
261 // array too small
262 testOneMontgomeryMultiplyCheck(blah, blah, mod, 40, n_prime, small, IllegalArgumentException.class);
263 testOneMontgomeryMultiplyCheck(blah, blah.clone(), mod, 40, n_prime, small, IllegalArgumentException.class);
264 testOneMontgomeryMultiplyCheck(small, blah, mod, 40, n_prime, blah, IllegalArgumentException.class);
265 testOneMontgomeryMultiplyCheck(blah, small, mod, 40, n_prime, blah, IllegalArgumentException.class);
266 testOneMontgomeryMultiplyCheck(blah, blah, mod, 40, n_prime, small, IllegalArgumentException.class);
267 testOneMontgomeryMultiplyCheck(small, small, mod, 40, n_prime, blah, IllegalArgumentException.class);
268 }
270 public static void main(String args[]) {
271 try {
272 new MontgomeryMultiplyTest().testMontgomeryMultiplyChecks();
273 new MontgomeryMultiplyTest().testResultValues();
274 } catch (Throwable ex) {
275 throw new RuntimeException(ex);
276 }
277 }
278 }