使用C#实现pholig_hellman算法，要求其中使用了小步大步算法，不使用BigInteger类

Pholig-Hellman算法（离散对数问题）是一个非常重要的密码学基础算法，其核心在于求解一个模数下离散对数问题。小步大步算法是求解离散对数问题的一种有效方法。本文将介绍如何在C#中使用小步大步算法实现Pholig-Hellman算法。

首先，我们需要实现一个模幂函数。由于题目要求不使用BigInteger类，我们可以通过模重复平方法实现模幂函数。代码如下：

public static long ModPow(long x, long y, long p)
{
    long res = 1;
    x %= p;
    while (y > 0)
    {
        if ((y & 1) == 1)
        {
            res = (res * x) % p;
        }
        y >>= 1;
        x = (x * x) % p;
    }
    return res;
}

接下来，我们可以实现小步大步算法。小步大步算法的核心思想是将指数y分解为x^j*b的形式，其中x^j是x的一些次幂，b是小于x^j的整数。我们可以先计算出x^j的值，然后用哈希表存储所有可能的b和其对应的j值，最后查找y对应的b值在哈希表中的j值即可。代码如下：

public static long BabyStepGiantStep(long a, long b, long p)
{
    // 计算m
    long m = (long)Math.Ceiling(Math.Sqrt(p - 1));

    // 预处理x^j mod p的值
    Dictionary<long, long> dict = new Dictionary<long, long>();
    long xj = b % p;
    for (long j = 0; j < m; j++)
    {
        dict[xj] = j;
        xj = (xj * a) % p;
    }

    // 计算x^-m mod p的值
    long xm = ModPow(a, p - 1 - m, p);

    // 穷举b*x^-m mod p的值，查找哈希表中对应的j值
    long xb = 1;
    for (long i = 0; i < m; i++)
    {
        if (dict.ContainsKey(xb))
        {
            return i * m + dict[xb];
        }
        xb = (xb * xm) % p;
    }

    return -1;  // 未找到解
}

最后，我们可以实现Pholig-Hellman算法。Pholig-Hellman算法的核心在于求解一个模数下离散对数问题。我们可以先计算出a^x mod p的值，并使用小步大步算法求解该值在模数p下的离散对数x。代码如下：

public static long PholigHellman(long a, long b, long p)
{
    // 计算m
    long m = (long)Math.Ceiling(Math.Sqrt(p - 1));

    // 预处理a^j mod p的值
    long aj = 1;
    for (long j = 0; j < m; j++)
    {
        aj = (aj * a) % p;
    }

    // 枚举i，计算a^(im) mod p的值，使用小步大步算法求解
    Dictionary<long, long> dict = new Dictionary<long, long>();
    long aim = b % p;
    for (long i = 0; i < m; i++)
    {
        dict[aim] = i;
        aim = (aim * aj) % p;
    }

    long ai = ModPow(a, m, p);
    long aix = 1;
    for (long i = 1; i <= m; i++)
    {
        aix = (aix * ai) % p;
        if (dict.ContainsKey(aix))
        {
            return i * m - dict[aix];
        }
    }

    return -1;  // 未找到解
}

完整代码如下：

using System;
using System.Collections.Generic;

public class PholigHellman
{
    public static long ModPow(long x, long y, long p)
    {
        long res = 1;
        x %= p;
        while (y > 0)
        {
            if ((y & 1) == 1)
            {
                res = (res * x) % p;
            }
            y >>= 1;
            x = (x * x) % p;
        }
        return res;
    }

    public static long BabyStepGiantStep(long a, long b, long p)
    {
        // 计算m
        long m = (long)Math.Ceiling(Math.Sqrt(p - 1));

        // 预处理x^j mod p的值
        Dictionary<long, long> dict = new Dictionary<long, long>();
        long xj = b % p;
        for (long j = 0; j < m; j++)
        {
            dict[xj] = j;
            xj = (xj * a) % p;
        }

        // 计算x^-m mod p的值
        long xm = ModPow(a, p - 1 - m, p);

        // 穷举b*x^-m mod p的值，查找哈希表中对应的j值
        long xb = 1;
        for (long i = 0; i < m; i++)
        {
            if (dict.ContainsKey(xb))
            {
                return i * m + dict[xb];
            }
            xb = (xb * xm) % p;
        }

        return -1;  // 未找到解
    }

    public static long PholigHellman(long a, long b, long p)
    {
        // 计算m
        long m = (long)Math.Ceiling(Math.Sqrt(p - 1));

        // 预处理a^j mod p的值
        long aj = 1;
        for (long j = 0; j < m; j++)
        {
            aj = (aj * a) % p;
        }

        // 枚举i，计算a^(im) mod p的值，使用小步大步算法求解
        Dictionary<long, long> dict = new Dictionary<long, long>();
        long aim = b % p;
        for (long i = 0; i < m; i++)
        {
            dict[aim] = i;
            aim = (aim * aj) % p;
        }

        long ai = ModPow(a, m, p);
        long aix = 1;
        for (long i = 1; i <= m; i++)
        {
            aix = (aix * ai) % p;
            if (dict.ContainsKey(aix))
            {
                return i * m - dict[aix];
            }
        }

        return -1;  // 未找到解
    }

    static void Main(string[] args)
    {
        long a = 3;
        long b = 7;
        long p = 11;
        long x = PholigHellman(a, b, p);
        Console.WriteLine("x = " + x);
    }
}