source: trunk/CrypPlugins/DiscreteLogarithm/HenselLifting.cs @ 1850

Last change on this file since 1850 was 1850, checked in by Sven Rech, 11 years ago

fixed non field linear equation solving algorithm in discrete logarithm plugin (I will need this for index-calculus-algorithm later)

File size: 5.5 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Text;
5using System.Numerics;
6
7namespace DiscreteLogarithm
8{
9    class HenselLifting
10    {
11        private FiniteFieldGauss gauss = new FiniteFieldGauss();
12
13        /// <summary>
14        /// Hensel-lifting is used when it is necessary to solve a matrix modulo p^r
15        /// where p is a prime and r an integer > 1.
16        /// </summary>
17        /// <param name="matrix">The matrix to solve</param>
18        /// <param name="mod">the prime which the modulo consists of</param>
19        /// <param name="exp">the exponent for mod</param>
20        /// <returns>solution of "matrix" modulo mod^exp </returns>
21        public BigInteger[] Solve(List<BigInteger[]> matrix, BigInteger mod, int exp)
22        {
23            List<List<BigInteger[]>> As = new List<List<BigInteger[]>>(exp+1);
24            List<BigInteger[]> bs = new List<BigInteger[]>(exp + 1);
25            List<BigInteger[]> xs = new List<BigInteger[]>(exp + 1);           
26           
27            //create As:
28            As.Add(matrix);
29            for (int i = 0; i < (exp-1); i++)
30            {
31                As.Add(SplitMatrix(As[i], BigInteger.Pow(mod, exp-i-1)));
32            }
33            As.Reverse();
34
35            //create bs:           
36            for (int i = 0; i < exp; i++)
37            {
38                bs.Add(GetLastColumnFromMatrix(As[i]));
39            }
40
41            //find xs:
42            List<BigInteger[]> A0 = As[0];
43            BigInteger[] b = bs[0];
44            for (int i = 0; i < exp-1; i++)
45            {
46                xs.Add(gauss.Solve(CreateAb(A0, b), mod));
47               
48                BigInteger[] q = DivVector(SubVectors(MultMatrixWithVector(A0, xs[i]), b), mod);
49                b = SubVectors(bs[i + 1], q);
50                for (int c = 0; c <= i; c++)
51                {
52                    b = SubVectors(b, MultMatrixWithVector(As[c + 1], xs[i-c]));
53                }
54            }           
55            xs.Add(gauss.Solve(CreateAb(A0, b), mod));
56
57            //glue xs together:
58            BigInteger[] x = new BigInteger[xs[0].Length];
59            for (int i = 0; i < exp; i++)
60            {
61                BigInteger p = BigInteger.Pow(mod, i);
62                for (int y = 0; y < x.Length; y++)
63                    x[y] += xs[i][y] * p;
64            }
65
66            return x;
67        }
68
69        private BigInteger[] MultMatrixWithVector(List<BigInteger[]> matrix, BigInteger[] vector)
70        {
71            BigInteger[] res = new BigInteger[matrix.Count];
72            for (int y = 0; y < matrix.Count; y++)
73            {
74                res[y] = 0;
75                for (int x = 0; x < vector.Length; x++)
76                {
77                    res[y] += matrix[y][x] * vector[x];
78                }
79            }
80            return res;
81        }
82
83        private BigInteger[] SubVectors(BigInteger[] vector1, BigInteger[] vector2)
84        {
85            BigInteger[] res = new BigInteger[vector1.Length];
86            for (int y = 0; y < vector1.Length; y++)
87                res[y] = vector1[y] - vector2[y];
88            return res;
89        }
90
91        private BigInteger[] ModVector(BigInteger[] vector, BigInteger mod)
92        {
93            BigInteger[] res = new BigInteger[vector.Length];
94            for (int y = 0; y < vector.Length; y++)
95            {
96                res[y] = vector[y] % mod;
97            }
98            return res;
99        }
100
101        private BigInteger[] DivVector(BigInteger[] vector, BigInteger mod)
102        {
103            BigInteger[] res = new BigInteger[vector.Length];
104            for (int y = 0; y < vector.Length; y++)
105            {
106                res[y] = vector[y] / mod;
107            }
108            return res;
109        }
110
111
112        /// <summary>
113        /// Creates a matrix with values of parameter "A" and the last column with values of parameter "b"
114        /// </summary>
115        /// <param name="A"></param>
116        /// <param name="b"></param>
117        /// <returns>the created matrix</returns>
118        private List<BigInteger[]> CreateAb(List<BigInteger[]> A, BigInteger[] b)
119        {
120            List<BigInteger[]> result = new List<BigInteger[]>();
121            for (int y = 0; y < A.Count; y++)
122            {
123                BigInteger[] row = new BigInteger[A[y].Length];
124                for (int x = 0; x < A[y].Length - 1; x++)
125                {
126                    row[x] = A[y][x];
127                }
128                row[A[y].Length - 1] = b[y];
129                result.Add(row);
130            }
131            return result;
132        }
133
134        private BigInteger[] GetLastColumnFromMatrix(List<BigInteger[]> matrix)
135        {
136            BigInteger[] res = new BigInteger[matrix.Count];
137            for (int y = 0; y < matrix.Count; y++)
138            {
139                res[y] = matrix[y][matrix[y].Length - 1];
140            }
141            return res;
142        }
143
144        private List<BigInteger[]> SplitMatrix(List<BigInteger[]> matrix, BigInteger modulo)
145        {
146            List<BigInteger[]> res = new List<BigInteger[]>();
147            for (int y = 0; y < matrix.Count; y++)
148            {
149                BigInteger[] row = new BigInteger[matrix[y].Length];
150                for (int x = 0; x < matrix[y].Length; x++)
151                {
152                    row[x] = matrix[y][x] % modulo;
153                    matrix[y][x] /= modulo;
154                }
155                res.Add(row);
156            }
157            return res;
158        }
159    }
160}
Note: See TracBrowser for help on using the repository browser.