Changeset 1830
 Timestamp:
 Aug 18, 2010, 12:51:31 AM (11 years ago)
 Location:
 trunk/CrypPlugins/DiscreteLogarithm
 Files:

 1 added
 1 edited
Legend:
 Unmodified
 Added
 Removed

trunk/CrypPlugins/DiscreteLogarithm/LinearSystemOfEquations.cs
r1816 r1830 60 60 61 61 FiniteFieldGauss gauss = new FiniteFieldGauss(); 62 //TODO ;) 62 HenselLifting hensel = new HenselLifting(); 63 64 List<Msieve.Factor> modfactors = Msieve.TrivialFactorization(mod); 65 List<BigInteger[]> results; 66 67 bool tryAgain; 68 69 do 70 { 71 results = new List<BigInteger[]>(); 72 tryAgain = false; 73 74 for (int i = 0; i < modfactors.Count; i++) 75 { 76 if (modfactors[i].prime) //mod prime 77 { 78 if (modfactors[i].count == 1) 79 results.Add(gauss.Solve(MatrixCopy(), modfactors[i].factor)); 80 else 81 results.Add(hensel.Solve(MatrixCopy(), modfactors[i].factor, modfactors[i].count)); 82 } 83 else //mod composite 84 { 85 //Try using gauss: 86 try 87 { 88 BigInteger[] res = gauss.Solve(MatrixCopy(), modfactors[i].factor); 89 results.Add(res); //Yeah, we had luck :) 90 } 91 catch (NotInvertibleException ex) 92 { 93 //We found a factor of modfactors[i]: 94 BigInteger notInvertible = ex.NotInvertibleNumber; 95 List<Msieve.Factor> morefactors = Msieve.TrivialFactorization(modfactors[i].factor / notInvertible); 96 List<Msieve.Factor> morefactors2 = Msieve.TrivialFactorization(notInvertible); 97 modfactors.RemoveAt(i); 98 ConcatFactorLists(modfactors, morefactors); 99 ConcatFactorLists(modfactors, morefactors2); 100 tryAgain = true; 101 break; 102 } 103 } 104 } 105 } while (tryAgain); 106 107 //TODO: "glue" the results together 108 63 109 return null; 110 } 111 112 /// <summary> 113 /// Creates a deep copy of member variable "matrix" 114 /// </summary> 115 /// <returns>a matrix copy</returns> 116 private List<BigInteger[]> MatrixCopy() 117 { 118 List<BigInteger[]> res = new List<BigInteger[]>(matrix.Count); 119 foreach (BigInteger[] row in matrix) 120 { 121 BigInteger[] resRow = new BigInteger[row.Length]; 122 for (int i = 0; i < row.Length; i++) 123 resRow[i] = row[i]; 124 res.Add(resRow); 125 } 126 return res; 127 } 128 129 private void ConcatFactorLists(List<Msieve.Factor> list1, List<Msieve.Factor> list2) 130 { 131 foreach (Msieve.Factor f in list2) 132 list1.Add(f); 64 133 } 65 134
Note: See TracChangeset
for help on using the changeset viewer.