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

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

fix in msieve class

File size: 5.2 KB
RevLine 
[1817]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        {
[1820]124            //Check if factor already in factorlist:
125            foreach (Factor f in factorlist)
126                if (f.factor == factor)
127                    return;
128
129            //Add to factorlist:
[1817]130            int count = 0;
131            while (currentNumber % factor == 0)
132            {
133                count++;
134                currentNumber /= factor;
135            }
136            Debug.Assert(count != 0);
137            factorlist.Add(new Factor(factor, prime, count));
138        }
139
140        #endregion
141
142    }
143}
Note: See TracBrowser for help on using the repository browser.