harmony-commits mailing list archives

Site index · List index
Message view « Date » · « Thread »
Top « Date » · « Thread »
From telli...@apache.org
Subject svn commit: r910505 - /harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Division.java
Date Tue, 16 Feb 2010 12:44:51 GMT
Author: tellison
Date: Tue Feb 16 12:44:50 2010
New Revision: 910505

URL: http://svn.apache.org/viewvc?rev=910505&view=rev
Log:
Remove Lorencz-based algorithm and replace with alternative based on Hars' paper (see source
comments) for computing modInverse of BigIntegers.

Modified:
    harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Division.java

Modified: harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Division.java
URL: http://svn.apache.org/viewvc/harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Division.java?rev=910505&r1=910504&r2=910505&view=diff
==============================================================================
--- harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Division.java (original)
+++ harmony/enhanced/classlib/trunk/modules/math/src/main/java/java/math/Division.java Tue
Feb 16 12:44:50 2010
@@ -488,7 +488,7 @@
         
         if (!p.testBit(0)){
             // montgomery inverse require even modulo
-            return modInverseLorencz(a, p);
+            return modInverseHars(a, p);
         }
         
         int m = p.numberLength * 32;
@@ -583,156 +583,87 @@
         return (int)(n2 & 0xFFFFFFFFL);
     }
 
