Mercurial > hg > release > icedtea7-forest-2.6 > jdk
changeset 9923:1ca2034e7079
8225603: Enhancement for big integers
Reviewed-by: darcy, ahgross, rhalade
author | bpb |
---|---|
date | Tue, 29 Oct 2019 14:07:27 -0700 |
parents | 1a95d48e5ff1 |
children | 269d16463fb2 |
files | src/share/classes/java/math/MutableBigInteger.java src/share/native/sun/security/ec/impl/mpi.c test/java/math/BigInteger/ModInvTime.java |
diffstat | 3 files changed, 80 insertions(+), 10 deletions(-) [+] |
line wrap: on
line diff
--- a/src/share/classes/java/math/MutableBigInteger.java Tue Apr 07 23:47:10 2020 +0100 +++ b/src/share/classes/java/math/MutableBigInteger.java Tue Oct 29 14:07:27 2019 -0700 @@ -1,5 +1,5 @@ /* - * Copyright (c) 1999, 2007, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 1999, 2020, Oracle and/or its affiliates. All rights reserved. * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. * * This code is free software; you can redistribute it and/or modify it @@ -1311,8 +1311,8 @@ } /** - * Calculate the multiplicative inverse of this mod mod, where mod is odd. - * This and mod are not changed by the calculation. + * Calculate the multiplicative inverse of this modulo mod, where the mod + * argument is odd. This and mod are not changed by the calculation. * * This method implements an algorithm due to Richard Schroeppel, that uses * the same intermediate representation as Montgomery Reduction @@ -1366,8 +1366,18 @@ k += trailingZeros; } - while (c.sign < 0) - c.signedAdd(p); + if (c.compare(p) >= 0) { // c has a larger magnitude than p + MutableBigInteger remainder = c.divide(p, + new MutableBigInteger()); + // The previous line ignores the sign so we copy the data back + // into c which will restore the sign as needed (and converts + // it back to a SignedMutableBigInteger) + c.copyValue(remainder); + } + + if (c.sign < 0) { + c.signedAdd(p); + } return fixup(c, p, k); } @@ -1405,8 +1415,8 @@ } // In theory, c may be greater than p at this point (Very rare!) - while (c.compare(p) >= 0) - c.subtract(p); + if (c.compare(p) >= 0) + c = c.divide(p, new MutableBigInteger()); return c; }
--- a/src/share/native/sun/security/ec/impl/mpi.c Tue Apr 07 23:47:10 2020 +0100 +++ b/src/share/native/sun/security/ec/impl/mpi.c Tue Oct 29 14:07:27 2019 -0700 @@ -1,5 +1,5 @@ /* - * Copyright (c) 2007, 2014, Oracle and/or its affiliates. All rights reserved. + * Copyright (c) 2007, 2020, Oracle and/or its affiliates. All rights reserved. * Use is subject to license terms. * * This library is free software; you can redistribute it and/or @@ -34,7 +34,7 @@ * Netscape Communications Corporation * Douglas Stebila <douglas@stebila.ca> of Sun Laboratories. * - * Last Modified Date from the Original Code: June 2014 + * Last Modified Date from the Original Code: Nov 2019 *********************************************************************** */ /* Arbitrary precision integer arithmetic library */ @@ -2134,7 +2134,10 @@ } } if (res >= 0) { - while (MP_SIGN(c) != MP_ZPOS) { + if (s_mp_cmp(c, p) >= 0) { + MP_CHECKOK( mp_div(c, p, NULL, c)); + } + if (MP_SIGN(c) != MP_ZPOS) { MP_CHECKOK( mp_add(c, p, c) ); } res = k;
--- /dev/null Thu Jan 01 00:00:00 1970 +0000 +++ b/test/java/math/BigInteger/ModInvTime.java Tue Oct 29 14:07:27 2019 -0700 @@ -0,0 +1,57 @@ +/* + * Copyright (c) 2020, Oracle and/or its affiliates. All rights reserved. + * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER. + * + * This code is free software; you can redistribute it and/or modify it + * under the terms of the GNU General Public License version 2 only, as + * published by the Free Software Foundation. + * + * This code is distributed in the hope that it will be useful, but WITHOUT + * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or + * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License + * version 2 for more details (a copy is included in the LICENSE file that + * accompanied this code). + * + * You should have received a copy of the GNU General Public License version + * 2 along with this work; if not, write to the Free Software Foundation, + * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA. + * + * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA + * or visit www.oracle.com if you need additional information or have any + * questions. + */ + +/* + * @test + * @bug 8225603 + * @summary Tests whether modInverse() completes in a reasonable time + * @run main/othervm ModInvTime + */ +import java.math.BigInteger; + +public class ModInvTime { + public static void main(String[] args) throws InterruptedException { + BigInteger prime = new BigInteger("39402006196394479212279040100143613805079739270465446667946905279627659399113263569398956308152294913554433653942643"); + BigInteger s = new BigInteger("9552729729729327851382626410162104591956625415831952158766936536163093322096473638446154604799898109762512409920799"); + System.out.format("int length: %d, modulus length: %d%n", + s.bitLength(), prime.bitLength()); + + System.out.println("Computing modular inverse ..."); + BigInteger mi = s.modInverse(prime); + System.out.format("Modular inverse: %s%n", mi); + check(s, prime, mi); + + BigInteger ns = s.negate(); + BigInteger nmi = ns.modInverse(prime); + System.out.format("Modular inverse of negation: %s%n", nmi); + check(ns, prime, nmi); + } + + public static void check(BigInteger val, BigInteger mod, BigInteger inv) { + BigInteger r = inv.multiply(val).remainder(mod); + if (r.signum() == -1) + r = r.add(mod); + if (!r.equals(BigInteger.ONE)) + throw new RuntimeException("Numerically incorrect modular inverse"); + } +}