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

Last change on this file since 1818 was 1818, checked in by Sven Rech, 11 years ago

some renaming

File size: 13.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 "input".  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 written by
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            if (input == 1)
210                return 1;
211            if (input == 0)
212                throw (new ArithmeticException("No inverse!"));
213
214            BigInteger[] p = { 0, 1 };
215            BigInteger[] q = new BigInteger[2];    // quotients
216            BigInteger[] r = { 0, 0 };             // remainders
217
218            int step = 0;
219
220            BigInteger a = modulus;
221            BigInteger b = input;
222
223            while (b != 0)
224            {
225                BigInteger quotient;
226                BigInteger remainder;
227
228                if (step > 1)
229                {
230                    BigInteger pval = (p[0] - (p[1] * q[0])) % modulus;
231                    p[0] = p[1];
232                    p[1] = pval;
233                }
234
235                quotient = BigInteger.DivRem(a, b, out remainder);
236
237                q[0] = q[1];
238                r[0] = r[1];
239                q[1] = quotient; r[1] = remainder;
240
241                a = b;
242                b = remainder;
243
244                step++;
245            }
246
247            if ((r[0] != 1 && r[0] != 0))
248                throw (new ArithmeticException("No inverse!"));
249
250            BigInteger result = ((p[0] - (p[1] * q[0])) % modulus);
251
252            while (result < 0)
253                result += modulus;  // get the least positive modulus
254
255            return result;
256        }
257
258        #region primesBelow2000
259        // primes smaller than 2000 to test the generated prime number (taken from BigInteger class written by Chew Keong TAN)
260
261        private static readonly int[] primesBelow2000 = {
262            2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97,
263            101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199,
264            211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293,
265            307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397,
266            401, 409, 419, 421, 431, 433, 439, 443, 449, 457, 461, 463, 467, 479, 487, 491, 499,
267            503, 509, 521, 523, 541, 547, 557, 563, 569, 571, 577, 587, 593, 599,
268            601, 607, 613, 617, 619, 631, 641, 643, 647, 653, 659, 661, 673, 677, 683, 691,
269            701, 709, 719, 727, 733, 739, 743, 751, 757, 761, 769, 773, 787, 797,
270            809, 811, 821, 823, 827, 829, 839, 853, 857, 859, 863, 877, 881, 883, 887,
271            907, 911, 919, 929, 937, 941, 947, 953, 967, 971, 977, 983, 991, 997,
272            1009, 1013, 1019, 1021, 1031, 1033, 1039, 1049, 1051, 1061, 1063, 1069, 1087, 1091, 1093, 1097,
273            1103, 1109, 1117, 1123, 1129, 1151, 1153, 1163, 1171, 1181, 1187, 1193,
274            1201, 1213, 1217, 1223, 1229, 1231, 1237, 1249, 1259, 1277, 1279, 1283, 1289, 1291, 1297,
275            1301, 1303, 1307, 1319, 1321, 1327, 1361, 1367, 1373, 1381, 1399,
276            1409, 1423, 1427, 1429, 1433, 1439, 1447, 1451, 1453, 1459, 1471, 1481, 1483, 1487, 1489, 1493, 1499,
277            1511, 1523, 1531, 1543, 1549, 1553, 1559, 1567, 1571, 1579, 1583, 1597,
278            1601, 1607, 1609, 1613, 1619, 1621, 1627, 1637, 1657, 1663, 1667, 1669, 1693, 1697, 1699,
279            1709, 1721, 1723, 1733, 1741, 1747, 1753, 1759, 1777, 1783, 1787, 1789,
280            1801, 1811, 1823, 1831, 1847, 1861, 1867, 1871, 1873, 1877, 1879, 1889,
281            1901, 1907, 1913, 1931, 1933, 1949, 1951, 1973, 1979, 1987, 1993, 1997, 1999 };
282
283        #endregion
284
285        /*
286         * This code is heavily inspired by the code from the BigInteger class written by Chew Keong TAN
287         */
288        public static bool IsProbablePrime(BigInteger thisVal)
289        {
290            thisVal = BigInteger.Abs(thisVal);
291
292            //test small numbers
293            if (thisVal == 0 || thisVal == 1)
294                return false;
295            if (thisVal == 2 || thisVal == 3)
296                return true;           
297
298            if (thisVal.IsEven)     // even numbers
299                return false;
300
301            // test for divisibility by primes < 2000
302            for (int p = 0; p < primesBelow2000.Length; p++)
303            {
304                BigInteger divisor = primesBelow2000[p];
305
306                if (divisor >= thisVal)
307                    break;
308
309                BigInteger resultNum = thisVal % divisor;
310                if (resultNum == 0)               
311                    return false;               
312            }
313
314            // Perform BASE 2 Rabin-Miller Test
315
316            // calculate values of s and t
317            int s = 0;
318
319            BigInteger t = thisVal - 1;
320            while ((t & 0x01) == 0)     //TODO: This could be implemented more efficient
321            {
322                t = t >> 1;
323                s++;
324            }
325
326            BigInteger a = 2;
327
328            // b = a^t mod p
329            BigInteger b = BigInteger.ModPow(a, t, thisVal);
330            bool result = false;
331
332            if (b == 1)         // a^t mod p = 1
333                result = true;
334
335            BigInteger p_sub1 = thisVal - 1;
336            for (int j = 0; result == false && j < s; j++)
337            {
338                if (b == p_sub1)         // a^((2^j)*t) mod p = p-1 for some 0 <= j <= s-1
339                {
340                    result = true;
341                    break;
342                }
343
344                b = (b * b) % thisVal;
345            }
346
347            /*  TODO: Implement this:
348            // if number is strong pseudoprime to base 2, then do a strong lucas test
349            if (result)
350                result = LucasStrongTestHelper(thisVal);
351            */
352
353            return result;
354        }
355
356    }
357}
Note: See TracBrowser for help on using the repository browser.