source: trunk/CrypPlugins/QuadraticSieve/QuadraticSieve.cs @ 1503

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

fixed quadratic sieve settings

File size: 25.9 KB
Line 
1/*                             
2   Copyright 2009 Team CrypTool (Sven Rech,Dennis Nolte,Raoul Falk,Nils Kopal), Uni 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
17using System;
18using System.Collections;
19using System.Linq;
20using System.Text;
21using Cryptool.PluginBase;
22using Cryptool.PluginBase.IO;
23using QuadraticSieve;
24using Cryptool.PluginBase.Miscellaneous;
25using System.ComponentModel;
26using System.Threading;
27using System.IO;
28using System.Windows.Controls;
29using System.Windows.Threading;
30using System.Windows;
31using System.Reflection;
32using System.Numerics;
33using System.Collections.Generic;
34using System.Diagnostics;
35
36namespace Cryptool.Plugins.QuadraticSieve
37{
38    /// <summary>
39    /// This class wraps the msieve algorithm in version 1.42 which you can find at http://www.boo.net/~jasonp/qs.html
40    /// It also extends the msieve functionality to multi threading
41    /// Many thanks to the author of msieve "jasonp_sf"
42    ///
43    /// For further information on quadratic sieve or msieve please have a look at the above mentioned URL
44    /// </summary>
45    [Author("Sven Rech", "rech@cryptool.org", "Uni Duisburg-Essen", "http://www.uni-due.de")]
46    [PluginInfo(false, "Quadratic Sieve", "Sieving Primes", "QuadraticSieve/DetailedDescription/Description.xaml", "QuadraticSieve/iconqs.png")]
47    class QuadraticSieve : DependencyObject, IThroughput
48    {
49        #region private variables
50
51        private readonly string directoryName;
52        private QuadraticSieveSettings settings = new QuadraticSieveSettings();
53        private BigInteger inputNumber;
54        private BigInteger[] outputFactors;
55        private bool running;
56        private Queue yieldqueue;
57        private AutoResetEvent yieldEvent = new AutoResetEvent(false);
58        private IntPtr obj = IntPtr.Zero;
59        private volatile int threadcount = 0;
60        private ArrayList conf_list;
61        private bool userStopped = false;
62        private FactorManager factorManager;
63        private PeerToPeer peerToPeer = new PeerToPeer();
64        private BigInteger sumSize = 0;
65
66        private static Assembly msieveDLL = null;
67        private static Type msieve = null;
68
69        #endregion
70
71        #region events
72
73        public event StatusChangedEventHandler OnPluginStatusChanged;
74        public event GuiLogNotificationEventHandler OnGuiLogNotificationOccured;
75        public event PluginProgressChangedEventHandler OnPluginProgressChanged;
76        public event System.ComponentModel.PropertyChangedEventHandler PropertyChanged;
77        public event PluginProgressChangedEventHandler OnPluginProcessChanged;       
78
79        #endregion
80
81        #region public
82
83        /// <summary>
84        /// Constructor
85        ///
86        /// constructs a new QuadraticSieve plugin
87        /// </summary>
88        public QuadraticSieve()
89        {
90            directoryName = Path.Combine(DirectoryHelper.DirectoryLocalTemp, "msieve");
91            if (!Directory.Exists(directoryName)) Directory.CreateDirectory(directoryName);
92
93            QuickWatchPresentation = new QuadraticSievePresentation();
94           
95            quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
96            {
97                quadraticSieveQuickWatchPresentation.timeLeft.Text = "?";
98                quadraticSieveQuickWatchPresentation.endTime.Text = "?";
99                quadraticSieveQuickWatchPresentation.logging.Text = "Currently not sieving.";
100            }
101            , null);
102        }               
103
104        /// <summary>
105        /// Getter / Setter for the settings of this plugin
106        /// </summary>
107        public Cryptool.PluginBase.ISettings Settings
108        {
109            get { return this.settings; }
110            set { this.settings = (QuadraticSieveSettings)value; } 
111        }           
112
113        /// <summary>
114        /// Called by the environment before executing this plugin
115        /// </summary>
116        public void PreExecution()
117        { 
118        }
119       
120        /// <summary>
121        /// Called by the environment to execute this plugin
122        /// </summary>
123        public void Execute()
124        {
125            sumSize = 0;
126            userStopped = false;
127
128            if (InputNumber != 0)
129            {
130                if (InputNumber.ToString().Length >= 275)
131                {
132                    GuiLogMessage("Input too big.", NotificationLevel.Error);
133                    return;
134                }
135
136                String timeLeft_message = "?";
137                String endtime_message = "?";
138                String logging_message = "Starting quadratic sieve, please wait!";
139
140                GuiLogMessage(logging_message, NotificationLevel.Info);
141                quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
142                {
143                    quadraticSieveQuickWatchPresentation.logging.Text = logging_message;
144                    quadraticSieveQuickWatchPresentation.endTime.Text = endtime_message;
145                    quadraticSieveQuickWatchPresentation.timeLeft.Text = timeLeft_message;
146                    quadraticSieveQuickWatchPresentation.factorList.Items.Clear();
147                    quadraticSieveQuickWatchPresentation.factorInfo.Content = "Searching trivial factors!";                   
148                }
149                , null);   
150
151                DateTime start_time = DateTime.Now;
152
153                initMsieveDLL();
154                factorManager = new FactorManager(msieve.GetMethod("getPrimeFactors"), msieve.GetMethod("getCompositeFactors"));
155                factorManager.FactorsChanged += this.FactorsChanged;
156
157                //Now factorize:               
158                try
159                {
160                    string file = Path.Combine(directoryName, "" + InputNumber + ".dat");
161                    if (settings.DeleteCache && File.Exists(file))
162                        File.Delete(file);
163                    MethodInfo start = msieve.GetMethod("start");
164                    start.Invoke(null, new object[] { InputNumber.ToString(), file });
165                    obj = IntPtr.Zero;
166                }
167                catch (Exception ex)
168                {
169                    GuiLogMessage("Error using msieve. " + ex.Message, NotificationLevel.Error);
170                    stopThreads();
171                    return;
172                }
173
174                if (!userStopped)
175                {
176                    timeLeft_message = "0 seconds left";
177                    endtime_message = "" + (DateTime.Now);
178                    logging_message = "Sieving finished in " + (DateTime.Now - start_time) + "!";
179
180                    GuiLogMessage(logging_message, NotificationLevel.Info);
181                    quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
182                    {
183                        quadraticSieveQuickWatchPresentation.logging.Text = logging_message;
184                        quadraticSieveQuickWatchPresentation.endTime.Text = endtime_message;
185                        quadraticSieveQuickWatchPresentation.timeLeft.Text = timeLeft_message;
186                        quadraticSieveQuickWatchPresentation.factorInfo.Content = "";
187                    }
188                    , null);
189
190                    Debug.Assert(factorManager.CalculateNumber() == InputNumber);
191                    OutputFactors = factorManager.getPrimeFactors();
192                }
193                else
194                {
195                    timeLeft_message = "0 sec left";
196                    endtime_message = "Stopped";
197                    logging_message = "Stopped by user!";
198
199                    GuiLogMessage(logging_message, NotificationLevel.Info);
200                    quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
201                    {
202                        quadraticSieveQuickWatchPresentation.logging.Text = logging_message;
203                        quadraticSieveQuickWatchPresentation.endTime.Text = endtime_message;
204                        quadraticSieveQuickWatchPresentation.timeLeft.Text = timeLeft_message;
205                        quadraticSieveQuickWatchPresentation.factorInfo.Content = "";
206                    }
207                    , null);
208                }
209                   
210                ProgressChanged(1, 1);
211               
212            }
213        }
214       
215        /// <summary>
216        /// Called by the environment after execution
217        /// </summary>
218        public void PostExecution()
219        {
220        }
221
222        /// <summary>
223        /// Called by the environment to pause execution
224        /// </summary>
225        public void Pause()
226        {
227        }
228
229        /// <summary>
230        /// Called by the environment to stop execution
231        /// </summary>
232        public void Stop()
233        {
234            this.userStopped = true;
235            if (obj != IntPtr.Zero)
236            {
237                stopThreads();
238                MethodInfo stop = msieve.GetMethod("stop");
239                stop.Invoke(null, new object[] { obj });
240            }
241
242        }
243
244        /// <summary>
245        /// Called by the environment to initialize this plugin
246        /// </summary>
247        public void Initialize()
248        {
249            settings.Initialize();
250        }
251
252        /// <summary>
253        /// Called by the environment to dispose this plugin
254        /// </summary>
255        public void Dispose()
256        {
257        }
258
259        /// <summary>
260        /// Getter / Setter for the input number which should be factorized
261        /// </summary>
262        [PropertyInfo(Direction.InputData, "Number input", "Enter the number you want to factorize", "", DisplayLevel.Beginner)]
263        public BigInteger InputNumber
264        {
265            get
266            {
267                return inputNumber;
268            }
269            set
270            {
271                this.inputNumber = value;
272                OnPropertyChanged("InputNumber");
273            }
274        }
275
276        /// <summary>
277        /// Getter / Setter for the factors calculated by msieve
278        /// </summary>
279        [PropertyInfo(Direction.OutputData, "Factors output", "Your factors will be sent here", "", DisplayLevel.Beginner)]
280        public BigInteger[] OutputFactors
281        {
282            get
283            {
284                return outputFactors;
285            }
286            set
287            {
288                this.outputFactors = value;
289                OnPropertyChanged("OutputFactors");
290            }
291        }
292       
293        /// <summary>
294        /// Called when a property of this plugin changes
295        /// </summary>
296        /// <param name="name">name</param>
297        public void OnPropertyChanged(string name)
298        {
299            EventsHelper.PropertyChanged(PropertyChanged, this, new PropertyChangedEventArgs(name));
300        }
301
302        /// <summary>
303        /// Getter / Setter for the presentation of this plugin
304        /// </summary>
305        public UserControl Presentation { get; private set; }
306
307        /// <summary>
308        /// Getter / Setter for the QuickWatchPresentation of this plugin
309        /// </summary>
310        public UserControl QuickWatchPresentation
311        {
312            get;
313            private set;
314        }
315
316        #endregion
317
318        #region private
319
320        /// <summary>
321        /// calculate a String which shows the timespan
322        ///
323        /// example
324        ///
325        ///     4 days
326        /// or
327        ///     2 minutes
328        /// </summary>
329        /// <param name="ts"></param>
330        /// <returns></returns>
331        private String showTimeSpan(TimeSpan ts)
332        {
333            String res = "";
334            if (ts.Days != 0)
335                res = ts.Days + " days ";
336            if (ts.Hours != 0 || res.Length != 0)
337                res += ts.Hours + " hours ";
338            if (ts.Minutes != 0)
339                res += ts.Minutes + " minutes";
340            if (res.Length == 0)
341                res += ts.Seconds + " seconds";
342            return res;
343        }
344
345        /// <summary>
346        /// Callback method to prepare sieving
347        /// Called by msieve
348        ///
349        /// </summary>
350        /// <param name="conf">pointer to configuration</param>
351        /// <param name="update">number of relations found</param>
352        /// <param name="core_sieve_fcn">pointer to internal sieve function of msieve</param>
353        private void prepareSieving(IntPtr conf, int update, IntPtr core_sieve_fcn, int max_relations)
354        {
355            int threads = Math.Min(settings.CoresUsed, Environment.ProcessorCount-1);
356            MethodInfo getObjFromConf = msieve.GetMethod("getObjFromConf");
357            this.obj = (IntPtr)getObjFromConf.Invoke(null, new object[] { conf });           
358            yieldqueue = Queue.Synchronized(new Queue());
359            conf_list = new ArrayList();
360
361            String message = "Start sieving using " + (threads + 1) + " cores!";
362            GuiLogMessage(message, NotificationLevel.Info);
363            quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
364            {
365                quadraticSieveQuickWatchPresentation.logging.Text = message;
366            }
367            , null);         
368
369            ProgressChanged(0.1, 1.0);
370
371            running = true;
372            //start helper threads:
373            for (int i = 0; i < threads+1; i++)
374            {
375                MethodInfo cloneSieveConf = msieve.GetMethod("cloneSieveConf");
376                IntPtr clone = (IntPtr)cloneSieveConf.Invoke(null, new object[] { conf });               
377                conf_list.Add(clone);
378                WaitCallback worker = new WaitCallback(MSieveJob);
379                ThreadPool.QueueUserWorkItem(worker, new object[] { clone, update, core_sieve_fcn, yieldqueue });
380            }
381
382            //manage the yields of the other threads:
383            manageYields(conf, max_relations);  //this method returns as soon as there are enough relations found
384            if (userStopped)
385                return;
386
387            //sieving is finished now, so give some informations and stop threads:
388            GuiLogMessage("Data size: " + (sumSize / 1024) / 1024 + " MB!", NotificationLevel.Debug);
389            ProgressChanged(0.9, 1.0);
390            GuiLogMessage("Sieving finished", NotificationLevel.Info);
391            quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
392            {
393                quadraticSieveQuickWatchPresentation.factorInfo.Content = "Found enough relations! Please wait...";
394            }, null);
395            stopThreads();
396            if (yieldqueue != null)
397                yieldqueue.Clear();
398        }
399
400        private void manageYields(IntPtr conf, int max_relations)
401        {
402            MethodInfo serializeYield = msieve.GetMethod("serializeYield");
403            MethodInfo getNumRelations = msieve.GetMethod("getNumRelations");
404            int num_relations = (int)getNumRelations.Invoke(null, new object[] { conf });
405            int start_relations = num_relations;
406            DateTime start_sieving_time = DateTime.Now;
407            MethodInfo saveYield = msieve.GetMethod("saveYield");
408
409            while (num_relations < max_relations)
410            {
411                ProgressChanged((double)num_relations / max_relations * 0.8 + 0.1, 1.0);
412               
413                yieldEvent.WaitOne();               //wait until queue is not empty
414                if (userStopped)
415                    return;
416                while (yieldqueue.Count != 0)       //get all the results from the helper threads, and store them
417                {
418                    IntPtr yield = (IntPtr)yieldqueue.Dequeue();
419                    byte[] serializedYield = (byte[])serializeYield.Invoke(null, new object[] { yield });                   
420
421                    int compressedSize = peerToPeer.put(serializedYield);
422                    sumSize += compressedSize;
423
424                    saveYield.Invoke(null, new object[] { conf, yield });
425                }
426                num_relations = (int)getNumRelations.Invoke(null, new object[] { conf });
427                showProgressPresentation(max_relations, num_relations, start_relations, start_sieving_time);
428            }           
429        }
430
431        private void showProgressPresentation(int max_relations, int num_relations, int start_relations, DateTime start_sieving_time)
432        {
433            TimeSpan diff = DateTime.Now - start_sieving_time;
434            double msleft = (diff.TotalMilliseconds / (num_relations - start_relations)) * (max_relations - num_relations);
435            if (msleft > 0)
436            {
437                TimeSpan ts = new TimeSpan(0, 0, 0, 0, (int)msleft);
438                String logging_message = "Found " + num_relations + " of " + max_relations + " relations!";
439                String timeLeft_message = showTimeSpan(ts) + " left";
440                String endtime_message = "" + DateTime.Now.AddMilliseconds((long)msleft);
441
442                GuiLogMessage(logging_message + " " + timeLeft_message + ".", NotificationLevel.Debug);
443                quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
444                {
445                    quadraticSieveQuickWatchPresentation.logging.Text = logging_message;
446                    quadraticSieveQuickWatchPresentation.timeLeft.Text = timeLeft_message;
447                    quadraticSieveQuickWatchPresentation.endTime.Text = endtime_message;
448                }
449                , null);
450            }
451        }
452
453        /// <summary>
454        /// This callback method is called by msieve. "list" is the trivial factor list (i.e. it consists of the factors that have been found without
455        /// using the quadratic sieve algorithm).
456        /// The method then factors all the factors that are still composite by using the quadratic sieve.
457        /// </summary>
458        private void getTrivialFactorlist(IntPtr list, IntPtr obj)
459        {
460            //add the trivial factors to the factor list:
461            factorManager.AddFactors(list);
462
463            MethodInfo msieve_run_core = msieve.GetMethod("msieve_run_core");
464
465            //Now factorize as often as needed:
466            while (!factorManager.OnlyPrimes())
467            {
468                //get one composite factor, which we want to sieve now:
469                BigInteger compositeFactor = factorManager.GetCompositeFactor();
470                quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
471                {
472                    quadraticSieveQuickWatchPresentation.factorInfo.Content = "Now sieving first composite factor!";
473                }, null);
474
475                //now start quadratic sieve on it:               
476                IntPtr resultList = (IntPtr)msieve_run_core.Invoke(null, new object[2] { obj, compositeFactor.ToString() });
477                if (userStopped)
478                    return;
479                factorManager.ReplaceCompositeByFactors(compositeFactor, resultList);
480            }
481        }
482
483        /// <summary>
484        /// Helper Thread for msieve, which sieves for relations:
485        /// </summary>
486        /// <param name="param">params</param>
487        private void MSieveJob(object param)
488        {
489            threadcount++;
490            object[] parameters = (object[])param;
491            IntPtr clone = (IntPtr)parameters[0];
492            int update = (int)parameters[1];
493            IntPtr core_sieve_fcn = (IntPtr)parameters[2];
494            Queue yieldqueue = (Queue)parameters[3];
495
496            while (running)
497            {
498                try
499                {
500                    MethodInfo collectRelations = msieve.GetMethod("collectRelations");
501                    collectRelations.Invoke(null, new object[] { clone, update, core_sieve_fcn });
502                    MethodInfo getYield = msieve.GetMethod("getYield");
503                    IntPtr yield = (IntPtr)getYield.Invoke(null, new object[] { clone });
504
505                    yieldqueue.Enqueue(yield);
506                    yieldEvent.Set();
507                }
508                catch (Exception ex)
509                {
510                    GuiLogMessage("Error using msieve." + ex.Message, NotificationLevel.Error);
511                    threadcount = 0;
512                    return;
513                }               
514            }
515
516            MethodInfo freeSieveConf = msieve.GetMethod("freeSieveConf");
517            freeSieveConf.Invoke(null, new object[] { clone });           
518            threadcount--;
519        }       
520
521        /// <summary>
522        /// Stop all running threads
523        /// </summary>
524        private void stopThreads()
525        {
526            if (conf_list != null)
527            {
528                running = false;
529                MethodInfo stop = msieve.GetMethod("stop");
530                MethodInfo getObjFromConf = msieve.GetMethod("getObjFromConf");
531                foreach (IntPtr conf in conf_list)
532                    stop.Invoke(null, new object[] { getObjFromConf.Invoke(null, new object[] { conf }) });
533                GuiLogMessage("Waiting for threads to stop!", NotificationLevel.Debug);
534                while (threadcount > 0)
535                {
536                    Thread.Sleep(0);
537                }
538                GuiLogMessage("Threads stopped!", NotificationLevel.Debug);
539                conf_list.Clear();
540            }
541        }   
542
543        /// <summary>
544        /// Change the progress of this plugin
545        /// </summary>
546        /// <param name="value">value</param>
547        /// <param name="max">max</param>
548        private void ProgressChanged(double value, double max)
549        {
550            EventsHelper.ProgressChanged(OnPluginProgressChanged, this, new PluginProgressEventArgs(value, max));
551        }
552
553        private void FactorsChanged(List<BigInteger> primeFactors, List<BigInteger> compositeFactors)
554        {
555            quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
556            {
557                quadraticSieveQuickWatchPresentation.factorList.Items.Clear();
558
559                foreach (BigInteger pf in primeFactors)         
560                    quadraticSieveQuickWatchPresentation.factorList.Items.Add("Prime Factor: " + pf.ToString());           
561
562                foreach (BigInteger cf in compositeFactors)
563                    quadraticSieveQuickWatchPresentation.factorList.Items.Add("Composite Factor: " + cf.ToString());
564            }, null);
565        }
566
567        /// <summary>
568        /// Logs a message to the CrypTool gui
569        /// </summary>
570        /// <param name="p">p</param>
571        /// <param name="notificationLevel">notificationLevel</param>
572        private void GuiLogMessage(string p, NotificationLevel notificationLevel)
573        {
574            EventsHelper.GuiLogMessage(OnGuiLogNotificationOccured, this, new GuiLogEventArgs(p, this, notificationLevel));
575        }
576
577        /// <summary>
578        /// Getter / Setter for the QuickWatchPresentation
579        /// </summary>
580        private QuadraticSievePresentation quadraticSieveQuickWatchPresentation
581        {
582            get { return QuickWatchPresentation as QuadraticSievePresentation; }
583        }
584
585        /// <summary>
586        /// dynamically loads the msieve dll file and sets the callbacks
587        /// </summary>
588        private void initMsieveDLL()
589        {
590            //Load msieve.dll (if necessary):
591            if (msieve == null || msieveDLL == null)
592            {
593                string s = Directory.GetCurrentDirectory();
594                string dllname;
595                string relPath;
596                if (IntPtr.Size == 4)
597                {
598                    dllname = "msieve.dll";
599                    relPath = "x86";
600                }
601                else
602                {
603                    dllname = "msieve64.dll";
604                    relPath = "x64";
605                }
606                msieveDLL = Assembly.LoadFile(Directory.GetCurrentDirectory() + "\\AppReferences\\"  + relPath + "\\" + dllname);
607                msieve = msieveDLL.GetType("Msieve.msieve");
608            }
609
610            //init msieve with callbacks:
611            MethodInfo initMsieve = msieve.GetMethod("initMsieve");
612            Object callback_struct = Activator.CreateInstance(msieveDLL.GetType("Msieve.callback_struct"));           
613            FieldInfo prepareSievingField = msieveDLL.GetType("Msieve.callback_struct").GetField("prepareSieving");
614            FieldInfo getTrivialFactorlistField = msieveDLL.GetType("Msieve.callback_struct").GetField("getTrivialFactorlist");           
615            Delegate prepareSievingDel = MulticastDelegate.CreateDelegate(msieveDLL.GetType("Msieve.prepareSievingDelegate"), this, "prepareSieving");
616            Delegate getTrivialFactorlistDel = MulticastDelegate.CreateDelegate(msieveDLL.GetType("Msieve.getTrivialFactorlistDelegate"), this, "getTrivialFactorlist");           
617            prepareSievingField.SetValue(callback_struct, prepareSievingDel);
618            getTrivialFactorlistField.SetValue(callback_struct, getTrivialFactorlistDel);
619            initMsieve.Invoke(null, new object[1] { callback_struct });
620        }
621        #endregion
622
623    }
624}
Note: See TracBrowser for help on using the repository browser.