Changeset 1816


Ignore:
Timestamp:
Aug 16, 2010, 10:42:33 PM (11 years ago)
Author:
Sven Rech
Message:

some preparation for DiscreteLogarithm plugin

Location:
trunk
Files:
2 added
3 edited

Legend:

Unmodified
Added
Removed
  • trunk/CrypPluginBase/Miscellaneous/BigIntegerHelper.cs

    r1455 r1816  
    207207        public static BigInteger ModInverse(BigInteger input, BigInteger modulus)
    208208        {
     209            if (input == 1)
     210                return 1;
     211            if (input == 0)
     212                throw (new ArithmeticException("No inverse!"));
     213
    209214            BigInteger[] p = { 0, 1 };
    210215            BigInteger[] q = new BigInteger[2];    // quotients
  • trunk/CrypPlugins/DiscreteLogarithm/DiscreteLogarithm.csproj

    r1810 r1816  
    8787  <ItemGroup>
    8888    <Compile Include="FactorBase.cs" />
     89    <Compile Include="FiniteFieldGauss.cs" />
     90    <Compile Include="LinearDependentException.cs" />
    8991    <Compile Include="LinearSystemOfEquations.cs" />
    9092    <Compile Include="Properties\AssemblyInfo.cs" />
  • trunk/CrypPlugins/DiscreteLogarithm/LinearSystemOfEquations.cs

    r1800 r1816  
    1212    {
    1313        private BigInteger mod;
    14         private BigInteger size;
    15         private List<int[]> matrix;
     14        private int size;
     15        private List<BigInteger[]> matrix;
    1616
    17         public LinearSystemOfEquations(BigInteger mod, BigInteger size)
     17        public LinearSystemOfEquations(BigInteger mod, int size)
    1818        {
    1919            this.mod = mod;
    2020            this.size = size;
    21             matrix = new List<int[]>((int)size);
     21            matrix = new List<BigInteger[]>(size);
    2222        }
    2323
    24         public void AddEquation(int[] coefficients, int b)
     24        public void AddEquation(BigInteger[] coefficients, BigInteger b)
    2525        {
    26             Debug.Assert(coefficients.Length == size);           
     26            Debug.Assert(coefficients.Length == size);
    2727
    28             int[] row = new int[coefficients.Length + 1];
     28            BigInteger[] row = new BigInteger[coefficients.Length + 1];
    2929            for (int c = 0; c < coefficients.Length; c++)
    3030                row[c] = coefficients[c];
    3131            row[row.Length - 1] = b;
    3232
    33             if (!LinearDependent(row))
    34                 matrix.Add(row);
    35         }
    36 
    37         private bool LinearDependent(int[] row)
    38         {
    39             foreach (int[] mr in matrix)
    40             {
    41                 bool linear = true;
    42                 BigInteger row0invers = BigIntegerHelper.ModInverse(row[0], mod);
    43                 BigInteger mr0 = new BigInteger(mr[0]);
    44                 BigInteger div = (mr0 * row0invers) % mod;
    45                 for (int i = 1; i < size + 1; i++)
    46                 {
    47                     if (row[i] * div != mr[0])
    48                     {
    49                         linear = false;
    50                         break;
    51                     }
    52                 }
    53                 if (linear)
    54                     return true;
    55             }
    56             return false;
     33            /** It would be better to check first if "row" is linear dependent to the other rows and neglect the adding in this case.
     34             *  However, checking this is not very efficient.
     35             *  So instead we hope that independence is given most of the time, and if not, solving the equation system will reveal this.
     36             *  TODO: Check if this is a good approach!
     37             **/
     38            matrix.Add(row);
    5739        }
    5840
     
    6244        }
    6345
    64         public int[] Solve()
     46        public BigInteger[] Solve()
    6547        {
    66             //TODO: Gauss here
     48            /* Solving a linear equation over a residue class is not so trivial if the modulus is not a prime.
     49             * This is because residue classes with a composite modulus is not a field, which means that not all elements
     50             * of this ring do have an inverse.
     51             * We cope with this problem by factorizing the modulus in its prime factors and solving gauss over them
     52             * separately. We can use the chinese remainder theorem to get the solution we need then.
     53             * But what happens if we aren't able to factorize the modulus completely, because this is to inefficient?
     54             * There is a simple trick to cope with that:
     55             * Try the gauss algorithm with the composite modulus. Either you have luck and it works out without a problem
     56             * (in this case we can just go on), or the gauss algorithm will have a problem inverting some number.
     57             * In the last case, we can search for the gcd of this number and the composite modulus. This gcd is a factor of the modulus,
     58             * so that solving the equation helped us finding the factorization.
     59             */
     60
     61            FiniteFieldGauss gauss = new FiniteFieldGauss();
     62            //TODO ;)
    6763            return null;
    6864        }
    6965
     66
     67        /**
     68         * For debugging only
     69         **/
     70        internal void PrintMatrix()
     71        {
     72            for (int x = 0; x < size; x++)
     73            {
     74                for (int y = 0; y < size + 1; y++)
     75                {
     76                    Console.Out.Write(matrix[x][y] + "\t");
     77                }
     78                Console.Out.WriteLine("");
     79            }
     80            Console.Out.WriteLine("");
     81        }
     82
     83        /*
     84        public static void Main()
     85        {
     86            LinearSystemOfEquations l = new LinearSystemOfEquations(7, 3);
     87            l.AddEquation(new int[] { 1, 2, 3 }, 4);
     88            l.AddEquation(new int[] { 2, 3, 4 }, 5);
     89            l.AddEquation(new int[] { 5, 4, 5 }, 6);
     90
     91            BigInteger[] sol = l.Solve();
     92
     93            foreach (int i in sol)
     94                Console.Out.WriteLine(i);
     95
     96            Console.In.ReadLine();
     97        }
     98         */
     99
    70100    }
    71101}
Note: See TracChangeset for help on using the changeset viewer.