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

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

some changes to quadratic sieve (doesn't work atm)

File size: 24.5 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 IntPtr obj = IntPtr.Zero;
58        private volatile int threadcount = 0;
59        private DateTime start_sieving_time;
60        private bool sieving_started;
61        private int start_relations;
62        private ArrayList conf_list;
63        private bool userStopped = false;
64        private FactorManager factorManager;
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            userStopped = false;
126
127            if (InputNumber != 0)
128            {
129                if (InputNumber.ToString().Length >= 275)
130                {
131                    GuiLogMessage("Input too big.", NotificationLevel.Error);
132                    return;
133                }
134
135                String timeLeft_message = "?";
136                String endtime_message = "?";
137                String logging_message = "Starting quadratic sieve, please wait!";
138
139                GuiLogMessage(logging_message, NotificationLevel.Info);
140                quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
141                {
142                    quadraticSieveQuickWatchPresentation.logging.Text = logging_message;
143                    quadraticSieveQuickWatchPresentation.endTime.Text = endtime_message;
144                    quadraticSieveQuickWatchPresentation.timeLeft.Text = timeLeft_message;
145                }
146                , null);   
147
148                DateTime start_time = DateTime.Now;
149
150                initMsieveDLL();
151                factorManager = new FactorManager(msieve.GetMethod("getPrimeFactors"), msieve.GetMethod("getCompositeFactors"));
152                factorManager.FactorsChanged += this.FactorsChanged;
153
154                //Now factorize:               
155                try
156                {
157                    string file = Path.Combine(directoryName, "" + InputNumber + ".dat");
158                    if (settings.DeleteCache && File.Exists(file))
159                        File.Delete(file);
160                    MethodInfo start = msieve.GetMethod("start");
161                    start.Invoke(null, new object[] { InputNumber.ToString(), file });
162                    obj = IntPtr.Zero;
163                }
164                catch (Exception ex)
165                {
166                    GuiLogMessage("Error using msieve. " + ex.Message, NotificationLevel.Error);
167                    stopThreads();
168                    return;
169                }
170
171                if (!userStopped)
172                {
173                    timeLeft_message = "0 seconds left";
174                    endtime_message = "" + (DateTime.Now);
175                    logging_message = "Sieving finished in " + (DateTime.Now - start_time) + "!";
176
177                    GuiLogMessage(logging_message, NotificationLevel.Info);
178                    quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
179                    {
180                        quadraticSieveQuickWatchPresentation.logging.Text = logging_message;
181                        quadraticSieveQuickWatchPresentation.endTime.Text = endtime_message;
182                        quadraticSieveQuickWatchPresentation.timeLeft.Text = timeLeft_message;
183                    }
184                    , null);
185
186                    Debug.Assert(factorManager.CalculateNumber() == InputNumber);
187                    OutputFactors = factorManager.getPrimeFactors();
188                }
189                else
190                {
191                    timeLeft_message = "0 sec left";
192                    endtime_message = "Stopped";
193                    logging_message = "Stopped by user!";
194
195                    GuiLogMessage(logging_message, NotificationLevel.Info);
196                    quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
197                    {
198                        quadraticSieveQuickWatchPresentation.logging.Text = logging_message;
199                        quadraticSieveQuickWatchPresentation.endTime.Text = endtime_message;
200                        quadraticSieveQuickWatchPresentation.timeLeft.Text = timeLeft_message;
201                    }
202                    , null);
203                }
204                   
205                ProgressChanged(1, 1);
206               
207            }
208        }
209       
210        /// <summary>
211        /// Called by the environment after execution
212        /// </summary>
213        public void PostExecution()
214        {
215        }
216
217        /// <summary>
218        /// Called by the environment to pause execution
219        /// </summary>
220        public void Pause()
221        {
222        }
223
224        /// <summary>
225        /// Called by the environment to stop execution
226        /// </summary>
227        public void Stop()
228        {
229            this.userStopped = true;
230            if (obj != IntPtr.Zero)
231            {
232                stopThreads();
233                MethodInfo stop = msieve.GetMethod("stop");
234                stop.Invoke(null, new object[] { obj });
235            }
236
237        }
238
239        /// <summary>
240        /// Called by the environment to initialize this plugin
241        /// </summary>
242        public void Initialize()
243        {
244        }
245
246        /// <summary>
247        /// Called by the environment to dispose this plugin
248        /// </summary>
249        public void Dispose()
250        {
251        }
252
253        /// <summary>
254        /// Getter / Setter for the input number which should be factorized
255        /// </summary>
256        [PropertyInfo(Direction.InputData, "Number input", "Enter the number you want to factorize", "", DisplayLevel.Beginner)]
257        public BigInteger InputNumber
258        {
259            get
260            {
261                return inputNumber;
262            }
263            set
264            {
265                this.inputNumber = value;
266                OnPropertyChanged("InputNumber");
267            }
268        }
269
270        /// <summary>
271        /// Getter / Setter for the factors calculated by msieve
272        /// </summary>
273        [PropertyInfo(Direction.OutputData, "Factors output", "Your factors will be sent here", "", DisplayLevel.Beginner)]
274        public BigInteger[] OutputFactors
275        {
276            get
277            {
278                return outputFactors;
279            }
280            set
281            {
282                this.outputFactors = value;
283                OnPropertyChanged("OutputFactors");
284            }
285        }
286       
287        /// <summary>
288        /// Called when a property of this plugin changes
289        /// </summary>
290        /// <param name="name">name</param>
291        public void OnPropertyChanged(string name)
292        {
293            EventsHelper.PropertyChanged(PropertyChanged, this, new PropertyChangedEventArgs(name));
294        }
295
296        /// <summary>
297        /// Getter / Setter for the presentation of this plugin
298        /// </summary>
299        public UserControl Presentation { get; private set; }
300
301        /// <summary>
302        /// Getter / Setter for the QuickWatchPresentation of this plugin
303        /// </summary>
304        public UserControl QuickWatchPresentation
305        {
306            get;
307            private set;
308        }
309
310        #endregion
311
312        #region private
313
314        /// <summary>
315        /// calculate a String which shows the timespan
316        ///
317        /// example
318        ///
319        ///     4 days
320        /// or
321        ///     2 minutes
322        /// </summary>
323        /// <param name="ts"></param>
324        /// <returns></returns>
325        private String showTimeSpan(TimeSpan ts)
326        {
327            String res = "";
328            if (ts.Days != 0)
329                res = ts.Days + " days ";
330            if (ts.Hours != 0 || res.Length != 0)
331                res += ts.Hours + " hours ";
332            if (ts.Minutes != 0)
333                res += ts.Minutes + " minutes";
334            if (res.Length == 0)
335                res += ts.Seconds + " seconds";
336            return res;
337        }   
338
339        /// <summary>
340        /// Actualize the progress of the current sieving process
341        /// </summary>
342        /// <param name="conf"></param>
343        /// <param name="num_relations"></param>
344        /// <param name="max_relations"></param>
345        private void showProgress(IntPtr conf, int num_relations, int max_relations)
346        {
347            if (num_relations == -1)    //sieving finished
348            {
349                ProgressChanged(0.9, 1.0);
350                GuiLogMessage("Sieving finished", NotificationLevel.Info);
351                stopThreads();
352                yieldqueue.Clear();
353            }
354            else
355            {
356                if (sieving_started)
357                {
358                    TimeSpan diff = DateTime.Now - start_sieving_time;
359                    double msleft = (diff.TotalMilliseconds / (num_relations - start_relations)) * (max_relations - num_relations);
360                    if (msleft > 0)
361                    {
362                        TimeSpan ts = new TimeSpan(0, 0, 0, 0, (int)msleft);
363                        String logging_message = "Found " + num_relations + " of " + max_relations + " relations!";
364                        String timeLeft_message = showTimeSpan(ts) + " left";
365                        String endtime_message = "" + DateTime.Now.AddMilliseconds((long)msleft);
366                       
367                        GuiLogMessage(logging_message + " " + timeLeft_message + ".", NotificationLevel.Debug);
368                        quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
369                        {
370                            quadraticSieveQuickWatchPresentation.logging.Text = logging_message;
371                            quadraticSieveQuickWatchPresentation.timeLeft.Text = timeLeft_message;
372                            quadraticSieveQuickWatchPresentation.endTime.Text = endtime_message;
373                        }
374                        , null);
375
376                    }
377                }
378
379                if (!sieving_started)
380                {
381                    MethodInfo getCurrentFactor = msieve.GetMethod("getCurrentFactor");
382                    //GuiLogMessage((String)(getCurrentFactor.Invoke(null, new object[] { conf })), NotificationLevel.Debug);
383
384                    start_relations = num_relations;
385                    start_sieving_time = DateTime.Now;
386                    sieving_started = true;
387                }
388
389                ProgressChanged((double)num_relations / max_relations * 0.8 + 0.1, 1.0);               
390
391                while (yieldqueue.Count != 0)       //get all the results from the helper threads, and store them
392                {
393                    MethodInfo saveYield = msieve.GetMethod("saveYield");
394                    saveYield.Invoke(null, new object[] { conf, (IntPtr)yieldqueue.Dequeue() });                   
395                }               
396            }
397        }
398
399        /// <summary>
400        /// Callback method to prepare sieving
401        /// Called by msieve
402        ///
403        /// </summary>
404        /// <param name="conf">pointer to configuration</param>
405        /// <param name="update">number of relations found</param>
406        /// <param name="core_sieve_fcn">pointer to internal sieve function of msieve</param>
407        private void prepareSieving (IntPtr conf, int update, IntPtr core_sieve_fcn)
408        {
409            int threads = Math.Min(settings.CoresUsed, Environment.ProcessorCount-1);
410            MethodInfo getObjFromConf = msieve.GetMethod("getObjFromConf");
411            this.obj = (IntPtr)getObjFromConf.Invoke(null, new object[] { conf });           
412            yieldqueue = Queue.Synchronized(new Queue());
413            sieving_started = false;
414            conf_list = new ArrayList();
415
416            String message = "Start sieving using " + (threads + 1) + " cores!";
417            GuiLogMessage(message, NotificationLevel.Info);
418            quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
419            {
420                quadraticSieveQuickWatchPresentation.logging.Text = message;
421            }
422            , null);         
423
424            ProgressChanged(0.1, 1.0);
425
426            running = true;
427            //start helper threads:
428            for (int i = 0; i < threads; i++)
429            {
430                MethodInfo cloneSieveConf = msieve.GetMethod("cloneSieveConf");
431                IntPtr clone = (IntPtr)cloneSieveConf.Invoke(null, new object[] { conf });               
432                conf_list.Add(clone);
433                WaitCallback worker = new WaitCallback(MSieveJob);
434                ThreadPool.QueueUserWorkItem(worker, new object[] { clone, update, core_sieve_fcn, yieldqueue });
435            }
436        }
437
438        /// <summary>
439        /// 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
440        /// using the quadratic sieve algorithm).
441        /// The method then factors all the factors that are still composite by using the quadratic sieve.
442        /// </summary>
443        private void getTrivialFactorlist(IntPtr list, IntPtr obj)
444        {
445            //add the trivial factors to the factor list:
446            factorManager.AddFactors(list);
447
448            MethodInfo factor_mpqs = msieve.GetMethod("factor_mpqs");
449
450            //Now factorize as often as needed:
451            while (!factorManager.OnlyPrimes())
452            {
453                //get one composite factor, which we want to sieve now:
454                BigInteger compositeFactor = factorManager.GetCompositeFactor();
455
456                //now start quadratic sieve on it:               
457                IntPtr resultList = (IntPtr)factor_mpqs.Invoke(null, new object[2] { obj, compositeFactor.ToString() });
458                factorManager.ReplaceCompositeByFactors(compositeFactor, resultList);
459            }
460        }
461
462        /// <summary>
463        /// Helper Thread for msieve, which sieves for relations:
464        /// </summary>
465        /// <param name="param">params</param>
466        private void MSieveJob(object param)
467        {
468            threadcount++;
469            object[] parameters = (object[])param;
470            IntPtr clone = (IntPtr)parameters[0];
471            int update = (int)parameters[1];
472            IntPtr core_sieve_fcn = (IntPtr)parameters[2];
473            Queue yieldqueue = (Queue)parameters[3];
474
475            while (running)
476            {
477                try
478                {
479                    MethodInfo collectRelations = msieve.GetMethod("collectRelations");
480                    collectRelations.Invoke(null, new object[] { clone, update, core_sieve_fcn });
481                    MethodInfo getYield = msieve.GetMethod("getYield");
482                    IntPtr yield = (IntPtr)getYield.Invoke(null, new object[] { clone });
483
484                    //Just for testing the serialize mechanism:
485                    MethodInfo serializeYield = msieve.GetMethod("serializeYield");
486                    byte[] serializedYield = (byte[])serializeYield.Invoke(null, new object[] { yield });
487                    /*MethodInfo deserializeYield = msieve.GetMethod("deserializeYield");
488                    yield = (IntPtr)deserializeYield.Invoke(null, new object[] { serializedYield });*/
489
490                    yieldqueue.Enqueue(yield);
491                }
492                catch (Exception ex)
493                {
494                    GuiLogMessage("Error using msieve." + ex.Message, NotificationLevel.Error);
495                    threadcount = 0;
496                    return;
497                }               
498            }
499            MethodInfo freeSieveConf = msieve.GetMethod("freeSieveConf");
500            freeSieveConf.Invoke(null, new object[] { clone });           
501            threadcount--;
502        }       
503
504        /// <summary>
505        /// Stop all running threads
506        /// </summary>
507        private void stopThreads()
508        {
509            if (conf_list != null)
510            {
511                running = false;
512                MethodInfo stop = msieve.GetMethod("stop");
513                MethodInfo getObjFromConf = msieve.GetMethod("getObjFromConf");
514                foreach (IntPtr conf in conf_list)
515                    stop.Invoke(null, new object[] { getObjFromConf.Invoke(null, new object[] { conf }) });
516                GuiLogMessage("Waiting for threads to stop!", NotificationLevel.Debug);
517                while (threadcount > 0)
518                {
519                    Thread.Sleep(0);
520                }
521                GuiLogMessage("Threads stopped!", NotificationLevel.Debug);
522                conf_list.Clear();
523            }
524        }   
525
526        /// <summary>
527        /// Change the progress of this plugin
528        /// </summary>
529        /// <param name="value">value</param>
530        /// <param name="max">max</param>
531        private void ProgressChanged(double value, double max)
532        {
533            EventsHelper.ProgressChanged(OnPluginProgressChanged, this, new PluginProgressEventArgs(value, max));
534        }
535
536        private void FactorsChanged(List<BigInteger> primeFactors, List<BigInteger> compositeFactors)
537        {
538            GuiLogMessage("Factors Changed:", NotificationLevel.Debug);
539
540            foreach (BigInteger pf in primeFactors)
541                GuiLogMessage("Prime Factor: " + pf.ToString(), NotificationLevel.Debug);
542
543            foreach (BigInteger cf in compositeFactors)
544                GuiLogMessage("Composite Factor: " + cf.ToString(), NotificationLevel.Debug);
545        }
546
547        /// <summary>
548        /// Logs a message to the CrypTool gui
549        /// </summary>
550        /// <param name="p">p</param>
551        /// <param name="notificationLevel">notificationLevel</param>
552        private void GuiLogMessage(string p, NotificationLevel notificationLevel)
553        {
554            EventsHelper.GuiLogMessage(OnGuiLogNotificationOccured, this, new GuiLogEventArgs(p, this, notificationLevel));
555        }
556
557        /// <summary>
558        /// Getter / Setter for the QuickWatchPresentation
559        /// </summary>
560        private QuadraticSievePresentation quadraticSieveQuickWatchPresentation
561        {
562            get { return QuickWatchPresentation as QuadraticSievePresentation; }
563        }
564
565        /// <summary>
566        /// dynamically loads the msieve dll file and sets the callbacks
567        /// </summary>
568        private void initMsieveDLL()
569        {
570            //Load msieve.dll (if necessary):
571            if (msieve == null || msieveDLL == null)
572            {
573                string s = Directory.GetCurrentDirectory();
574                string dllname;
575                if (IntPtr.Size == 4)
576                    dllname = "msieve.dll";
577                else
578                    dllname = "msieve64.dll";
579                msieveDLL = Assembly.LoadFile(Directory.GetCurrentDirectory() + "\\AppReferences\\" + dllname);
580                msieve = msieveDLL.GetType("Msieve.msieve");
581            }
582
583            //init msieve with callbacks:
584            MethodInfo initMsieve = msieve.GetMethod("initMsieve");
585            Object callback_struct = Activator.CreateInstance(msieveDLL.GetType("Msieve.callback_struct"));
586            FieldInfo showProgressField = msieveDLL.GetType("Msieve.callback_struct").GetField("showProgress");
587            FieldInfo prepareSievingField = msieveDLL.GetType("Msieve.callback_struct").GetField("prepareSieving");
588            FieldInfo getTrivialFactorlistField = msieveDLL.GetType("Msieve.callback_struct").GetField("getTrivialFactorlist");
589            Delegate showProgressDel = MulticastDelegate.CreateDelegate(msieveDLL.GetType("Msieve.showProgressDelegate"), this, "showProgress");
590            Delegate prepareSievingDel = MulticastDelegate.CreateDelegate(msieveDLL.GetType("Msieve.prepareSievingDelegate"), this, "prepareSieving");
591            Delegate getTrivialFactorlistDel = MulticastDelegate.CreateDelegate(msieveDLL.GetType("Msieve.getTrivialFactorlistDelegate"), this, "getTrivialFactorlist");
592            showProgressField.SetValue(callback_struct, showProgressDel);
593            prepareSievingField.SetValue(callback_struct, prepareSievingDel);
594            getTrivialFactorlistField.SetValue(callback_struct, getTrivialFactorlistDel);
595            initMsieve.Invoke(null, new object[1] { callback_struct });
596        }
597        #endregion
598
599    }
600}
Note: See TracBrowser for help on using the repository browser.