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

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

some additional BigIntegerHelper stuff (added probable prime test)

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