# Changeset 1850

Ignore:
Timestamp:
Aug 20, 2010, 8:42:56 PM (11 years ago)
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

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

 r1785 using System.Numerics; using Cryptool.PluginBase.IO; using DiscreteLogarithm; namespace Cryptool.Plugins.DiscreteLogarithm
• ## trunk/CrypPlugins/DiscreteLogarithm/FiniteFieldGauss.cs

 r1833 private int size; private List matrix; private List rowSwaps; private int[] rowSwaps; private BigInteger mod; this.mod = mod; size = matrix.Count; this.rowSwaps = new List(); this.rowSwaps = new int[matrix.Count]; for (int i = 0; i < matrix.Count; i++) rowSwaps[i] = i; if ((matrix[y][x] % mod) != 0) SubAndMultiplyWithConstantRows(x, y, (matrixXXinverse * matrix[y][x]) % mod); Debug.Assert(matrix[y][x] == 0); Debug.Assert((matrix[y][x] % mod) == 0); } } if ((matrix[y][x] % mod) != 0) SubAndMultiplyWithConstantRows(x, y, (matrixXXinverse * matrix[y][x]) % mod); Debug.Assert(matrix[y][x] == 0); Debug.Assert((matrix[y][x] % mod) == 0); } } BigInteger matrixXXinverse = BigIntegerHelper.ModInverse(matrix[x][x], mod); sol[x] = (matrixXXinverse * matrix[x][size]) % mod; while (sol[x] < 0) sol[x] += mod; } return sol; { matrix[destIndex][i] -= (constant * matrix[srcIndex][i]) % mod; matrix[destIndex][i] %= mod; while (matrix[destIndex][i] < 0) matrix[destIndex][i] += mod; matrix[destIndex][i] %= mod; matrix[destIndex][i] += mod; } }
• ## trunk/CrypPlugins/DiscreteLogarithm/HenselLifting.cs

 r1830 //create As: As.Add(matrix); for (int i = 0; i < exp; i++) for (int i = 0; i < (exp-1); i++) { As.Add(SplitMatrix(As[i], BigInteger.Pow(mod, exp-i))); As.Add(SplitMatrix(As[i], BigInteger.Pow(mod, exp-i-1))); } As.Reverse(); //create bs: for (int i = 0; i <= exp; i++) for (int i = 0; i < exp; i++) { bs.Add(GetLastColumnFromMatrix(As[i])); List A0 = As[0]; BigInteger[] b = bs[0]; for (int i = 0; i < exp; i++) for (int i = 0; i < exp-1; i++) { SetLastColumnFromMatrix(A0, b); xs[i] = gauss.Solve(A0, mod); xs.Add(gauss.Solve(CreateAb(A0, b), mod)); BigInteger[] q = ModVector(SubVectors(MultMatrixWithVector(A0, xs[i]), b), mod); BigInteger[] q = DivVector(SubVectors(MultMatrixWithVector(A0, xs[i]), b), mod); b = SubVectors(bs[i + 1], q); for (int c = 0; c <= i; c++) b = SubVectors(b, MultMatrixWithVector(As[c + 1], xs[i-c])); } } SetLastColumnFromMatrix(A0, b); xs[exp] = gauss.Solve(A0, mod); } xs.Add(gauss.Solve(CreateAb(A0, b), mod)); //glue xs together: BigInteger[] x = new BigInteger[xs[0].Length]; for (int i = 0; i <= exp; i++) for (int i = 0; i < exp; i++) { BigInteger p = BigInteger.Pow(mod, i); { res[y] = 0; for (int x = 0; x < vector.Length - 1; x++) for (int x = 0; x < vector.Length; x++) { res[y] += matrix[y][x] * vector[x]; } private void SetLastColumnFromMatrix(List matrix, BigInteger[] b) private BigInteger[] DivVector(BigInteger[] vector, BigInteger mod) { for (int y = 0; y < matrix.Count; y++) BigInteger[] res = new BigInteger[vector.Length]; for (int y = 0; y < vector.Length; y++) { matrix[y][matrix[y].Length - 1] = b[y]; res[y] = vector[y] / mod; } return res; } /// /// Creates a matrix with values of parameter "A" and the last column with values of parameter "b" /// /// /// /// the created matrix private List CreateAb(List A, BigInteger[] b) { List result = new List(); for (int y = 0; y < A.Count; y++) { BigInteger[] row = new BigInteger[A[y].Length]; for (int x = 0; x < A[y].Length - 1; x++) { row[x] = A[y][x]; } row[A[y].Length - 1] = b[y]; result.Add(row); } return result; }
• ## trunk/CrypPlugins/DiscreteLogarithm/LinearSystemOfEquations.cs

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