Changeset 1830


Ignore:
Timestamp:
Aug 18, 2010, 12:51:31 AM (11 years ago)
Author:
Sven Rech
Message:

more preparation for discrete logarithm

Location:
trunk/CrypPlugins/DiscreteLogarithm
Files:
1 added
1 edited

Legend:

Unmodified
Added
Removed
  • trunk/CrypPlugins/DiscreteLogarithm/LinearSystemOfEquations.cs

    r1816 r1830  
    6060
    6161            FiniteFieldGauss gauss = new FiniteFieldGauss();
    62             //TODO ;)
     62            HenselLifting hensel = new HenselLifting();
     63
     64            List<Msieve.Factor> modfactors = Msieve.TrivialFactorization(mod);
     65            List<BigInteger[]> results;
     66
     67            bool tryAgain;
     68
     69            do
     70            {
     71                results = new List<BigInteger[]>();
     72                tryAgain = false;
     73
     74                for (int i = 0; i < modfactors.Count; i++)
     75                {
     76                    if (modfactors[i].prime)    //mod prime
     77                    {
     78                        if (modfactors[i].count == 1)
     79                            results.Add(gauss.Solve(MatrixCopy(), modfactors[i].factor));
     80                        else
     81                            results.Add(hensel.Solve(MatrixCopy(), modfactors[i].factor, modfactors[i].count));
     82                    }
     83                    else    //mod composite
     84                    {
     85                        //Try using gauss:
     86                        try
     87                        {
     88                            BigInteger[] res = gauss.Solve(MatrixCopy(), modfactors[i].factor);
     89                            results.Add(res);   //Yeah, we had luck :)
     90                        }
     91                        catch (NotInvertibleException ex)
     92                        {
     93                            //We found a factor of modfactors[i]:
     94                            BigInteger notInvertible = ex.NotInvertibleNumber;
     95                            List<Msieve.Factor> morefactors = Msieve.TrivialFactorization(modfactors[i].factor / notInvertible);
     96                            List<Msieve.Factor> morefactors2 = Msieve.TrivialFactorization(notInvertible);
     97                            modfactors.RemoveAt(i);
     98                            ConcatFactorLists(modfactors, morefactors);
     99                            ConcatFactorLists(modfactors, morefactors2);
     100                            tryAgain = true;
     101                            break;
     102                        }
     103                    }
     104                }
     105            } while (tryAgain);
     106
     107            //TODO: "glue" the results together
     108
    63109            return null;
     110        }
     111
     112        /// <summary>
     113        /// Creates a deep copy of member variable "matrix"
     114        /// </summary>
     115        /// <returns>a matrix copy</returns>
     116        private List<BigInteger[]> MatrixCopy()
     117        {
     118            List<BigInteger[]> res = new List<BigInteger[]>(matrix.Count);
     119            foreach (BigInteger[] row in matrix)
     120            {
     121                BigInteger[] resRow = new BigInteger[row.Length];
     122                for (int i = 0; i < row.Length; i++)
     123                    resRow[i] = row[i];
     124                res.Add(resRow);
     125            }
     126            return res;
     127        }
     128
     129        private void ConcatFactorLists(List<Msieve.Factor> list1, List<Msieve.Factor> list2)
     130        {
     131            foreach (Msieve.Factor f in list2)
     132                list1.Add(f);
    64133        }
    65134
Note: See TracChangeset for help on using the changeset viewer.