llongint.cpp

应用编码与计算机密码学>程序 如果好的话请发言

LLongIntDivideLoop:
		//求出被除数的第一个双字的最高位的二进制0的个数
		mov ecx, 32
		mov edx, 0
		mov esi, 0x80000000
		mov edi, pDividendLLI2
		mov edi, [edi]
CalcDividendLZLoop:
		test esi, edi
		jnz CalcDividendLZOver
		inc edx
		shr esi, 1
		loop CalcDividendLZLoop
CalcDividendLZOver:
;//		mov dividendLZs, edx

;//被除数左移max(1, dividendLZs-divisorLZs)位
		mov ecx, 1
		;//mov edx, dividendLZs
		sub edx, divisorLZs
		cmp edx, 1
		jle DividendShiftLeft
		cmp edx, 32
		jb LessThan32Bits
		mov edx, 31
LessThan32Bits:
		mov ecx, edx
DividendShiftLeft:
		add shiftedBits, ecx
		mov edx, shiftedBits
		cmp edx, totalShiftBits
		jbe ShiftBitsOK
		sub shiftedBits, ecx
		mov edx, totalShiftBits
		sub edx, shiftedBits
		mov ecx, edx
		mov edx, totalShiftBits
		mov shiftedBits, edx
ShiftBitsOK:
		mov esi, pDividendLLI2
;//		cmp esi, pDividendLLI
;//		jb DividendShiftLeftOver
DividendShiftLeftLoop:
		mov edx, [esi]
		shld [esi+4], edx, cl
		sub esi, 4
		cmp esi, pDividendLLI
		jae DividendShiftLeftLoop
;//DividendShiftLeftOver:
		add esi, 4
		shl dword ptr [esi], cl

;//商左移max(1, dividendLZs-divisorLZs)位
;//QuotientShiftLeft:
		mov esi, pQuotient2
		cmp esi, pQuotient
		jbe QuotientShiftLeftOver
QuotientShiftLeftLoop:
		mov edx, [esi-4]
		shld [esi], edx, cl
		sub esi, 4
		cmp esi, pQuotient
		ja QuotientShiftLeftLoop
QuotientShiftLeftOver:
		shl dword ptr [esi], cl
;//比较被除数和除数的...位
		mov esi, pDividendLLI2
;//		add esi, 4
		cmp dword ptr [esi+4], 0
		ja SetQuotientTo1
;//		sub esi, 4
		mov ecx, [eax][lliLength]
		mov edi, pDivisorLLI2
CmpDividendDivisor2:
		mov edx, [esi]
		cmp edx, [edi]
		jb SetQuotientTo0
		ja SetQuotientTo1
		sub esi, 4
		sub edi, 4
		loop CmpDividendDivisor2
SetQuotientTo1:
		mov esi, pQuotient
		or dword ptr [esi], 1

;//substraction
		mov esi, pDividendLLI1
		mov edi, pDivisorLLI
		mov ecx, [eax][lliLength]
		push eax
		xor eax, eax
		clc
SubDivisorFromDividend:
		mov edx, [edi][eax*4]
		sbb [esi][eax*4], edx
		inc eax
		loop SubDivisorFromDividend
		sbb [esi][eax*4], 0
		pop eax
;//		jmp SetQuotientOver
SetQuotientTo0:
;//SetQuotientOver:
		mov ecx, shiftedBits
		cmp ecx, totalShiftBits
		jb LLongIntDivideLoop
	}
	remainder = LLongInt(pDividendLLI1, divisor.lliLength, dividend.sign);
	LLongInt rc(pQuotient, quotientLen, rSign);
	delete pQuotient;
	delete pDividendLLI;
	return rc;
}

//求b, 使得 (*this)*b ≡ 1 mod m
int LLongInt::ModRevert(LLongInt &m, LLongInt &result)
{
//S1:
	LLongInt n1 = m;
	LLongInt n2 = *this;
	LLongInt b1("0");
	LLongInt b2(1);
	LLongInt zero("0");
	LLongInt q, r, t;
//S2:
	q = Divide(n2, n1, r);
//S3:
	while (r != zero)
	{
		n1 = n2;
		n2 = r;
		t = b2;
		b2 = b1 - q * b2;
		b1 = t;
		q = Divide(n2, n1, r);
	}
//S4:
	if (n2 != LLongInt(1))
		return 0;
//S5:
	if (b2 < zero)
		b2 = b2 + m;
	result = b2;
	return 1;
}


