如何优化这个算法.两个字典和搜索一个特定的值
本文关键字:一个 搜索 优化 何优化 算法 两个 字典 | 更新日期: 2023-09-27 18:09:07
我有2本字典。我正在尝试优化此代码以尽可能快地运行。
编辑:对不起,这是解决Shanks婴儿步巨人步算法
算法:
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;
}
一个简单的优化是切换g字典,使BigInteger成为键
那么你可以使用。containskey来搜索它,而不是循环,这会快得多