使用C#实现pholig_hellman算法,要求其中使用了小步大步算法
时间: 2024-05-03 09:19:11 浏览: 17
下面是使用 C# 实现 pholig_hellman 算法,并使用了小步大步算法的代码示例:
```csharp
using System;
using System.Numerics;
namespace Pohlig_Hellman
{
class Program
{
static void Main(string[] args)
{
BigInteger p = 23; // 模数
BigInteger g = 5; // 原根
BigInteger y = 8; // y = g^x mod p
BigInteger x = Pohlig_Hellman(p, g, y);
Console.WriteLine("x = " + x);
}
// pholig_hellman 算法
static BigInteger Pohlig_Hellman(BigInteger p, BigInteger g, BigInteger y)
{
BigInteger m = Sqrt(p - 1);
BigInteger[] b = new BigInteger[m + 1];
BigInteger[] g_inv = new BigInteger[m + 1];
for (BigInteger i = 0; i < m; i++)
{
b[i] = BigInteger.ModPow(g, i, p);
g_inv[i] = BigInteger.ModPow(b[i], p - 2, p);
}
BigInteger yp = y;
for (BigInteger i = 0; i < m; i++)
{
BigInteger j = Array.IndexOf(b, yp);
if (j >= 0)
{
return i * m + j;
}
yp = yp * g_inv[i % m] % p;
}
return -1;
}
// 计算平方根
static BigInteger Sqrt(BigInteger n)
{
BigInteger a = n;
BigInteger b = 1;
while (b <= a)
{
a -= b;
b += 2;
}
return (b - 1) / 2;
}
}
}
```
在上面的代码中,我们首先定义了模数 p、原根 g 和 y = g^x mod p。接着,我们实现了 Pohlig_Hellman 算法,其中使用了小步大步算法。最后,我们调用 Pohlig_Hellman 函数,并输出结果。
值得注意的是,在 Pohlig_Hellman 函数中,我们首先计算了 b[i] 和 g_inv[i],这两个数组分别存储了 g^i 和 (g^i)^(-1)。接着,我们使用小步大步算法依次计算 yp,并查找是否存在一个 j,满足 b[j] = yp。如果找到了这样的 j,则返回 i * m + j,即 x 的值。如果遍历了整个数组,仍然没有找到这样的 j,则返回 -1。
相关推荐
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)