Changeset 1454


Ignore:
Timestamp:
May 20, 2010, 11:58:29 PM (12 years ago)
Author:
Sven Rech
Message:

added ModInverse operation for BigIntegerHelper class

File:
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/CrypPluginBase/Miscellaneous/BigIntegerHelper.cs

    r1448 r1454  
    1 using System;
     1/*
     2   Copyright 2010 Sven Rech (svenrech at cryptool dot org), University of Duisburg-Essen
     3
     4   Licensed under the Apache License, Version 2.0 (the "License");
     5   you may not use this file except in compliance with the License.
     6   You may obtain a copy of the License at
     7
     8       http://www.apache.org/licenses/LICENSE-2.0
     9
     10   Unless required by applicable law or agreed to in writing, software
     11   distributed under the License is distributed on an "AS IS" BASIS,
     12   WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13   See the License for the specific language governing permissions and
     14   limitations under the License.
     15*/
     16
     17/*
     18 * This class provides some additional functionality for the BigInteger class.
     19 * The parser stuff is written by Sven Rech and Nils Kopal.
     20 */
     21
     22using System;
    223using System.Collections.Generic;
    324using System.Linq;
     
    175196        }
    176197
    177         public static BigInteger ModInverse(BigInteger Input1, BigInteger Mod)
    178         {
    179             throw new NotImplementedException();
    180         }
    181 
     198        /*
     199         * Returns the modulo inverse of this.  Throws ArithmeticException if
     200         * the inverse does not exist.  (i.e. gcd(this, modulus) != 1)
     201         *
     202         * This method is taken from the BigInteger class of
     203         * Chew Keong TAN (source: http://www.codeproject.com/KB/cs/biginteger.aspx)
     204         * (but modified by us)
     205        */
     206
     207        public static BigInteger ModInverse(BigInteger input, BigInteger modulus)
     208        {
     209            BigInteger[] p = { 0, 1 };
     210            BigInteger[] q = new BigInteger[2];    // quotients
     211            BigInteger[] r = { 0, 0 };             // remainders
     212
     213            int step = 0;
     214
     215            BigInteger a = modulus;
     216            BigInteger b = input;
     217
     218            while (b != 0)
     219            {
     220                BigInteger quotient;
     221                BigInteger remainder;
     222
     223                if (step > 1)
     224                {
     225                    BigInteger pval = (p[0] - (p[1] * q[0])) % modulus;
     226                    p[0] = p[1];
     227                    p[1] = pval;
     228                }
     229
     230                quotient = BigInteger.DivRem(a, b, out remainder);
     231
     232                q[0] = q[1];
     233                r[0] = r[1];
     234                q[1] = quotient; r[1] = remainder;
     235
     236                a = b;
     237                b = remainder;
     238
     239                step++;
     240            }
     241
     242            if ((r[0] != 1 && r[0] != 0))
     243                throw (new ArithmeticException("No inverse!"));
     244
     245            BigInteger result = ((p[0] - (p[1] * q[0])) % modulus);
     246
     247            while (result < 0)
     248                result += modulus;  // get the least positive modulus
     249
     250            return result;
     251        }
     252
     253       
    182254        public static bool isProbablePrime(BigInteger p)
    183255        {
     256            return true;    //TODO: Implement this!!
    184257            throw new NotImplementedException();
    185258        }
Note: See TracChangeset for help on using the changeset viewer.