source: trunk/CrypPluginBase/Miscellaneous/Msieve.cs @ 1817

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

added Msieve class in CrypPluginBase.
This makes it possible for every plugin to use msieve functionality (i.e. fast factorization).
I will need this for the discrete logarithm plugin.

File size: 5.0 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Text;
5using System.Reflection;
6using System.IO;
7using Cryptool.PluginBase.IO;
8using System.Numerics;
9using System.Threading;
10using System.Collections;
11using System.Diagnostics;
12
13namespace Cryptool.PluginBase.Miscellaneous
14{
15    /// <summary>
16    /// This class is responsible for loading the msieve dll and offers some functions
17    /// for factorizing.
18    /// </summary>
19    public class Msieve
20    {
21        private static Assembly msieveDLL = null;
22        private static Mutex msieveMutex = new Mutex();
23
24        /// <summary>
25        /// A single factor
26        /// </summary>
27        public struct Factor
28        {
29            public BigInteger factor;
30            public bool prime;
31            public int count;
32
33            public Factor(BigInteger factor, bool prime, int count)
34            {
35                this.factor = factor;
36                this.prime = prime;
37                this.count = count;
38            }
39        }
40
41        /// <summary>
42        /// This method is mainly a singleton.
43        /// </summary>
44        /// <returns>The (only) msieve assembly</returns>
45        public static Assembly GetMsieveDLL()
46        {
47            msieveMutex.WaitOne();
48
49            if (msieveDLL == null)
50            {
51                string s = Directory.GetCurrentDirectory();
52                string dllname;
53                if (IntPtr.Size == 4)
54                    dllname = "msieve.dll";
55                else
56                    dllname = "msieve64.dll";
57
58                msieveDLL = Assembly.LoadFile(DirectoryHelper.BaseDirectory + "\\AppReferences\\" + dllname);
59            }
60
61            msieveMutex.ReleaseMutex();
62
63            return msieveDLL;
64        }
65
66        /// <summary>
67        /// This method factorizes the parameter "number" by using the "trivial" (i.e. very fast) methods that are available in msieve.
68        /// This means, that the factorization doesn't take very long, but on the other hand, you can end up having some
69        /// composite factors left, because they can't be factorized efficiently.
70        /// </summary>
71        /// <param name="number">the number to factorize</param>
72        /// <returns>A list of factors</returns>
73        public static List<Factor> TrivialFactorization(BigInteger number)
74        {
75            msieveMutex.WaitOne();
76
77            Type msieve = GetMsieveDLL().GetType("Msieve.msieve");
78
79            //init msieve with callbacks:
80            MethodInfo initMsieve = msieve.GetMethod("initMsieve");
81            Object callback_struct = Activator.CreateInstance(msieveDLL.GetType("Msieve.callback_struct"));
82            FieldInfo putTrivialFactorlistField = msieveDLL.GetType("Msieve.callback_struct").GetField("putTrivialFactorlist");
83            BindingFlags flags = BindingFlags.NonPublic | BindingFlags.Static;
84            MethodInfo putTrivialFactorlistMethodInfo = typeof(Msieve).GetMethod("putTrivialFactorlist", flags);
85            Delegate putTrivialFactorlistDel = MulticastDelegate.CreateDelegate(msieveDLL.GetType("Msieve.putTrivialFactorlistDelegate"), putTrivialFactorlistMethodInfo);
86            putTrivialFactorlistField.SetValue(callback_struct, putTrivialFactorlistDel);
87            initMsieve.Invoke(null, new object[1] { callback_struct });
88
89            //start msieve:
90            currentNumber = number;
91            MethodInfo start = msieve.GetMethod("start");
92            start.Invoke(null, new object[] { number.ToString(), null });
93
94            msieveMutex.ReleaseMutex();
95            return factorlist;
96        }
97
98        #region private
99
100        private static List<Factor> factorlist;
101        private static BigInteger currentNumber;
102
103        private static void putTrivialFactorlist(IntPtr list, IntPtr obj)
104        {
105            factorlist = new List<Factor>();
106           
107            Type msieve = GetMsieveDLL().GetType("Msieve.msieve");
108            MethodInfo getPrimeFactorsMethod = msieve.GetMethod("getPrimeFactors");
109            MethodInfo getCompositeFactorsMethod = msieve.GetMethod("getCompositeFactors");
110
111            ArrayList pf = (ArrayList)(getPrimeFactorsMethod.Invoke(null, new object[] { list }));
112            foreach (Object o in pf)
113                AddToFactorlist(BigInteger.Parse((string)o), true);
114
115            ArrayList cf = (ArrayList)(getCompositeFactorsMethod.Invoke(null, new object[] { list }));
116            foreach (Object o in cf)
117                AddToFactorlist(BigInteger.Parse((string)o), false);
118
119            Debug.Assert(currentNumber == 1);
120        }
121
122        private static void AddToFactorlist(BigInteger factor, bool prime)
123        {
124            int count = 0;
125            while (currentNumber % factor == 0)
126            {
127                count++;
128                currentNumber /= factor;
129            }
130            Debug.Assert(count != 0);
131            factorlist.Add(new Factor(factor, prime, count));
132        }
133
134        #endregion
135
136    }
137}
Note: See TracBrowser for help on using the repository browser.