关于Diffie-Hellman算法

Diffie-Hellman算法来实现密钥交换,具体算法原理就不说了.这里要求(n^x)mod p,其中n是大整数,p是大素数.x是一个随机生成的整数,各位达人,(n^x)直接做的话肯定会溢出,请问有什么办法可以实现?是在linux下用C库做.

9 个解决方案

#1

保存到数组当中去进行了...

//-----------------NO1 求X^n次方------------------------
//纯C跑就小地方改改就可以跑了
#include <iostream>
#include <algorithm>

using namespace std;

int tvalue;
int effectbit;
#define  N 100
#define  ENDPOS N-1
int temp[N];
int result[N];
void moveonebit()
{
	int newpos,endpos,prevpos;
	endpos = ENDPOS;
	newpos = endpos-temp[0]; //此位置位进位后的数开始位置 
	prevpos = newpos+1; //此位置为原temp中数开始的位置
	for(int loopcnt = temp[0]; loopcnt>0; loopcnt--,newpos++,prevpos++)
	{
		temp[newpos] = temp[prevpos];
	}
	temp[endpos] = 0;
	temp[0] += 1;
}

void multiply(int bitvalue)//处理乘法进位
{
	int bitlen = temp[0];
	if(bitlen>ENDPOS) exit(-1); //进位到temp[0]的标志位时，说明长度不够，出现异常

	int newcnt = 0;    //从新统计目标数组的有效位数
	int cur;
	int bkvalue=0;

	for(int i=ENDPOS; bitlen--; i--)//此处bitlen该为temp的有效位数
	{	
		cur = i;
		result[i] += temp[i] * bitvalue;

		while(result[cur]/10 && cur>0)
		{
			result[cur-1] += result[cur] / 10;
			result[cur] = result[cur] % 10;
			cur --; //从尾部向前移
		}
	}
	newcnt = ENDPOS-cur+1;
	result[0] = newcnt;
}

int* Power(int arr[], int n)
{	
	if(1 == n)
	{
		int effectnum = effectbit;
		int elen = ENDPOS;
		while(effectnum-- > 0)
		{
			temp[elen] = arr[elen];
			elen --;
		}
		return temp;
	}
	else
	{   
		Power(arr,--n);
		int  len = ENDPOS;

		int elen,ilen;
		elen = ilen = len;
		int  loopcnt = effectbit;

		while(loopcnt--)//此循环次数位输入数组的有效位数
		{               //需要循环每一位让其与目标数组的每一位进行乘法进位
			multiply(arr[len]); //将这值
			if(loopcnt > 0)
			{
				moveonebit(); //temp 进一位
			}
			len --;	
		}
		memcpy(temp,result,N*4); //更新下一次递归的temp值
		memset(result,0,N*4);    //将result清空,不清空则会与旧值累加，变成就阶乘的情况
		return temp;		
	}

}

int main()
{
	int array[N],n;
	cout << "calculate X^n!\n";
	cout << "input X :";
	char cNumber='\0';

	scanf("%c",&cNumber);
	int icnt = 0;
	int end = N-1;
	while(cNumber != '\n' && icnt++ < N)
	{
		array[end--] = cNumber - '0'; 
		scanf("%c",&cNumber);
	}
	if(icnt > 1) //处理 输入123 保存是从后保存的，所以变成321，现要在数组中改成实际输入状况
	{
		int tswap=0;
		int ix , jx;
		int wid = icnt;
		end = ENDPOS;
		for(ix=jx= ENDPOS-wid+1; (wid)/2 && ix<=ENDPOS ; ix++,end--,wid-=2)
		{
			tswap = array[ix];
			array[ix] = array[end];
			array[end] = tswap;
		}
	}

	cout << "input n :";
	cin >> n;
	if(n<=0)
	{
		cout << "n value must greate 0" <<endl;
		exit(-1);
	}

	int emp = N - icnt;
	for(int i=0; emp--; i++) //对空位进行标识
	{
		array[i] = -1;
	}

	for(i=1; i<N; i++)
	{
		temp[i] = 0;
	}

	array[0] = icnt; 
	temp[0]  = icnt;
        effectbit = icnt;

	Power(array,n);

	cout << endl << "X^n result is:" ;
	memcpy(result,temp,N*4);
	copy(result+(ENDPOS-result[0]+1),result+N,ostream_iterator<int>(cout," "));
	cout << endl;
	system("pause");
	return 0;
}

#2

google一下大数运算咯

一般都是用字符串来模拟大书运算了

#3

貌似大数求余也是个问题..

#4

2楼的代码我跑了下,才50^20000就没结果了?

#5

怕溢出就用大数运算 

#6

汗,只是给你个思路,不会一点都改不来吧

#7

我只需要把N改大点不就可以跑代码了吗?不用改它也应该可以出正确的结果啊,难道不是吗?我是想先在VC环境下测测这段代码能跑到什么程度...

#8

你是最后要实现(n^x)mod p吧?其实大可不必求出n^x,我这里有个不错的办法,(n^2)mod p=((n mod p)*n) mod p,类推,这样的话,就把运算的数量级从n^x降到了p*n的数量级.这样就好做了吧?甚至都可以不用大数乘法就可以实现.

#9

发现1楼和8楼结合起来,效果不错..哈哈.