Changeset 1851


Ignore:
Timestamp:
Aug 20, 2010, 11:59:33 PM (11 years ago)
Author:
Sven Rech
Message:

for discrete logarithm plugin:
added first part of index-calculus-algorithm

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

Legend:

Unmodified
Added
Removed
  • trunk/CrypPlugins/DiscreteLogarithm/DiscreteLogarithm.csproj

    r1832 r1851  
    8989    <Compile Include="FiniteFieldGauss.cs" />
    9090    <Compile Include="HenselLifting.cs" />
     91    <Compile Include="IndexCalculusMethod.cs" />
    9192    <Compile Include="LinearDependentException.cs" />
    9293    <Compile Include="LinearSystemOfEquations.cs" />
  • trunk/CrypPlugins/DiscreteLogarithm/FactorBase.cs

    r1799 r1851  
    3636
    3737        /**
    38          * Tries to factor parameter "number" with the factor base and returns an array giving the relations.
     38         * (Trial Division)
     39         * Tries to factor parameter "number" with the factor base and returns an array indicating how many times each factor had to be divided.
     40         * If factorization is not possible, returns null.
    3941         **/
    40         public int[] Factorize(BigInteger number)
     42        public BigInteger[] Factorize(BigInteger number)
    4143        {
    42             int[] result = new int[primes.Count];
     44            BigInteger[] result = new BigInteger[primes.Count];
    4345            for (int c = 0; c < primes.Count; c++)
    4446            {
     
    5658        }
    5759
     60        public int FactorCount()
     61        {
     62            return primes.Count;
     63        }
     64
    5865    }
    5966}
  • trunk/CrypPlugins/DiscreteLogarithm/FiniteFieldGauss.cs

    r1850 r1851  
    3535                {
    3636                    int y = x + 1;
    37                     while (y < size && (matrix[x][y] % mod) == 0)
     37                    while (y < size && (matrix[y][x] % mod) == 0)
    3838                        y++;
    3939                    if (y == size)
  • trunk/CrypPlugins/DiscreteLogarithm/LinearSystemOfEquations.cs

    r1850 r1851  
    2525        {
    2626            Debug.Assert(coefficients.Length == size);
    27             if (!MoreEquations())
     27            if (!NeedMoreEquations())
    2828                return;
    2929
     
    4141        }
    4242
    43         public bool MoreEquations()
     43        public bool NeedMoreEquations()
    4444        {
    4545            return (matrix.Count < size);
     
    7070            bool tryAgain;
    7171
    72             do
    73             {
    74                 results = new List<KeyValuePair<BigInteger[],Msieve.Factor>>();
    75                 tryAgain = false;
    76 
    77                 for (int i = 0; i < modfactors.Count; i++)
     72            try
     73            {
     74           
     75                do
    7876                {
    79                     if (modfactors[i].prime)    //mod prime
     77                    results = new List<KeyValuePair<BigInteger[], Msieve.Factor>>();
     78                    tryAgain = false;
     79
     80                    for (int i = 0; i < modfactors.Count; i++)
    8081                    {
    81                         if (modfactors[i].count == 1)                           
    82                             results.Add(new KeyValuePair<BigInteger[],Msieve.Factor>(gauss.Solve(MatrixCopy(), modfactors[i].factor), modfactors[i]));
    83                         else
    84                             results.Add(new KeyValuePair<BigInteger[],Msieve.Factor>(hensel.Solve(MatrixCopy(), modfactors[i].factor, modfactors[i].count), modfactors[i]));
    85                     }
    86                     else    //mod composite
    87                     {
    88                         //Try using gauss:
    89                         try
     82                        if (modfactors[i].prime)    //mod prime
    9083                        {
    91                             BigInteger[] res = gauss.Solve(MatrixCopy(), modfactors[i].factor);
    92                             results.Add(new KeyValuePair<BigInteger[],Msieve.Factor>(res, modfactors[i]));   //Yeah, we had luck :)
     84                            if (modfactors[i].count == 1)
     85                                results.Add(new KeyValuePair<BigInteger[], Msieve.Factor>(gauss.Solve(MatrixCopy(), modfactors[i].factor), modfactors[i]));
     86                            else
     87                                results.Add(new KeyValuePair<BigInteger[], Msieve.Factor>(hensel.Solve(MatrixCopy(), modfactors[i].factor, modfactors[i].count), modfactors[i]));
    9388                        }
    94                         catch (NotInvertibleException ex)
     89                        else    //mod composite
    9590                        {
    96                             //We found a factor of modfactors[i]:
    97                             BigInteger notInvertible = ex.NotInvertibleNumber;
    98                             List<Msieve.Factor> morefactors = Msieve.TrivialFactorization(modfactors[i].factor / notInvertible);
    99                             List<Msieve.Factor> morefactors2 = Msieve.TrivialFactorization(notInvertible);
    100                             modfactors.RemoveAt(i);
    101                             ConcatFactorLists(modfactors, morefactors);
    102                             ConcatFactorLists(modfactors, morefactors2);
    103                             tryAgain = true;
    104                             break;
    105                         }
    106                         catch (LinearDependentException ex)
    107                         {
    108                             //We have to throw away one row and try again later:
    109                             matrix.RemoveAt(ex.RowToDelete);
    110                             return null;
     91                            //Try using gauss:
     92                            try
     93                            {
     94                                BigInteger[] res = gauss.Solve(MatrixCopy(), modfactors[i].factor);
     95                                results.Add(new KeyValuePair<BigInteger[], Msieve.Factor>(res, modfactors[i]));   //Yeah, we had luck :)
     96                            }
     97                            catch (NotInvertibleException ex)
     98                            {
     99                                //We found a factor of modfactors[i]:
     100                                BigInteger notInvertible = ex.NotInvertibleNumber;
     101                                List<Msieve.Factor> morefactors = Msieve.TrivialFactorization(modfactors[i].factor / notInvertible);
     102                                List<Msieve.Factor> morefactors2 = Msieve.TrivialFactorization(notInvertible);
     103                                modfactors.RemoveAt(i);
     104                                ConcatFactorLists(modfactors, morefactors);
     105                                ConcatFactorLists(modfactors, morefactors2);
     106                                tryAgain = true;
     107                                break;
     108                            }
     109
    111110                        }
    112111                    }
    113                 }
    114             } while (tryAgain);
    115 
     112                } while (tryAgain);
     113           
     114            }
     115            catch (LinearDependentException ex)
     116            {
     117                //We have to throw away one row and try again later:
     118                matrix.RemoveAt(ex.RowToDelete);
     119                return null;
     120            }
    116121
    117122            BigInteger[] result = new BigInteger[size];
Note: See TracChangeset for help on using the changeset viewer.