//---------------------------------------------------------------------------------------------------
char* LLongInt::LLongInt2A(char *buff, int radix, char *radixSymbols)
{
	static char strRadixSymbols[16] = {'0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 
		'a', 'b', 'c', 'd', 'e', 'f'};
	if (radix <= 1)
		return NULL;
	if (radix > 16 && radixSymbols==NULL)
		return NULL;
	if (radix <=16 && radixSymbols==NULL)
		radixSymbols = strRadixSymbols;
	LLongInt zero((__int64)0);
	LLongInt divisor((__int64)radix);
	LLongInt quotient = *this;
	LLongInt remainder((__int64)0);
	int symbols = 0;
	char *pBuff;
	if (this->sign == 0)
		pBuff = buff;
	else
	{
		pBuff = buff + 1;
		buff[0] = '-';
	}
	if (quotient == zero)
	{
		pBuff[0] = radixSymbols[0];
		pBuff[1] = 0;
		return buff;
	}

	while (quotient != zero)
	{
		quotient = Divide(divisor, quotient, remainder);
		pBuff[symbols] = radixSymbols[remainder.pLLI[0]];
		symbols++;
	}
	pBuff[symbols] = 0;
	symbols--;
	int index = 0;
	char temp;
	while (index < symbols)
	{
		temp = pBuff[index];
		pBuff[index] = pBuff[symbols];
		pBuff[symbols] = temp;
		index++;
		symbols--;
	}
	return buff;
}

int LLongInt::IsPrime()
{
	int rc;
	int l;
	LLongInt m, b;
	unsigned int *pmLLI;
	if (lliLength==1 && pLLI[0]==1)  //*this == 1
		return 0;
	if (lliLength==1 && pLLI[0]==2)
		return 1;
	if (pLLI[0] %2 == 0)
		return 0;
	__asm
	{
		mov eax, this
		mov esi, [eax][pLLI]
;//		mov edx, [esi]
;//		test edx, 1
;//		jnz CalcLAndM
;//		mov rc, 0
;//		jmp rt				;//是偶数，肯定不是素数
CalcLAndM:					;//计算l，使得 *this-1 = 2^l * m
		and dword ptr [esi], 0xfffffffe			;//*this = *this - 1;
		mov dword ptr l, 0
		mov edi, esi   ;//&(this->pLLI[0])
		
CalcLLoop:
		mov edx, [edi]
		cmp edx, 0
		jz LAdd32
		mov ecx, 32
CalcLLastDWord:
		shr edx, 1
		jc CalcLAdd
		loop CalcLLastDWord
CalcLAdd:
		add l, 32
		sub l, ecx
		jmp CalcLOver
LAdd32:
		add l, 32
		add edi, 4
		jmp CalcLLoop
CalcLOver:
		;//or dword ptr [esi], 1			;//*this = *this + 1
	}
	int mLLILength = lliLength - l/32;
	pmLLI = new unsigned int[mLLILength];
	__asm			;//计算使得 *this-1 = 2^l * m   的 m
	{
		mov edx, l
		shr edx, 5		;//edx = edx / 32
		shl edx, 2		;//edx = edx * 4

		mov eax, this
		mov esi, [eax][pLLI]
		add esi, edx
		
		mov edi, pmLLI
		mov ecx, [eax][lliLength]
		shr edx, 2
		sub ecx, edx
		push edi
		push ecx
		cld
		rep movsd
		pop edx
		pop edi

		mov ecx, l
		and ecx, 31		;//(31)d = (11111)b   这里等价于  edx = l % 32
MLLIShiftLeft:
		dec edx
		jz MLLIShiftLeftOver
		mov eax, [edi+4]
		shrd [edi], eax, cl
		add edi, 4
		jmp MLLIShiftLeft
MLLIShiftLeftOver:
		shr dword ptr [edi], cl
		;//恢复*this
		mov eax, this
		mov esi, [eax][pLLI]
		or dword ptr [esi], 1			;//*this = *this + 1
	}

	m = LLongInt(pmLLI, mLLILength, sign);
	delete pmLLI;
	int randomInt, a;
Miller_RabinTest:
	__asm		;//取得32位“随机”数
	{
		rdtsc

		mov ebx, eax
		xor bh, al
		mov dh, bh
		ror ebx, 8
		xor bh, dh
		ror ebx, 8
		xor bh, dh
		ror ebx, 16
		mov randomInt, ebx

/*
		mov bx, ax
		ror ebx, 16
		mov bx, ax
*/
	}
//	randomInt = 2;
	b = *this;
	unsigned int *pbLLI = b.pLLI;
	__asm
	{
		mov eax, this
		mov ecx, [eax][lliLength]
		mov edi, pbLLI
		mov edx, randomInt
XorBLLI:
		xor [edi], edx
		mov edx, [edi]
		add edi, 4
		loop XorBLLI

		sub edi, 4
		mov esi, [eax][pLLI]
		mov ecx, [eax][lliLength]
		dec ecx
		shl ecx, 2
		add esi, ecx
		mov edx, [esi]
//		mov esi, [eax][pLLI]
//		and dword ptr [esi], 0xfffffffe
BLLIDiv2:
		cmp [edi], edx
		jb BLLIDiv2Over
		shr dword ptr [edi], 1
		jmp BLLIDiv2
BLLIDiv2Over:
		
//		or dword ptr [esi], 1
	}

	b.Trim();

	if (b.lliLength==1 && (b.pLLI[0]==0 || b.pLLI[0]==1))
		b.pLLI[0] = 2;
	else
	if (b.lliLength==1 && lliLength==1 && b.pLLI[0]>=(pLLI[0]-1))
		b.pLLI[0] = pLLI[0] / 32;


	//b = LLongInt(2);

	LLongInt thisMinus1 = *this - LLongInt(1);
	LLongInt gap = (thisMinus1 - LLongInt(1) - b) / LLongInt(100);
	LLongInt v;
	int i;
	rc = 1;
	for (a=0; a<100; a++)
	{
S1:
		v = b.ExpMod(m, *this);
S2:
		if (v.lliLength==1 && v.pLLI[0]==1)
			goto S7;
S3:
		i = 1;
S4:
		if (v == thisMinus1)
			goto S7;
S5:
		if (i == l)
		{
			rc = 0;
			break;
		}
S6:
		v = (v * v) % *this;
		i = i + 1;
		goto S4;
S7:
		b = b + gap;
	}
rt:
	return rc;
}

