Changeset 1520


Ignore:
Timestamp:
May 27, 2010, 8:08:03 PM (12 years ago)
Author:
Sven Rech
Message:

some implementations for FactorManager

File:
1 edited

Legend:

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

    r1511 r1520  
    7373        {
    7474            compositeFactors.AddRange(factors);
     75            FactorsChanged(this.primeFactors, this.compositeFactors);
    7576        }
    7677
     
    8182        {
    8283            primeFactors.AddRange(factors);
     84            FactorsChanged(this.primeFactors, this.compositeFactors);
    8385        }
    8486
     
    8991        public bool Synchronize(FactorManager factorManager)
    9092        {
    91             throw new NotImplementedException();
     93            Debug.Assert(factorManager.CalculateNumber() == this.CalculateNumber());
     94            if (sameFactorization(factorManager))
     95                return false;
     96
     97            //check if we can gain information from factorManager for our FactorList (and put these informations in our list)
     98            foreach (BigInteger comp in compositeFactors)
     99            {
     100                if (!factorManager.compositeFactors.Contains(comp))
     101                {
     102                    List<BigInteger> primeFactorsForComp = new List<BigInteger>();
     103                    List<BigInteger> compositeFactorsForComp = new List<BigInteger>();
     104                    //Let's check whether factorManager already has a factorization for comp:
     105                    foreach (BigInteger p in factorManager.primeFactors)
     106                        if (comp % p == 0)
     107                            primeFactorsForComp.Add(p);
     108                    foreach (BigInteger c in factorManager.compositeFactors)
     109                        if (comp != c && comp % c == 0)
     110                            compositeFactorsForComp.Add(c);
     111                    if (primeFactorsForComp.Count != 0 || compositeFactorsForComp.Count != 0)
     112                    {
     113                        ReplaceCompositeByFactors(comp, primeFactorsForComp, compositeFactorsForComp);
     114                        return Synchronize(factorManager);
     115                    }
     116                }
     117            }
     118
     119            //now check if our FactorList has more informations than factorManager:
     120            return !sameFactorization(factorManager);
     121        }
     122
     123        private bool sameFactorization(FactorManager factorManager)
     124        {
     125            bool equalPrimes = primeFactors.Intersect(factorManager.primeFactors).Count() == 0;
     126            bool equalComposites = compositeFactors.Intersect(factorManager.compositeFactors).Count() == 0;
     127            return (equalPrimes && equalComposites);
    92128        }
    93129
     
    101137                    return true;
    102138            return false;
     139        }
     140
     141        /// <summary>
     142        /// replaces the composite factor "composite" by the factors of the parameters "primeFactors" and "compositeFactors".
     143        /// of course, the factors have to multiply up to composite.
     144        /// </summary>
     145        public void ReplaceCompositeByFactors(BigInteger composite, List<BigInteger> primeFactors, List<BigInteger> compositeFactors)
     146        {
     147            #region debug
     148            BigInteger n = 1;
     149            foreach (BigInteger p in primeFactors)
     150                n *= p;
     151            foreach (BigInteger c in compositeFactors)
     152                n *= c;
     153            Debug.Assert(n == compositeFactors);
     154            #endregion
     155
     156            int amount = this.compositeFactors.Count(c => (c == composite));
     157            for (int i = 0; i < amount; i++)
     158            {
     159                this.primeFactors.AddRange(primeFactors);
     160                this.compositeFactors.AddRange(compositeFactors);
     161            }
     162            int amount2 = this.compositeFactors.RemoveAll(c => (c == composite));
     163           
     164            Debug.Assert(amount == amount2);
     165            Debug.Assert(CalculateNumber() == n);
     166
     167            FactorsChanged(this.primeFactors, this.compositeFactors);
    103168        }
    104169
Note: See TracChangeset for help on using the changeset viewer.