source: trunk/CrypPluginBase/Miscellaneous/BigIntegerHelper.cs @ 1454

Last change on this file since 1454 was 1454, checked in by Sven Rech, 12 years ago

added ModInverse operation for BigIntegerHelper class

File size: 9.0 KB
Line 
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;
23using System.Collections.Generic;
24using System.Linq;
25using System.Text;
26using System.Numerics;
27
28namespace Cryptool.PluginBase.Miscellaneous
29{
30    public class BigIntegerHelper
31    {
32        #region internal stuff of expression parser
33
34        private struct TOKEN
35        {
36            public enum Ttype { MULTIPLY, DIVIDE, PLUS, MINUS, POW, BRACKETOPEN, BRACKETCLOSE, INTEGER };
37            public Ttype ttype;
38            public BigInteger integer;
39        }
40
41        private static Stack<TOKEN> scan(string expr)
42        {
43            TOKEN t = new TOKEN();
44            int startIndex = 0;
45            if (expr == "")
46                return new Stack<TOKEN>();
47            switch (expr[0])
48            {
49                case ' ':
50                    return scan(expr.Substring(1));
51                case '(':
52                    t.ttype = TOKEN.Ttype.BRACKETOPEN;
53                    startIndex = 1;
54                    break;
55                case ')':
56                    t.ttype = TOKEN.Ttype.BRACKETCLOSE;
57                    startIndex = 1;
58                    break;
59                case '+':
60                    t.ttype = TOKEN.Ttype.PLUS;
61                    startIndex = 1;
62                    break;
63                case '-':
64                    t.ttype = TOKEN.Ttype.MINUS;
65                    startIndex = 1;
66                    break;
67                case '*':
68                    t.ttype = TOKEN.Ttype.MULTIPLY;
69                    startIndex = 1;
70                    break;
71                case '/':
72                    t.ttype = TOKEN.Ttype.DIVIDE;
73                    startIndex = 1;
74                    break;
75                case '^':
76                    t.ttype = TOKEN.Ttype.POW;
77                    startIndex = 1;
78                    break;
79                case '0':
80                case '1':
81                case '2':
82                case '3':
83                case '4':
84                case '5':
85                case '6':
86                case '7':
87                case '8':
88                case '9':
89                    int length = 1;
90                    for (; length < expr.Length; length++)
91                        if (!(expr[length] >= '0' && expr[length] <= '9'))
92                            break;
93                    t.integer = BigInteger.Parse(expr.Substring(0, length));
94                    t.ttype = TOKEN.Ttype.INTEGER;
95                    startIndex = length;
96                    break;
97                default:
98                    throw new Exception("Expression parsing failed at character " + expr[0]);
99            }
100            Stack<TOKEN> st = scan(expr.Substring(startIndex));
101            st.Push(t);
102            return st;
103        }
104
105        private enum Priority { ALL, POW, MULTDIV, ADDSUB };
106
107        private static BigInteger parse(Stack<TOKEN> stack, Priority priority, bool endbracket)
108        {
109            if (stack.Count == 0)
110                throw new Exception("Expression Parsing Error.");
111            int minus = 1;
112            BigInteger v = 0;
113            TOKEN t = stack.Pop();  //get -, +, integer or bracket
114
115            if (t.ttype == TOKEN.Ttype.MINUS)
116            {
117                minus = -1;
118                t = stack.Pop();    //get integer or bracket
119            }
120            else if (t.ttype == TOKEN.Ttype.PLUS)
121            {
122                minus = 1;
123                t = stack.Pop();    //get integer or bracket
124            }
125
126            if (t.ttype == TOKEN.Ttype.INTEGER)
127            {
128                v = minus * t.integer;
129            }
130            else if (t.ttype == TOKEN.Ttype.BRACKETOPEN)
131            {
132                v = minus * parse(stack, Priority.ALL, true);
133                stack.Pop();    //pop the closing bracket
134            }
135
136            while (stack.Count != 0)
137            {
138                switch (stack.Peek().ttype) //next operator
139                {
140                    case TOKEN.Ttype.PLUS:
141                        if (priority == Priority.MULTDIV || priority == Priority.POW)
142                            return v;
143                        stack.Pop();
144                        v = v + parse(stack, Priority.ADDSUB, endbracket);
145                        break;
146                    case TOKEN.Ttype.MINUS:
147                        if (priority == Priority.MULTDIV || priority == Priority.POW)
148                            return v;
149                        stack.Pop();
150                        v = v - parse(stack, Priority.ADDSUB, endbracket);
151                        break;
152                    case TOKEN.Ttype.MULTIPLY:
153                        if (priority == Priority.POW)
154                            return v;
155                        stack.Pop();
156                        v = v * parse(stack, Priority.MULTDIV, endbracket);
157                        break;
158                    case TOKEN.Ttype.DIVIDE:
159                        if (priority == Priority.POW)
160                            return v;
161                        stack.Pop();
162                        v = v / parse(stack, Priority.MULTDIV, endbracket);
163                        break;
164                    case TOKEN.Ttype.POW:
165                        stack.Pop();
166                        v = BigInteger.Pow(v, (int)parse(stack, Priority.POW, endbracket));
167                        break;
168                    case TOKEN.Ttype.BRACKETCLOSE:
169                        if (endbracket)
170                            return v;
171                        else
172                            throw new Exception("Expression Parsing Error (closing bracket misplaced).");
173                    default:
174                        throw new Exception("Expression Parsing Error.");
175                }
176            }
177            if (endbracket)
178                throw new Exception("Expression Parsing Error (closing bracket missing).");
179
180            return v;
181        }
182
183        #endregion
184
185        /*         
186         * Parses a math expression (example: (2+2)^(17-5) )
187         * and returns a BigInteger based on this expression
188         *
189         * throws an exception when expression is not valid or the Number gets too big
190         */
191        public static BigInteger parseExpression(string expr)
192        {
193            Stack<TOKEN> stack = scan(expr);
194            BigInteger i = parse(stack, Priority.ALL, false);
195            return i;
196        }
197
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       
254        public static bool isProbablePrime(BigInteger p)
255        {
256            return true;    //TODO: Implement this!!
257            throw new NotImplementedException();
258        }
259    }
260}
Note: See TracBrowser for help on using the repository browser.