//模幂乘算法, 计算 *this ^ e mod n
LLongInt LLongInt::ExpMod(LLongInt e, LLongInt n)
{

	//汇编算法
	//m = *this		计算 m ^ e mod n
	int a, totalBits, nowBit, nowDW, testBits;
	LLongInt *pE = &e;
	LLongInt c(1);
	LLongInt m = *this;
	__asm
	{
	//计算e共有多少个二进制位
		mov eax, pE
		mov edx, [eax][lliLength]
		mov edi, edx
		shl edx, 5   ;//*32
		dec edi
		shl edi, 2   ;//*4

		mov ecx, 32
		mov esi, 0x80000000
		add edi, [eax][pLLI]
		mov edi, [edi]
CalcLZ:
		test esi, edi
		jnz CalcLZOver
		dec edx
		shr esi, 1
		loop CalcLZ
CalcLZOver:
		mov totalBits, edx
		mov dword ptr nowBit, 0
	}

	while (nowBit < totalBits)
	{
		__asm
		{
			mov esi, nowBit
			shr esi, 5    ;// /32
			shl esi, 2    ;// *4
			mov eax, pE
			add esi, [eax][pLLI]
			mov edx, [esi]
			mov nowDW, edx
			mov edx, totalBits
			sub edx, nowBit
			mov testBits, edx
			cmp edx, 32
			jbe TestHighestDWord
			;//mov testBits, 32
			jmp TestLowerDWords
		}
TestHighestDWord:
		for (a=0; a<testBits; a++)
		{
			__asm
			{
				test dword ptr nowDW, 1
				jz eDivide2
				;//and dword ptr nowDW, 0xfffffffe
			}
			c = ( m * c ) % n;
			__asm
			{
				mov edx, totalBits
				sub edx, nowBit
				cmp edx, 1
				jbe ExpModOver
			}
eDivide2:
			__asm	shr dword ptr nowDW, 1
			m = (m * m) % n;
			__asm	inc nowBit
		}

TestLowerDWords:
		for (a=0; a<32; a++)
		{
			__asm
			{
				test dword ptr nowDW, 1
				jz eDivide2_2
				;//and dword ptr nowDW, 0xfffffffe
			}
			c = ( m * c ) % n;
eDivide2_2:
			__asm	shr dword ptr nowDW, 1
			m = (m * m) % n;
			__asm	inc nowBit
		}
	}

ExpModOver:
	return c;


/*
	//C++算法
	LLongInt c(1);
	LLongInt m = *this;
	LLongInt zero((__int64)0);
	LLongInt one(1);
	LLongInt two(2);
	while ( e != zero)
	{
		if ( ( e % two ) == zero )
		{
			e = e / two;
			m = ( m * m ) % n;
		}
		else
		{
			e = e - one;
			c = ( m * c ) % n;
		}
	}
	return c;
*/

}

unsigned int* LLongInt::GetBuff()
{
	return pLLI;
}

int LLongInt::GetBuffLength()
{
	return lliLength;
}

int LLongInt::GetSign()
{
	return sign;
}