# Changeset 1833

Ignore:
Timestamp:
Aug 18, 2010, 9:20:18 PM (11 years ago)
Message:

discrete logarithm preparation

Location:
trunk/CrypPlugins/DiscreteLogarithm
Files:
4 edited

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

 r1816 private int size; private List matrix; private List rowSwaps; private BigInteger mod; this.mod = mod; size = matrix.Count; this.rowSwaps = new List(); for (int i = 0; i < matrix.Count; i++) rowSwaps[i] = i; //make lower triangular matrix: for (int x = 0; x < size; x++) { if (matrix[x][x] == 0) if ((matrix[x][x] % mod) == 0) { int y = x + 1; while (y < size && matrix[x][y] == 0) while (y < size && (matrix[x][y] % mod) == 0) y++; if (y == size) { matrix.RemoveAt(size - 1); throw new LinearDependentException(); throw new LinearDependentException(rowSwaps[size-1]); } SwapRows(x, y); } BigInteger matrixXXinverse = BigIntegerHelper.ModInverse(matrix[x][x], mod); BigInteger matrixXXinverse; try { matrixXXinverse = BigIntegerHelper.ModInverse(matrix[x][x], mod); } catch (ArithmeticException) { throw new NotInvertibleException(matrix[x][x] % mod); } for (int y = x + 1; y < size; y++) { if (matrix[y][x] != 0) if ((matrix[y][x] % mod) != 0) SubAndMultiplyWithConstantRows(x, y, (matrixXXinverse * matrix[y][x]) % mod); Debug.Assert(matrix[y][x] == 0); for (int x = (size - 1); x >= 0; x--) { BigInteger matrixXXinverse = BigIntegerHelper.ModInverse(matrix[x][x], mod); BigInteger matrixXXinverse; try { matrixXXinverse = BigIntegerHelper.ModInverse(matrix[x][x], mod); } catch (ArithmeticException) { throw new NotInvertibleException(matrix[x][x] % mod); } for (int y = x - 1; y >= 0; y--) { if (matrix[y][x] != 0) SubAndMultiplyWithConstantRows(x, y, matrixXXinverse * matrix[y][x]); if ((matrix[y][x] % mod) != 0) SubAndMultiplyWithConstantRows(x, y, (matrixXXinverse * matrix[y][x]) % mod); Debug.Assert(matrix[y][x] == 0); } } matrix[index1] = matrix[index2]; matrix[index2] = tmp; int tmp2 = rowSwaps[index1]; rowSwaps[index1] = rowSwaps[index2]; rowSwaps[index2] = tmp2; }
• ## trunk/CrypPlugins/DiscreteLogarithm/LinearDependentException.cs

 r1816 class LinearDependentException : Exception { public int RowToDelete { get; private set; } public LinearDependentException(int rowToDelete) { this.RowToDelete = rowToDelete; } } }
• ## trunk/CrypPlugins/DiscreteLogarithm/LinearSystemOfEquations.cs

 r1830 { Debug.Assert(coefficients.Length == size); if (!MoreEquations()) return; BigInteger[] row = new BigInteger[coefficients.Length + 1]; HenselLifting hensel = new HenselLifting(); List modfactors = Msieve.TrivialFactorization(mod); List results; List modfactors = Msieve.TrivialFactorization(mod); List> results;   //Stores the partial solutions together with their factors bool tryAgain; do { results = new List(); results = new List>(); tryAgain = false; if (modfactors[i].prime)    //mod prime { if (modfactors[i].count == 1) results.Add(gauss.Solve(MatrixCopy(), modfactors[i].factor)); if (modfactors[i].count == 1) results.Add(new KeyValuePair(gauss.Solve(MatrixCopy(), modfactors[i].factor), modfactors[i])); else results.Add(hensel.Solve(MatrixCopy(), modfactors[i].factor, modfactors[i].count)); results.Add(new KeyValuePair(hensel.Solve(MatrixCopy(), modfactors[i].factor, modfactors[i].count), modfactors[i])); } else    //mod composite { BigInteger[] res = gauss.Solve(MatrixCopy(), modfactors[i].factor); results.Add(res);   //Yeah, we had luck :) results.Add(new KeyValuePair(res, modfactors[i]));   //Yeah, we had luck :) } catch (NotInvertibleException ex) break; } catch (LinearDependentException ex) { //We have to throw away one row and try again later: matrix.RemoveAt(ex.RowToDelete); return null; } } } } while (tryAgain); //TODO: "glue" the results together return null; BigInteger[] result = new BigInteger[size]; //"glue" the results together: for (int i = 0; i < size; i++) { List> partSolItem = new List>(); for (int c = 0; c < results.Count; c++) { partSolItem.Add(new KeyValuePair(results[c].Key[i], BigInteger.Pow(results[c].Value.factor, results[c].Value.count))); } result[i] = CRT(partSolItem); } return result; } /// /// Implementation of solutionfinding for chinese remainder theorem. /// i.e. finding an x that fullfills /// x = a1 (mod m1) /// x = a2 (mod m2) /// ... /// /// The congruences (a_i, m_i) /// the value that fits into all congruences private BigInteger CRT(List> congruences) { BigInteger x = 0; for (int i = 0; i < congruences.Count; i++) { BigInteger k = 1; for (int c = 0; c < congruences.Count; c++) if (c != i) k *= congruences[c].Value; BigInteger r = BigIntegerHelper.ModInverse(k, congruences[i].Value); x += congruences[i].Key * r * k; } return x; }
• ## trunk/CrypPlugins/DiscreteLogarithm/NotInvertibleException.cs

 r1832 using System.Linq; using System.Text; using System.Numerics; namespace DiscreteLogarithm class NotInvertibleException : Exception { public int NotInvertibleNumber public BigInteger NotInvertibleNumber { get; } public NotInvertibleException(int notInvertible) public NotInvertibleException(BigInteger notInvertible) { NotInvertibleNumber = notInvertible;
Note: See TracChangeset for help on using the changeset viewer.