-    /**
-     * @return bi == abs(2^exp)
-     */
-    private static boolean isPowerOfTwo(BigInteger bi, int exp) {
-        boolean result = false;
-        result = ( exp >> 5 == bi.numberLength - 1 )
-        && ( bi.digits[bi.numberLength - 1] == 1 << ( exp & 31 ) );
-        if (result) {
-            for (int i = 0; result && i < bi.numberLength - 1; i++) {
-                result = bi.digits[i] == 0;
+    static BigInteger squareAndMultiply(BigInteger x2, BigInteger a2, BigInteger exponent,BigInteger
modulus, int n2  ){
+        BigInteger res = x2;
+        for (int i = exponent.bitLength() - 1; i >= 0; i--) {
+            res = monPro(res,res,modulus, n2);
+            if (BitLevel.testBit(exponent, i)) {
+                res = monPro(res, a2, modulus, n2);
             }
         }
-        return result;
+        return res;
     }
-    
+
     /**
-     * Calculate how many iteration of Lorencz's algorithm would perform the
-     * same operation
-     *
-     * @param bi
-     * @param n
-     * @return
-     */
-    private static int howManyIterations(BigInteger bi, int n) {
-        int i = n - 1;
-        if (bi.sign > 0) {
-            while (!bi.testBit(i))
-                i--;
-            return n - 1 - i;
+     * Implements the "Shifting Euclidean modular inverse algorithm".
+     * "Laszlo Hars - Modular Inverse Algorithms Without Multiplications
+     * for Cryptographic Applications"
+     * 
+     * @see BigInteger#modInverse(BigInteger)
+     * @param a
+     *            a positive number
+     * @param m
+     *            a positive modulus
+     */
+    static BigInteger modInverseHars(BigInteger a, BigInteger m) {
+        // PRE: (a > 0) and (m > 0)
+        BigInteger u, v, r, s, temp;
+        // u = MAX(a,m), v = MIN(a,m)
+        if (a.compareTo(m) == BigInteger.LESS) {
+            u = m;
+            v = a;
+            r = BigInteger.ZERO;
+            s = BigInteger.ONE;
         } else {
-            while (bi.testBit(i))
-                i--;
-            return n - 1 - Math.max(i, bi.getLowestSetBit());
-        }
-        
-    }
-    
-    /**
-     *
-     * Based on "New Algorithm for Classical Modular Inverse" Róbert Lórencz.
-     * LNCS 2523 (2002)
-     *
-     * @return a^(-1) mod m
-     */
-    static BigInteger modInverseLorencz(BigInteger a, BigInteger modulo) {
-        // PRE: a is coprime with modulo, a < modulo
-        
-        int max = Math.max(a.numberLength, modulo.numberLength);
-        int uDigits[] = new int[max + 1]; // enough place to make all the inplace operation
-        int vDigits[] = new int[max + 1];
-        System.arraycopy(modulo.digits, 0, uDigits, 0, modulo.numberLength);
-        System.arraycopy(a.digits, 0, vDigits, 0, a.numberLength);
-        BigInteger u = new BigInteger(modulo.sign, modulo.numberLength,
-                uDigits);
-        BigInteger v = new BigInteger(a.sign, a.numberLength, vDigits);
-        
-        BigInteger r = new BigInteger(0, 1, new int[max + 1]); // BigInteger.ZERO;
-        BigInteger s = new BigInteger(1, 1, new int[max + 1]);
-        s.digits[0] = 1;
-        // r == 0 && s == 1, but with enough place
-        
-        int coefU = 0, coefV = 0;
-        int n = modulo.bitLength();
-        int k;
-        while (!isPowerOfTwo(u, coefU) && !isPowerOfTwo(v, coefV)) {
-            
-            // modification of original algorithm: I calculate how many times the algorithm
will enter in the same branch of if
-            k = howManyIterations(u, n);
-            
-            if (k != 0) {
-                BitLevel.inplaceShiftLeft(u, k);
-                if (coefU >= coefV) {
-                    BitLevel.inplaceShiftLeft(r, k);
-                } else {
-                    BitLevel.inplaceShiftRight(s, Math.min(coefV - coefU, k));
-                    if (k - ( coefV - coefU ) > 0) {
-                        BitLevel.inplaceShiftLeft(r, k - coefV + coefU);
-                    }
-                }
-                coefU += k;
-            }
-            
-            k = howManyIterations(v, n);
-            if (k != 0) {
-                BitLevel.inplaceShiftLeft(v, k);
-                if (coefV >= coefU) {
-                    BitLevel.inplaceShiftLeft(s, k);
-                } else {
-                    BitLevel.inplaceShiftRight(r, Math.min(coefU - coefV, k));
-                    if (k - ( coefU - coefV ) > 0) {
-                        BitLevel.inplaceShiftLeft(s, k - coefU + coefV);
-                    }
-                }
-                coefV += k;
-                
-            }
-            
-            if (u.signum() == v.signum()) {
-                if (coefU <= coefV) {
-                    Elementary.completeInPlaceSubtract(u, v);
-                    Elementary.completeInPlaceSubtract(r, s);
-                } else {
-                    Elementary.completeInPlaceSubtract(v, u);
-                    Elementary.completeInPlaceSubtract(s, r);
-                }
-            } else {
-                if (coefU <= coefV) {
-                    Elementary.completeInPlaceAdd(u, v);
-                    Elementary.completeInPlaceAdd(r, s);
-                } else {
-                    Elementary.completeInPlaceAdd(v, u);
-                    Elementary.completeInPlaceAdd(s, r);
-                }
-            }
-            if (v.signum() == 0 || u.signum() == 0){
-                // math.19: BigInteger not invertible
-                throw new ArithmeticException(Messages.getString("math.19"));
-            }
-        }
-        
-        if (isPowerOfTwo(v, coefV)) {
-            r = s;
-            if (v.signum() != u.signum())
-                u = u.negate();
-        }
-        if (u.testBit(n)) {
-            if (r.signum() < 0) {
-                r = r.negate();
+            v = m;
+            u = a;
+            s = BigInteger.ZERO;
+            r = BigInteger.ONE;
+        }
+        int uLen = u.bitLength();
+        int vLen = v.bitLength();
+        int f = uLen - vLen;
+
+        while (vLen > 1) {
+            if (u.sign == v.sign) {
+                u = u.subtract(v.shiftLeft(f));
+                r = r.subtract(s.shiftLeft(f));
             } else {
-                r = modulo.subtract(r);
+                u = u.add(v.shiftLeft(f));
+                r = r.add(s.shiftLeft(f));
             }
+            uLen = u.abs().bitLength();
+            vLen = v.abs().bitLength();
+            f = uLen - vLen;
+            if (f < 0) {
+                // SWAP(u,v)
+                temp = u;
+                u = v;
+                v = temp;
+                // SWAP(r,s)
+                temp = r;
+                r = s;
+                s = temp;
+
+                f = -f;
+                vLen = uLen;
+            }
+        }
+        if (v.sign == 0) {
+            return BigInteger.ZERO;
+        }
+        if (v.sign < 0) {
+            s = s.negate();
         }
-        if (r.signum() < 0) {
-            r = r.add(modulo);
+        if (s.compareTo(m) == BigInteger.GREATER) {
+            return s.subtract(m);
         }
-        
-        return r;
-    }
-    
-    static BigInteger squareAndMultiply(BigInteger x2, BigInteger a2, BigInteger exponent,BigInteger
modulus, int n2  ){
-        BigInteger res = x2;
-        for (int i = exponent.bitLength() - 1; i >= 0; i--) {
-            res = monPro(res,res,modulus, n2);
-            if (BitLevel.testBit(exponent, i)) {
-                res = monPro(res, a2, modulus, n2);
-            }
+        if (s.sign < 0) {
+            return s.add(m);
         }
-        return res;
+        return s; // a^(-1) mod m
     }
-    
+
     /*Implements the Montgomery modular exponentiation based in <i>The sliding windows
algorithm and the Mongomery
      *Reduction</i>.
      *@ar.org.fitc.ref "A. Menezes,P. van Oorschot, S. Vanstone - Handbook of Applied Cryptography";



Mime
View raw message