Comment optimiser cet algorithme. Deux dictionnaires et la recherche d'une valeur spécifique

Question

J'ai 2 dictionnaires. J'essaye d'optimiser ce code pour courir aussi vite que possible.

modifier: Désolé, c'est pour la résolution de Shanks bébé Giant Step Step algorithme
algorithme:

Given b = a^x (mod p) 
First choose n, such that n^2 >= p-1 
Then create 2 lists: 
    1. a^j (mod p) for 0 <= j < n 
    2. b*(a(inverse)^n)^k for 0 <= k < n 
Finally look for a match between the 2 lists. 


public static BigInteger modInverse(BigInteger a, BigInteger n) 
{ 
    BigInteger i = n, v = 0, d = 1; 
    while (a > 0) 
    { 
     BigInteger t = i/a, x = a; 
     a = i % x; 
     i = x; 
     x = d; 
     d = v - t * x; 
     v = x; 
    } 
    v %= n; 
    if (v < 0) v = (v + n) % n; 
    return v; 
} 

static int Main() 
{ 
    BigInteger r = 92327518017225, 
       rg, 
       temp, 
       two=2, 
       tm, 
       n = ((BigInteger)Math.Sqrt(247457076132467-1))+1, 
       mod = 247457076132467; 
    Dictionary<int, BigInteger> b = new Dictionary<int, BigInteger>(); 
    Dictionary<int, BigInteger> g = new Dictionary<int, BigInteger>(); 
    temp = modInverse(two, mod); 
    temp = BigInteger.ModPow(temp, n, mod); 
    for (int j = 0; (BigInteger)j < n; j++) 
    { 
     rg = r * BigInteger.ModPow(temp, j, mod); 
     g.Add(j, rg); 
    } 
    for (int i = 0; (BigInteger)i < n ; i++) 
    { 
     tm = BigInteger.ModPow(2, i, mod); 
     foreach (KeyValuePair<int, BigInteger> d in g) 
     { 
      if (d.Value.Equals(tm)) 
      { 
       Console.WriteLine("j={0} B*t^j(mod m) = {1}",d.Key,d.Value); 
       Console.WriteLine("a^"+i+" = "+tm); 
      } 
     } 
     b.Add(i,tm); 
    } 
    Console.ReadKey(); 
    return 0; 
} 

Answer 1

Une optimisation facile est de passer autour du dictionnaire g de sorte que la BigInteger est la

clé

Ensuite, vous pouvez utiliser .ContainsKey pour la rechercher au lieu de la boucle, ce qui serait beaucoup plus rapide