Changeset 1833


Ignore:
Timestamp:
Aug 18, 2010, 9:20:18 PM (11 years ago)
Author:
Sven Rech
Message:

discrete logarithm preparation

Location:
trunk/CrypPlugins/DiscreteLogarithm
Files:
4 edited

Legend:

Unmodified
Added
Removed
  • trunk/CrypPlugins/DiscreteLogarithm/FiniteFieldGauss.cs

    r1816 r1833  
    1717        private int size;
    1818        private List<BigInteger[]> matrix;
     19        private List<int> rowSwaps;
    1920        private BigInteger mod;
    2021
     
    2425            this.mod = mod;
    2526            size = matrix.Count;
     27            this.rowSwaps = new List<int>();
     28            for (int i = 0; i < matrix.Count; i++)
     29                rowSwaps[i] = i;
    2630
    2731            //make lower triangular matrix:
    2832            for (int x = 0; x < size; x++)
    2933            {
    30                 if (matrix[x][x] == 0)
     34                if ((matrix[x][x] % mod) == 0)
    3135                {
    3236                    int y = x + 1;
    33                     while (y < size && matrix[x][y] == 0)
     37                    while (y < size && (matrix[x][y] % mod) == 0)
    3438                        y++;
    3539                    if (y == size)
    3640                    {
    37                         matrix.RemoveAt(size - 1);
    38                         throw new LinearDependentException();
     41                        throw new LinearDependentException(rowSwaps[size-1]);
    3942                    }
    4043                    SwapRows(x, y);
    4144                }
    4245
    43                 BigInteger matrixXXinverse = BigIntegerHelper.ModInverse(matrix[x][x], mod);
     46                BigInteger matrixXXinverse;
     47
     48                try
     49                {
     50                    matrixXXinverse = BigIntegerHelper.ModInverse(matrix[x][x], mod);
     51                }
     52                catch (ArithmeticException)
     53                {                   
     54                    throw new NotInvertibleException(matrix[x][x] % mod);
     55                }
    4456
    4557                for (int y = x + 1; y < size; y++)
    4658                {
    47                     if (matrix[y][x] != 0)
     59                    if ((matrix[y][x] % mod) != 0)
    4860                        SubAndMultiplyWithConstantRows(x, y, (matrixXXinverse * matrix[y][x]) % mod);
    4961                    Debug.Assert(matrix[y][x] == 0);
     
    5466            for (int x = (size - 1); x >= 0; x--)
    5567            {
    56                 BigInteger matrixXXinverse = BigIntegerHelper.ModInverse(matrix[x][x], mod);
     68                BigInteger matrixXXinverse;
     69
     70                try
     71                {
     72                    matrixXXinverse = BigIntegerHelper.ModInverse(matrix[x][x], mod);
     73                }
     74                catch (ArithmeticException)
     75                {
     76                    throw new NotInvertibleException(matrix[x][x] % mod);
     77                }
    5778
    5879                for (int y = x - 1; y >= 0; y--)
    5980                {
    60                     if (matrix[y][x] != 0)
    61                         SubAndMultiplyWithConstantRows(x, y, matrixXXinverse * matrix[y][x]);
     81                    if ((matrix[y][x] % mod) != 0)
     82                        SubAndMultiplyWithConstantRows(x, y, (matrixXXinverse * matrix[y][x]) % mod);
     83                    Debug.Assert(matrix[y][x] == 0);
    6284                }
    6385            }
     
    78100            matrix[index1] = matrix[index2];
    79101            matrix[index2] = tmp;
     102
     103            int tmp2 = rowSwaps[index1];
     104            rowSwaps[index1] = rowSwaps[index2];
     105            rowSwaps[index2] = tmp2;
    80106        }
    81107
  • trunk/CrypPlugins/DiscreteLogarithm/LinearDependentException.cs

    r1816 r1833  
    88    class LinearDependentException : Exception
    99    {
     10        public int RowToDelete
     11        {
     12            get;
     13            private set;
     14        }
     15
     16        public LinearDependentException(int rowToDelete)
     17        {
     18            this.RowToDelete = rowToDelete;
     19        }
    1020    }
    1121}
  • trunk/CrypPlugins/DiscreteLogarithm/LinearSystemOfEquations.cs

    r1830 r1833  
    2525        {
    2626            Debug.Assert(coefficients.Length == size);
     27            if (!MoreEquations())
     28                return;
    2729
    2830            BigInteger[] row = new BigInteger[coefficients.Length + 1];
     
    6264            HenselLifting hensel = new HenselLifting();
    6365
    64             List<Msieve.Factor> modfactors = Msieve.TrivialFactorization(mod);
    65             List<BigInteger[]> results;
     66            List<Msieve.Factor> modfactors = Msieve.TrivialFactorization(mod);           
     67            List<KeyValuePair<BigInteger[], Msieve.Factor>> results;   //Stores the partial solutions together with their factors
    6668
    6769            bool tryAgain;
     
    6971            do
    7072            {
    71                 results = new List<BigInteger[]>();
     73                results = new List<KeyValuePair<BigInteger[],Msieve.Factor>>();
    7274                tryAgain = false;
    7375
     
    7678                    if (modfactors[i].prime)    //mod prime
    7779                    {
    78                         if (modfactors[i].count == 1)
    79                             results.Add(gauss.Solve(MatrixCopy(), modfactors[i].factor));
     80                        if (modfactors[i].count == 1)                           
     81                            results.Add(new KeyValuePair<BigInteger[],Msieve.Factor>(gauss.Solve(MatrixCopy(), modfactors[i].factor), modfactors[i]));
    8082                        else
    81                             results.Add(hensel.Solve(MatrixCopy(), modfactors[i].factor, modfactors[i].count));
     83                            results.Add(new KeyValuePair<BigInteger[],Msieve.Factor>(hensel.Solve(MatrixCopy(), modfactors[i].factor, modfactors[i].count), modfactors[i]));
    8284                    }
    8385                    else    //mod composite
     
    8789                        {
    8890                            BigInteger[] res = gauss.Solve(MatrixCopy(), modfactors[i].factor);
    89                             results.Add(res);   //Yeah, we had luck :)
     91                            results.Add(new KeyValuePair<BigInteger[],Msieve.Factor>(res, modfactors[i]));   //Yeah, we had luck :)
    9092                        }
    9193                        catch (NotInvertibleException ex)
     
    101103                            break;
    102104                        }
     105                        catch (LinearDependentException ex)
     106                        {
     107                            //We have to throw away one row and try again later:
     108                            matrix.RemoveAt(ex.RowToDelete);
     109                            return null;
     110                        }
    103111                    }
    104112                }
    105113            } while (tryAgain);
    106114
    107             //TODO: "glue" the results together
    108 
    109             return null;
     115
     116            BigInteger[] result = new BigInteger[size];
     117            //"glue" the results together:
     118            for (int i = 0; i < size; i++)
     119            {
     120                List<KeyValuePair<BigInteger, BigInteger>> partSolItem = new List<KeyValuePair<BigInteger,BigInteger>>();
     121                for (int c = 0; c < results.Count; c++)
     122                {
     123                    partSolItem.Add(new KeyValuePair<BigInteger, BigInteger>(results[c].Key[i], BigInteger.Pow(results[c].Value.factor, results[c].Value.count)));
     124                }
     125                result[i] = CRT(partSolItem);
     126            }
     127
     128            return result;
     129        }
     130
     131        /// <summary>
     132        /// Implementation of solutionfinding for chinese remainder theorem.
     133        /// i.e. finding an x that fullfills
     134        /// x = a1 (mod m1)
     135        /// x = a2 (mod m2)
     136        /// ...
     137        /// </summary>
     138        /// <param name="congruences">The congruences (a_i, m_i)</param>
     139        /// <returns>the value that fits into all congruences</returns>
     140        private BigInteger CRT(List<KeyValuePair<BigInteger, BigInteger>> congruences)
     141        {
     142            BigInteger x = 0;
     143            for (int i = 0; i < congruences.Count; i++)
     144            {
     145                BigInteger k = 1;
     146                for (int c = 0; c < congruences.Count; c++)
     147                    if (c != i)
     148                        k *= congruences[c].Value;
     149                BigInteger r = BigIntegerHelper.ModInverse(k, congruences[i].Value);
     150
     151                x += congruences[i].Key * r * k;
     152            }
     153
     154            return x;
    110155        }
    111156
  • trunk/CrypPlugins/DiscreteLogarithm/NotInvertibleException.cs

    r1832 r1833  
    33using System.Linq;
    44using System.Text;
     5using System.Numerics;
    56
    67namespace DiscreteLogarithm
     
    89    class NotInvertibleException : Exception
    910    {
    10         public int NotInvertibleNumber
     11        public BigInteger NotInvertibleNumber
    1112        {
    1213            get;
     
    1415        }
    1516
    16         public NotInvertibleException(int notInvertible)
     17        public NotInvertibleException(BigInteger notInvertible)
    1718        {
    1819            NotInvertibleNumber = notInvertible;
Note: See TracChangeset for help on using the changeset viewer.