Changeset 1521


Ignore:
Timestamp:
May 27, 2010, 11:53:19 PM (12 years ago)
Author:
Sven Rech
Message:

some more quadratic sieve implementation stuff

Location:
trunk/CrypPlugins/QuadraticSieve
Files:
1 added
4 edited

Legend:

Unmodified
Added
Removed
  • trunk/CrypPlugins/QuadraticSieve/FactorManager.cs

    r1520 r1521  
    9292        {
    9393            Debug.Assert(factorManager.CalculateNumber() == this.CalculateNumber());
    94             if (sameFactorization(factorManager))
     94            if (SameFactorization(factorManager))
    9595                return false;
    9696
     
    102102                    List<BigInteger> primeFactorsForComp = new List<BigInteger>();
    103103                    List<BigInteger> compositeFactorsForComp = new List<BigInteger>();
     104
    104105                    //Let's check whether factorManager already has a factorization for comp:
    105106                    foreach (BigInteger p in factorManager.primeFactors)
     
    109110                        if (comp != c && comp % c == 0)
    110111                            compositeFactorsForComp.Add(c);
     112
    111113                    if (primeFactorsForComp.Count != 0 || compositeFactorsForComp.Count != 0)
    112114                    {
     
    118120
    119121            //now check if our FactorList has more informations than factorManager:
    120             return !sameFactorization(factorManager);
    121         }
    122 
    123         private bool sameFactorization(FactorManager factorManager)
     122            return !SameFactorization(factorManager);
     123        }
     124
     125        private bool SameFactorization(FactorManager factorManager)
    124126        {
    125127            bool equalPrimes = primeFactors.Intersect(factorManager.primeFactors).Count() == 0;
     
    151153            foreach (BigInteger c in compositeFactors)
    152154                n *= c;
    153             Debug.Assert(n == compositeFactors);
     155            Debug.Assert(n == composite);
    154156            #endregion
    155157
     
    188190        }
    189191
    190         private BigInteger DivideIntByFactors(BigInteger composite, IntPtr factorList)
    191         {
    192             throw new NotImplementedException();
    193         }
    194 
    195192        /// <summary>
    196193        /// Returns a single composite factor (or 0, if no composite factors are left).
     
    211208        }
    212209
     210        /// <summary>
     211        /// Returns all prime factors in a sorted fashion.
     212        /// </summary>
    213213        public BigInteger[] getPrimeFactors()
    214214        {
  • trunk/CrypPlugins/QuadraticSieve/PeerToPeer.cs

    r1511 r1521  
    1 using System;
     1/*                             
     2   Copyright 2010 Sven Rech, 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;
    218using System.Collections.Generic;
    319using System.Linq;
     
    824using System.Numerics;
    925using System.Diagnostics;
     26using System.Collections;
     27using System.Threading;
    1028
    1129namespace Cryptool.Plugins.QuadraticSieve
     
    1735        private BigInteger factor;
    1836        private int head;
     37        private Queue storequeue;   //yields to store in the DHT
     38        private Queue loadqueue;    //yields that have been loaded from the DHT
     39        private Thread loadStoreThread;
     40        private bool stopLoadStoreThread;
    1941
    2042        private byte[] ReadYield(int index)
    2143        {
    22             byte[] yield = P2PManager.Retrieve(channel + "#" + factor + "!" + index);
     44            byte[] yield = P2PManager.Retrieve(YieldIdentifier(index));
    2345            if (yield == null)
    2446                return null;
     
    2850            defStream.Read(yield, 0, yield.Length);
    2951            byte[] decompressedYield = memStream.ToArray();
     52           
     53            return decompressedYield;
     54        }
    3055
    31             return decompressedYield;
     56        private void LoadStoreThreadProc()
     57        {
     58            int loadEnd = head; //we know, that the DHT entries from 1 to "loadEnd" are unknown to us, so we will load these when we have no other things to do
     59            int loadIndex = 0;
     60
     61            while (!stopLoadStoreThread)
     62            {
     63                if (loadIndex >= loadEnd)   //if we already loaded the yields up to "loadEnd", we don't have too much to do anymore, so we can slow down :)
     64                    Thread.Sleep(1000);
     65
     66                if (storequeue.Count != 0)  //storing has priority
     67                {
     68                    byte[] yield = (byte[])storequeue.Dequeue();
     69                    P2PManager.Store(YieldIdentifier(head), yield);
     70                    //TODO: If versioning sytem tells us, that there is already a newer entry here, we load this value, enqueue it in loadqueue and try again with head++
     71                    head++;
     72                    P2PManager.Store(HeadIdentifier(), head.ToString());
     73                    //TODO: If versioning system tells us, that there is already a newer head entry, we ignore this and don't store ours
     74                }
     75                else                      //if there is nothing to store, we can load the yields up to "loadEnd"
     76                {
     77                    if (loadIndex < loadEnd)
     78                    {
     79                        byte[] yield = ReadYield(loadIndex);
     80                        loadqueue.Enqueue(yield);
     81                        loadIndex++;
     82                    }
     83                }
     84            }
     85        }
     86
     87        private string HeadIdentifier()
     88        {
     89            return channel + "#" + factor + "HEAD";
     90        }
     91
     92        private string YieldIdentifier(int index)
     93        {
     94            return channel + "#" + factor + "!" + index;
     95        }
     96
     97        private void StartLoadStoreThread()
     98        {
     99            storequeue = Queue.Synchronized(new Queue());
     100            loadqueue = Queue.Synchronized(new Queue());
     101
     102            stopLoadStoreThread = false;
     103            loadStoreThread = new Thread(LoadStoreThreadProc);
     104            loadStoreThread.Start();
     105        }
     106
     107        public void StopLoadStoreThread()
     108        {
     109            stopLoadStoreThread = true;
     110            loadStoreThread.Join();
     111            loadStoreThread = null;
     112        }
     113
     114        public Queue GetLoadedYieldsQueue()
     115        {
     116            return loadqueue;
    32117        }
    33118
     
    43128            byte[] compressedYield = memStream.ToArray();
    44129
    45             P2PManager.Store(channel + "#" + factor + "!" + head, compressedYield);
    46             head++;
    47             P2PManager.Store(channel + "#" + factor + "HEAD:" + head, head.ToString());
    48 
     130            storequeue.Enqueue(compressedYield);
    49131            return compressedYield.Length;
    50132        }
     
    67149
    68150        /// <summary>
    69         /// Sets the factor to sieve next
     151        /// Sets the factor to sieve next and starts reading informations from the DHT.
    70152        /// </summary>
    71153        public void SetFactor(BigInteger factor)
     
    74156            Debug.Assert(this.number % this.factor == 0);
    75157
    76             byte[] h = P2PManager.Retrieve(channel + "#" + factor + "HEAD:" + head);
     158            byte[] h = P2PManager.Retrieve(HeadIdentifier());
    77159            if (h != null)
    78160                head = int.Parse(h.ToString());
    79161            else
    80162                head = 0;
     163
     164            if (loadStoreThread != null)
     165                throw new Exception("LoadStoreThread already started");
     166            StartLoadStoreThread();
    81167        }       
    82168
  • trunk/CrypPlugins/QuadraticSieve/QuadraticSieve.cs

    r1511 r1521  
    435435
    436436            //manage the yields of the other threads:
    437             if (manageYields(conf, max_relations))  //this method returns as soon as there are enough relations found
    438             {
    439                 //sieving is finished now, so give some informations and stop threads:
    440                 ProgressChanged(0.9, 1.0);
    441                 GuiLogMessage("Sieving finished", NotificationLevel.Info);
    442                 quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
    443                 {
    444                     quadraticSieveQuickWatchPresentation.factorInfo.Content = "Found enough relations! Please wait...";
    445                 }, null);
    446             }
     437            manageYields(conf, max_relations);  //this method returns as soon as there are enough relations found
     438            if (userStopped)
     439                return;
     440
     441            //sieving is finished now, so give some informations and stop threads:
     442            ProgressChanged(0.9, 1.0);
     443            GuiLogMessage("Sieving finished", NotificationLevel.Info);
     444            quadraticSieveQuickWatchPresentation.Dispatcher.Invoke(DispatcherPriority.Normal, (SendOrPostCallback)delegate
     445            {
     446                quadraticSieveQuickWatchPresentation.factorInfo.Content = "Found enough relations! Please wait...";
     447            }, null);
     448           
    447449            stopThreads();
    448450            if (yieldqueue != null)
     
    454456        /// Returns true, if enough relations have been found.
    455457        /// </summary>
    456         private bool manageYields(IntPtr conf, int max_relations)
     458        private void manageYields(IntPtr conf, int max_relations)
    457459        {
    458460            MethodInfo serializeYield = msieve.GetMethod("serializeYield");
     461            MethodInfo deserializeYield = msieve.GetMethod("deserializeYield");
    459462            MethodInfo getNumRelations = msieve.GetMethod("getNumRelations");
    460463            int num_relations = (int)getNumRelations.Invoke(null, new object[] { conf });
     
    469472                yieldEvent.WaitOne();               //wait until queue is not empty
    470473                if (userStopped)
    471                     return false;
     474                    return;
     475
    472476                while (yieldqueue.Count != 0)       //get all the results from the helper threads, and store them
    473477                {
     
    483487                    saveYield.Invoke(null, new object[] { conf, yield });
    484488                }
     489
     490                if (usePeer2Peer)
     491                {
     492                    Queue dhtqueue = peerToPeer.GetLoadedYieldsQueue();
     493                    while (dhtqueue.Count != 0)       //get all the loaded results from the DHT, and store them
     494                    {
     495                        byte[] yield = (byte[])dhtqueue.Dequeue();
     496                        IntPtr deserializedYield = (IntPtr)deserializeYield.Invoke(null, new object[] { yield });
     497                        saveYield.Invoke(null, new object[] { conf, deserializedYield });
     498                    }
     499                }
     500
    485501                num_relations = (int)getNumRelations.Invoke(null, new object[] { conf });
    486502                showProgressPresentation(max_relations, num_relations, start_relations, start_sieving_time);
     
    488504                if (usePeer2Peer && !peerToPeer.SyncFactorManager(factorManager))   //an other peer already finished sieving
    489505                {
    490                     return false;
    491                 }
    492             }
    493             return true;
     506                    throw new AlreadySievedException();
     507                }
     508            }           
    494509        }
    495510
     
    549564                    peerToPeer.SetFactor(compositeFactor);
    550565
    551                 //now start quadratic sieve on it:               
    552                 IntPtr resultList = (IntPtr)msieve_run_core.Invoke(null, new object[2] { obj, compositeFactor.ToString() });
    553                 if (userStopped)
    554                     return;
    555                 if (!usePeer2Peer || peerToPeer.SyncFactorManager(factorManager))       //add the result list to factorManager if no other peer already updated it
    556                     factorManager.ReplaceCompositeByFactors(compositeFactor, resultList);
    557 
    558                 if (usePeer2Peer)
    559                     peerToPeer.SyncFactorManager(factorManager);
     566                try
     567                {
     568                    //now start quadratic sieve on it:               
     569                    IntPtr resultList = (IntPtr)msieve_run_core.Invoke(null, new object[2] { obj, compositeFactor.ToString() });
     570                    if (userStopped)
     571                        return;
     572
     573                    factorManager.ReplaceCompositeByFactors(compositeFactor, resultList);   //add the result list to factorManager
     574
     575                    if (usePeer2Peer)
     576                        peerToPeer.SyncFactorManager(factorManager);
     577                }
     578                catch (AlreadySievedException)
     579                {
     580                    GuiLogMessage("Another peer already finished factorization of composite factor" + compositeFactor + ". Sieving next one...", NotificationLevel.Info);
     581                }
    560582            }
    561583        }
     
    620642            {
    621643                running = false;
     644                if (usePeer2Peer)
     645                    peerToPeer.StopLoadStoreThread();
     646
    622647                MethodInfo stop = msieve.GetMethod("stop");
    623648                MethodInfo getObjFromConf = msieve.GetMethod("getObjFromConf");
  • trunk/CrypPlugins/QuadraticSieve/QuadraticSieve.csproj

    r1510 r1521  
    106106  </ItemGroup>
    107107  <ItemGroup>
     108    <Compile Include="AlreadySievedException.cs" />
    108109    <Compile Include="FactorManager.cs" />
    109110    <Compile Include="PeerToPeer.cs" />
Note: See TracChangeset for help on using the changeset viewer.