Changeset 1851
 Timestamp:
 Aug 20, 2010, 11:59:33 PM (11 years ago)
 Location:
 trunk/CrypPlugins/DiscreteLogarithm
 Files:

 1 added
 4 edited
Legend:
 Unmodified
 Added
 Removed

trunk/CrypPlugins/DiscreteLogarithm/DiscreteLogarithm.csproj
r1832 r1851 89 89 <Compile Include="FiniteFieldGauss.cs" /> 90 90 <Compile Include="HenselLifting.cs" /> 91 <Compile Include="IndexCalculusMethod.cs" /> 91 92 <Compile Include="LinearDependentException.cs" /> 92 93 <Compile Include="LinearSystemOfEquations.cs" /> 
trunk/CrypPlugins/DiscreteLogarithm/FactorBase.cs
r1799 r1851 36 36 37 37 /** 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. 39 41 **/ 40 public int[] Factorize(BigInteger number)42 public BigInteger[] Factorize(BigInteger number) 41 43 { 42 int[] result = new int[primes.Count];44 BigInteger[] result = new BigInteger[primes.Count]; 43 45 for (int c = 0; c < primes.Count; c++) 44 46 { … … 56 58 } 57 59 60 public int FactorCount() 61 { 62 return primes.Count; 63 } 64 58 65 } 59 66 } 
trunk/CrypPlugins/DiscreteLogarithm/FiniteFieldGauss.cs
r1850 r1851 35 35 { 36 36 int y = x + 1; 37 while (y < size && (matrix[ x][y] % mod) == 0)37 while (y < size && (matrix[y][x] % mod) == 0) 38 38 y++; 39 39 if (y == size) 
trunk/CrypPlugins/DiscreteLogarithm/LinearSystemOfEquations.cs
r1850 r1851 25 25 { 26 26 Debug.Assert(coefficients.Length == size); 27 if (! MoreEquations())27 if (!NeedMoreEquations()) 28 28 return; 29 29 … … 41 41 } 42 42 43 public bool MoreEquations()43 public bool NeedMoreEquations() 44 44 { 45 45 return (matrix.Count < size); … … 70 70 bool tryAgain; 71 71 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 78 76 { 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++) 80 81 { 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 90 83 { 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])); 93 88 } 94 catch (NotInvertibleException ex)89 else //mod composite 95 90 { 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 111 110 } 112 111 } 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 } 116 121 117 122 BigInteger[] result = new BigInteger[size];
Note: See TracChangeset
for help on using the changeset viewer.