Changeset 1850


Ignore:
Timestamp:
Aug 20, 2010, 8:42:56 PM (11 years ago)
Author:
Sven Rech
Message:

fixed non field linear equation solving algorithm in discrete logarithm plugin (I will need this for index-calculus-algorithm later)

Location:
trunk/CrypPlugins/DiscreteLogarithm
Files:
4 edited

Legend:

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

    r1785 r1850  
    2727using System.Numerics;
    2828using Cryptool.PluginBase.IO;
     29using DiscreteLogarithm;
    2930
    3031namespace Cryptool.Plugins.DiscreteLogarithm
  • trunk/CrypPlugins/DiscreteLogarithm/FiniteFieldGauss.cs

    r1833 r1850  
    1717        private int size;
    1818        private List<BigInteger[]> matrix;
    19         private List<int> rowSwaps;
     19        private int[] rowSwaps;
    2020        private BigInteger mod;
    2121
     
    2525            this.mod = mod;
    2626            size = matrix.Count;
    27             this.rowSwaps = new List<int>();
     27            this.rowSwaps = new int[matrix.Count];
    2828            for (int i = 0; i < matrix.Count; i++)
    2929                rowSwaps[i] = i;
     
    5959                    if ((matrix[y][x] % mod) != 0)
    6060                        SubAndMultiplyWithConstantRows(x, y, (matrixXXinverse * matrix[y][x]) % mod);
    61                     Debug.Assert(matrix[y][x] == 0);
     61                    Debug.Assert((matrix[y][x] % mod) == 0);
    6262                }
    6363            }
     
    8181                    if ((matrix[y][x] % mod) != 0)
    8282                        SubAndMultiplyWithConstantRows(x, y, (matrixXXinverse * matrix[y][x]) % mod);
    83                     Debug.Assert(matrix[y][x] == 0);
     83                    Debug.Assert((matrix[y][x] % mod) == 0);
    8484                }
    8585            }
     
    9191                BigInteger matrixXXinverse = BigIntegerHelper.ModInverse(matrix[x][x], mod);
    9292                sol[x] = (matrixXXinverse * matrix[x][size]) % mod;
     93                while (sol[x] < 0)
     94                    sol[x] += mod;
    9395            }
    9496            return sol;
     
    113115            {
    114116                matrix[destIndex][i] -= (constant * matrix[srcIndex][i]) % mod;
     117                matrix[destIndex][i] %= mod;
    115118                while (matrix[destIndex][i] < 0)
    116                     matrix[destIndex][i] += mod;
    117                 matrix[destIndex][i] %= mod;
     119                    matrix[destIndex][i] += mod;               
    118120            }
    119121        }
  • trunk/CrypPlugins/DiscreteLogarithm/HenselLifting.cs

    r1830 r1850  
    2727            //create As:
    2828            As.Add(matrix);
    29             for (int i = 0; i < exp; i++)
     29            for (int i = 0; i < (exp-1); i++)
    3030            {
    31                 As.Add(SplitMatrix(As[i], BigInteger.Pow(mod, exp-i)));
     31                As.Add(SplitMatrix(As[i], BigInteger.Pow(mod, exp-i-1)));
    3232            }
    3333            As.Reverse();
    3434
    3535            //create bs:           
    36             for (int i = 0; i <= exp; i++)
     36            for (int i = 0; i < exp; i++)
    3737            {
    3838                bs.Add(GetLastColumnFromMatrix(As[i]));
     
    4242            List<BigInteger[]> A0 = As[0];
    4343            BigInteger[] b = bs[0];
    44             for (int i = 0; i < exp; i++)
     44            for (int i = 0; i < exp-1; i++)
    4545            {
    46                 SetLastColumnFromMatrix(A0, b);
    47                 xs[i] = gauss.Solve(A0, mod);
     46                xs.Add(gauss.Solve(CreateAb(A0, b), mod));
    4847               
    49                 BigInteger[] q = ModVector(SubVectors(MultMatrixWithVector(A0, xs[i]), b), mod);
     48                BigInteger[] q = DivVector(SubVectors(MultMatrixWithVector(A0, xs[i]), b), mod);
    5049                b = SubVectors(bs[i + 1], q);
    5150                for (int c = 0; c <= i; c++)
     
    5352                    b = SubVectors(b, MultMatrixWithVector(As[c + 1], xs[i-c]));
    5453                }
    55             }
    56             SetLastColumnFromMatrix(A0, b);
    57             xs[exp] = gauss.Solve(A0, mod);
     54            }           
     55            xs.Add(gauss.Solve(CreateAb(A0, b), mod));
    5856
    5957            //glue xs together:
    6058            BigInteger[] x = new BigInteger[xs[0].Length];
    61             for (int i = 0; i <= exp; i++)
     59            for (int i = 0; i < exp; i++)
    6260            {
    6361                BigInteger p = BigInteger.Pow(mod, i);
     
    7573            {
    7674                res[y] = 0;
    77                 for (int x = 0; x < vector.Length - 1; x++)
     75                for (int x = 0; x < vector.Length; x++)
    7876                {
    7977                    res[y] += matrix[y][x] * vector[x];
     
    10199        }
    102100
    103         private void SetLastColumnFromMatrix(List<BigInteger[]> matrix, BigInteger[] b)
     101        private BigInteger[] DivVector(BigInteger[] vector, BigInteger mod)
    104102        {
    105             for (int y = 0; y < matrix.Count; y++)
     103            BigInteger[] res = new BigInteger[vector.Length];
     104            for (int y = 0; y < vector.Length; y++)
    106105            {
    107                 matrix[y][matrix[y].Length - 1] = b[y];
     106                res[y] = vector[y] / mod;
    108107            }
     108            return res;
     109        }
     110
     111
     112        /// <summary>
     113        /// Creates a matrix with values of parameter "A" and the last column with values of parameter "b"
     114        /// </summary>
     115        /// <param name="A"></param>
     116        /// <param name="b"></param>
     117        /// <returns>the created matrix</returns>
     118        private List<BigInteger[]> CreateAb(List<BigInteger[]> A, BigInteger[] b)
     119        {
     120            List<BigInteger[]> result = new List<BigInteger[]>();
     121            for (int y = 0; y < A.Count; y++)
     122            {
     123                BigInteger[] row = new BigInteger[A[y].Length];
     124                for (int x = 0; x < A[y].Length - 1; x++)
     125                {
     126                    row[x] = A[y][x];
     127                }
     128                row[A[y].Length - 1] = b[y];
     129                result.Add(row);
     130            }
     131            return result;
    109132        }
    110133
  • trunk/CrypPlugins/DiscreteLogarithm/LinearSystemOfEquations.cs

    r1833 r1850  
    5252             * of this ring do have an inverse.
    5353             * We cope with this problem by factorizing the modulus in its prime factors and solving gauss over them
    54              * separately. We can use the chinese remainder theorem to get the solution we need then.
     54             * separately (in the case of p^q (q>1) by using "hensel lifting").
     55             * We can use the chinese remainder theorem to get the solution we need then.
    5556             * But what happens if we aren't able to factorize the modulus completely, because this is to inefficient?
    5657             * There is a simple trick to cope with that:
     
    195196        }
    196197
    197         /*
    198         public static void Main()
    199         {
    200             LinearSystemOfEquations l = new LinearSystemOfEquations(7, 3);
    201             l.AddEquation(new int[] { 1, 2, 3 }, 4);
    202             l.AddEquation(new int[] { 2, 3, 4 }, 5);
    203             l.AddEquation(new int[] { 5, 4, 5 }, 6);
     198
     199        /*public static void test()
     200        {
     201            LinearSystemOfEquations l = new LinearSystemOfEquations(2*2*2*2*3*3, 3);
     202            l.AddEquation(new BigInteger[] { 2, 4, 1 }, 2);
     203            l.AddEquation(new BigInteger[] { 4, 3, 1 }, 0);
     204            l.AddEquation(new BigInteger[] { 5, 1, 0 }, 2);
    204205
    205206            BigInteger[] sol = l.Solve();
    206207
    207             foreach (int i in sol)
    208                 Console.Out.WriteLine(i);
    209 
    210             Console.In.ReadLine();
    211         }
    212          */
     208            int a = 4;      //Set breackpoint here
     209        }*/
    213210
    214211    }
Note: See TracChangeset for help on using the changeset viewer.