Changeset 1851

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

for discrete logarithm plugin:

Location:
trunk/CrypPlugins/DiscreteLogarithm
Files:
4 edited

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

 r1832
• trunk/CrypPlugins/DiscreteLogarithm/FactorBase.cs

 r1799 /** * Tries to factor parameter "number" with the factor base and returns an array giving the relations. * (Trial Division) * Tries to factor parameter "number" with the factor base and returns an array indicating how many times each factor had to be divided. * If factorization is not possible, returns null. **/ public int[] Factorize(BigInteger number) public BigInteger[] Factorize(BigInteger number) { int[] result = new int[primes.Count]; BigInteger[] result = new BigInteger[primes.Count]; for (int c = 0; c < primes.Count; c++) { } public int FactorCount() { return primes.Count; } } }
• trunk/CrypPlugins/DiscreteLogarithm/FiniteFieldGauss.cs

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

 r1850 { Debug.Assert(coefficients.Length == size); if (!MoreEquations()) if (!NeedMoreEquations()) return; } public bool MoreEquations() public bool NeedMoreEquations() { return (matrix.Count < size); bool tryAgain; do { results = new List>(); tryAgain = false; for (int i = 0; i < modfactors.Count; i++) try { do { if (modfactors[i].prime)    //mod prime results = new List>(); tryAgain = false; for (int i = 0; i < modfactors.Count; i++) { if (modfactors[i].count == 1) results.Add(new KeyValuePair(gauss.Solve(MatrixCopy(), modfactors[i].factor), modfactors[i])); else results.Add(new KeyValuePair(hensel.Solve(MatrixCopy(), modfactors[i].factor, modfactors[i].count), modfactors[i])); } else    //mod composite { //Try using gauss: try if (modfactors[i].prime)    //mod prime { BigInteger[] res = gauss.Solve(MatrixCopy(), modfactors[i].factor); results.Add(new KeyValuePair(res, modfactors[i]));   //Yeah, we had luck :) if (modfactors[i].count == 1) results.Add(new KeyValuePair(gauss.Solve(MatrixCopy(), modfactors[i].factor), modfactors[i])); else results.Add(new KeyValuePair(hensel.Solve(MatrixCopy(), modfactors[i].factor, modfactors[i].count), modfactors[i])); } catch (NotInvertibleException ex) else    //mod composite { //We found a factor of modfactors[i]: BigInteger notInvertible = ex.NotInvertibleNumber; List morefactors = Msieve.TrivialFactorization(modfactors[i].factor / notInvertible); List morefactors2 = Msieve.TrivialFactorization(notInvertible); modfactors.RemoveAt(i); ConcatFactorLists(modfactors, morefactors); ConcatFactorLists(modfactors, morefactors2); tryAgain = true; break; } catch (LinearDependentException ex) { //We have to throw away one row and try again later: matrix.RemoveAt(ex.RowToDelete); return null; //Try using gauss: try { BigInteger[] res = gauss.Solve(MatrixCopy(), modfactors[i].factor); results.Add(new KeyValuePair(res, modfactors[i]));   //Yeah, we had luck :) } catch (NotInvertibleException ex) { //We found a factor of modfactors[i]: BigInteger notInvertible = ex.NotInvertibleNumber; List morefactors = Msieve.TrivialFactorization(modfactors[i].factor / notInvertible); List morefactors2 = Msieve.TrivialFactorization(notInvertible); modfactors.RemoveAt(i); ConcatFactorLists(modfactors, morefactors); ConcatFactorLists(modfactors, morefactors2); tryAgain = true; break; } } } } } while (tryAgain); } while (tryAgain); } catch (LinearDependentException ex) { //We have to throw away one row and try again later: matrix.RemoveAt(ex.RowToDelete); return null; } BigInteger[] result = new BigInteger[size];
Note: See TracChangeset for help on using the changeset viewer.