Changeset 1588


Ignore:
Timestamp:
Jun 4, 2010, 8:50:14 PM (12 years ago)
Author:
Sven Rech
Message:

quadratic sieve fix

Location:
trunk/CrypPlugins/QuadraticSieve
Files:
2 edited

Legend:

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

    r1531 r1588  
    3232        private List<BigInteger> primeFactors = new List<BigInteger>();
    3333        private List<BigInteger> compositeFactors = new List<BigInteger>();
     34        private BigInteger number;
    3435
    3536        [NonSerialized]
     
    4243        public event FactorsChangedHandler FactorsChanged;
    4344
    44         public FactorManager(MethodInfo getPrimeFactors, MethodInfo getCompositeFactors)
     45        public FactorManager(MethodInfo getPrimeFactors, MethodInfo getCompositeFactors, BigInteger number)
    4546        {
    4647            this.getPrimeFactorsMethod = getPrimeFactors;
    4748            this.getCompositeFactorsMethod = getCompositeFactors;
     49            this.number = number;
    4850        }
    4951
     
    7072            AddFactorsWithoutFiringEvent(factorList);
    7173            FactorsChanged(primeFactors, compositeFactors);
    72         }
    73 
    74         /// <summary>
    75         /// adds the factor list as composite factors
    76         /// </summary>
    77         public void AddCompositeFactors(List<BigInteger> factors)
    78         {
    79             compositeFactors.AddRange(factors);
    80             FactorsChanged(this.primeFactors, this.compositeFactors);
    81         }
    82 
    83         /// <summary>
    84         /// adds the factor list as prime factors
    85         /// </summary>
    86         public void AddPrimeFactors(List<BigInteger> factors)
    87         {
    88             primeFactors.AddRange(factors);
    89             FactorsChanged(this.primeFactors, this.compositeFactors);
    9074        }
    9175
     
    152136        public void ReplaceCompositeByFactors(BigInteger composite, List<BigInteger> primeFactors, List<BigInteger> compositeFactors)
    153137        {
    154             #region debug
    155             BigInteger n = 1;
     138            //Some debug stuff:
     139            BigInteger comp = 1;
    156140            foreach (BigInteger p in primeFactors)
    157                 n *= p;
     141                comp *= p;
    158142            foreach (BigInteger c in compositeFactors)
    159                 n *= c;
    160             Debug.Assert(n == composite);
    161             #endregion
    162 
    163             int amount = this.compositeFactors.Count(c => (c == composite));
    164             for (int i = 0; i < amount; i++)
    165             {
    166                 this.primeFactors.AddRange(primeFactors);
    167                 this.compositeFactors.AddRange(compositeFactors);
    168             }
    169             int amount2 = this.compositeFactors.RemoveAll(c => (c == composite));
    170            
    171             Debug.Assert(amount == amount2);
    172             Debug.Assert(CalculateNumber() == n);
    173 
     143                comp *= c;
     144            Debug.Assert(comp == composite);
     145
     146            //Add:
     147            this.primeFactors.AddRange(primeFactors);
     148            this.compositeFactors.AddRange(compositeFactors);
     149            normalizeLists();
     150
     151            Debug.Assert(CalculateNumber() == this.number);
    174152            FactorsChanged(this.primeFactors, this.compositeFactors);
    175153        }
     
    181159        public void ReplaceCompositeByFactors(BigInteger composite, IntPtr factorList)
    182160        {
    183             int amount = compositeFactors.Count(c => (c == composite));
    184             for (int i = 0; i < amount; i++)
    185                 AddFactorsWithoutFiringEvent(factorList);
    186             int amount2 = compositeFactors.RemoveAll(c => (c == composite));
    187 
    188161            //Some debug stuff:
    189             Debug.Assert(amount == amount2);
    190             FactorManager debugFactorManager = new FactorManager(getPrimeFactorsMethod, getCompositeFactorsMethod);
     162            FactorManager debugFactorManager = new FactorManager(getPrimeFactorsMethod, getCompositeFactorsMethod, composite);
    191163            debugFactorManager.AddFactorsWithoutFiringEvent(factorList);
    192164            Debug.Assert(debugFactorManager.CalculateNumber() == composite);
    193165
     166            //Add:
     167            AddFactorsWithoutFiringEvent(factorList);
     168            normalizeLists();
     169
     170            Debug.Assert(CalculateNumber() == this.number);
    194171            FactorsChanged(primeFactors, compositeFactors);
    195172        }
     
    238215            foreach (Object o in cf)
    239216                compositeFactors.Add(BigInteger.Parse((string)o));
     217
     218            normalizeLists();
     219        }
     220
     221        /// <summary>
     222        /// Normalizes the prime and composite factor lists, i.e. after calling this method, N is the product
     223        /// of the elements from both the prime and the composite factor list.
     224        /// </summary>       
     225        private void normalizeLists()
     226        {
     227            primeFactors.Sort();
     228            compositeFactors.Sort();
     229
     230            BigInteger N = this.number;
     231            List<BigInteger> pf = new List<BigInteger>();
     232            List<BigInteger> cf = new List<BigInteger>();
     233
     234            foreach (BigInteger p in primeFactors)
     235            {
     236                while (N % p == 0)  //while N is divisible by p...
     237                {
     238                    pf.Add(p);
     239                    N = N / p;
     240                }
     241            }
     242
     243            foreach (BigInteger c in compositeFactors)
     244            {
     245                while (N % c == 0)  //while N is divisible by c...
     246                {
     247                    cf.Add(c);
     248                    N = N / c;
     249                }
     250            }
     251           
     252            primeFactors = pf;
     253            compositeFactors = cf;
     254
     255            Debug.Assert(N == 1);
    240256        }
    241257
  • trunk/CrypPlugins/QuadraticSieve/QuadraticSieve.cs

    r1575 r1588  
    201201
    202202                initMsieveDLL();
    203                 factorManager = new FactorManager(msieve.GetMethod("getPrimeFactors"), msieve.GetMethod("getCompositeFactors"));
     203                factorManager = new FactorManager(msieve.GetMethod("getPrimeFactors"), msieve.GetMethod("getCompositeFactors"), InputNumber);
    204204                factorManager.FactorsChanged += this.FactorsChanged;
    205205
Note: See TracChangeset for help on using the changeset viewer.