source: trunk/CrypPlugins/DiscreteLogarithm/IndexCalculusMethod.cs @ 1933

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

Some index-calculus-algorithm fixes (still doesn't work very good yet :( )

File size: 2.5 KB
Line 
1using System;
2using System.Collections.Generic;
3using System.Linq;
4using System.Text;
5using System.Numerics;
6
7namespace DiscreteLogarithm
8{
9    class IndexCalculusMethod
10    {
11        private FactorBase factorBase;
12
13        public BigInteger DiscreteLog(BigInteger n, BigInteger logbase, BigInteger mod)
14        {
15            int B = GetSmoothnessBound(mod);
16            factorBase = new FactorBase();
17            factorBase.Generate(B);
18
19            //First part: Find logarithms of the factorbase elements:
20
21            LinearSystemOfEquations linearSystem = new LinearSystemOfEquations(mod - 1, factorBase.FactorCount());
22            BigInteger r = 1;
23            BigInteger[] logs = null;
24
25            do
26            {
27                while (linearSystem.NeedMoreEquations())
28                {
29                    BigInteger gr = BigInteger.ModPow(logbase, r, mod);
30                    if (gr == 1)
31                        throw new Exception("Input base not a generator of given residue class");
32
33                    BigInteger[] coefficients = factorBase.Factorize(gr);
34                    if (coefficients != null)
35                        linearSystem.AddEquation(coefficients, r);
36
37                    r++;
38                    if (r > mod - 2)
39                        throw new Exception("Index-Calculus step 1 Exception: Not enough relations!");
40                }
41
42                logs = linearSystem.Solve();
43            } while (logs == null);
44
45            //Second part: Find the discrete logarithm of n:
46
47            r = 0;
48            BigInteger[] factorization;
49            do
50            {
51                r++;
52                if (r > mod - 2)
53                    throw new Exception("Index-Calculus step 2 Exception: Not factorizable!");
54
55                factorization = factorBase.Factorize(BigInteger.ModPow(logbase, r, mod) * n);               
56            } while (factorization == null);
57
58            BigInteger result = -r;
59            for (int i = 0; i < logs.Length; i++)
60                result += (factorization[i] * logs[i]) % (mod-1);
61
62            result %= (mod - 1);
63            while (result < 0)
64                result += (mod - 1);
65
66            return result;
67        }
68
69        private int GetSmoothnessBound(BigInteger mod)
70        {           
71            double logm = BigInteger.Log(mod);
72            int B = (int)(Math.Exp(Math.Sqrt(logm * Math.Log(logm)))/2);
73
74            if (B < 1000)
75                B = 1000;
76            return B;
77        }
78    }
79}
Note: See TracBrowser for help on using the repository browser.