source: trunk/CrypPluginBase/Miscellaneous/Msieve.cs

Last change on this file was 8983, checked in by kopal, 7 months ago

Complete CrypTool 2 project

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