#include<iostream>
#include<time.h>
using namespace std;


//求方幂模，求解res，计算res=g^x mod p
int ModularExponent(int g, int x, int p)
{//计算g^x mod p
	int res = 1;
	for (int i = 0; i < x; i++)
	{
		res = res*g%p;
	}
	return res;
}

//计算离散对数，求x，条件：a=g^x mod p
int dlog(int a, int g, int p) 
{//a为余数，g为底数，模p
	int x = 1, y = 1;
	y = y*g%p;
	while (a!=y&&x<p)
	{
		x++;
		y = y*g%p;
	}
	return x;
}

//sherwood算法变换，求a的离散对数x，先转换为求c的离散对数，最后变换成求a的离散对数
//好处：当要求第三方计算时，能够不使原始数据信息泄露
int dlogRH(int a, int g, int p)
{
	srand((unsigned)time(NULL));
	int r = 0 + rand() % (p - 2);
	int b = ModularExponent(g, r, p);	//求指数为r时的模
	int c = b*a%p;	//变换求c的离散对数
	int y = dlog(c, g, p);

	return (y - r) % (p - 1);	//因为离散对数是循环群，需要模（p-1）
}

void main()
{
	cout << dlog(3, 2, 5) << endl;
	cout << ModularExponent(3, 2, 5) << endl;
	cout << dlogRH(3, 2, 5)<<endl;	//sherwood算法计算，结果和dlog计算一样
	system("pause");
}