ĐẠI HỌC CÔNG NGHỆ - ĐHQG HÀ NỘI
KHOA CÔNG NGHỆ THÔNG TIN
BÀI TẬP LỚN
MÔN HỌC: AN NINH CƠ SỞ DỮ LIỆU
ĐỀ TÀI:
VẤN ĐỀ TÍNH TOÁN VỚI CÁC SỐ LỚN
Giảng viên hướng dẫn: PGS.TS Trịnh Nhật Tiến
Người thực hiện: Nguyễn Thị Chi
1
I.Giới thiệu
Vấn đề tính toán với các số lớn có ý nghĩa rất lớn trong thực tế. Chẳng hạn như thuật
toán mã hóa công khai RSA (do Rivers, Shamir và Adleman viết ra vào năm 1978 ) sử
dụng tới 512 số khóa (thuật toán này có liên quan tới việc phân tích các số nguyên tố).
Trong nhiều ngành khoa học kĩ thuật chúng ta phải sử dụng tới các con số lớn hơn thế
rất nhiều.
Một số vấn đề liên quan tới việc tính toán với các số lớn như: kiểm tra tính nguyên
tố của một số lớn , khai căn bậc hai của số lớn, vấn đề tính lũy thừa với số lớn theo
modulo, vấn đề tính phần tử nghịch đảo theo modulo, vấn đề tính giai thừa số lớn, vấn
đề các phép toán trên số lớn…
Đặt Vấn Đề:
2
Trong các ngôn ngữ lập trình cấp cao như Pascal, C, C#, … hỗ trợ kiểu dữ liệu số
nguyên và các phép toán trên số học. Nhưng, độ lớn của chữ số có giới hạn. Trong
Pascal, một số nguyên được lưu trữ tối đa là 32 bit (4 byte), trong C# là 64 bit (8 byte).
Do đó, để có thể thực hiện được các phép toán số học với các số lớn vượt ra khỏi giới
hạn kiểu dữ liệu số của ngôn ngữ lập trình, người lập trình cần xây dựng riêng cho
mình một cấu trúc dữ liệu có thể lưu được số lớn, và các phép toán số học trên cấu trúc
dữ liệu đó. Sau đây, em xin trình bày một phương pháp xây dựng số lớn và các phép
toán số học trên số lớn trên C#.
II. Bài toán
1. Phát biểu bài toán

else if(posVal >= 'A' && posVal <= 'Z')
posVal = (posVal - 'A') + 10;
else
posVal = 9999999; // arbitrary large
if(posVal >= radix)
throw(new ArithmeticException("Invalid string in constructor."));
else
{
if(value[0] == '-')
posVal = -posVal;
result = result + (multiplier * posVal);
if((i - 1) >= limit)
multiplier = multiplier * radix;
}
}
if(value[0] == '-') // negative values
{
if((result.data[maxLength-1] & 0x80000000) == 0)
4
throw(new ArithmeticException("Negative underflow in
constructor."));
}
else // positive values
{
if((result.data[maxLength-1] & 0x80000000) != 0)
throw(new ArithmeticException("Positive overflow in
constructor."));
}
data = new uint[maxLength];
for(int i = 0; i < result.dataLength; i++)

result.data[i] = (uint)(sum & 0xFFFFFFFF);
}
if(carry != 0 && result.dataLength < maxLength)
{
result.data[result.dataLength] = (uint)(carry);
result.dataLength++;
}
while(result.dataLength > 1 && result.data[result.dataLength-1] == 0)
result.dataLength ;
// overflow check
int lastPos = maxLength - 1;
if((bi1.data[lastPos] & 0x80000000) == (bi2.data[lastPos] & 0x80000000)
&&
(result.data[lastPos] & 0x80000000) != (bi1.data[lastPos] & 0x80000000))
{
throw (new ArithmeticException());
}
return result;
2.2.2. Phép toán trừ
- Thực hiên trong mỗi một block và thực hiện trừ như phép trừ bình thường.
- Sử dụng một biến carry để lưu trữ biến nhớ:
+ Nếu kết quả nhỏ hơn không: carry=1
+ Ngược lại: carry=0.
- Kết quả của phần tử thứ i sẽ là:
long diff = (long)bi1.data[i] - (long)bi2.data[i] -carry;
result.data[i] = (uint)(diff & 0xFFFFFFFF);
- Thủ tuc thực hiện như sau:
6
public static BigInteger operator -(BigInteger bi1, BigInteger bi2)
{

throw (new ArithmeticException());
}
7
return result;
}
2.2.3. Phép nhân
- Nhân từng phần tử của số b với số a, kết quả thu được lưu vào trong mang data[k].
- Kết quả mỗi phần tử thứ i được xác định bởi công thức như sau:
ulong Val= bi1.data[i]*bi2.data[j]+ result.data[k]+mcarry;
rusult.data[k]= (unit)(Val&0xFFFFFFFF)
mcarry=(val>>32)
- Thủ tục thực hiện như sau:
public static BigInteger operator *(BigInteger bi1, BigInteger bi2)
{
int lastPos = maxLength-1;
bool bi1Neg = false, bi2Neg = false;
// take the absolute value of the inputs
try
{
if((bi1.data[lastPos] & 0x80000000) != 0) // bi1 negative
{
bi1Neg = true; bi1 = -bi1;
}
if((bi2.data[lastPos] & 0x80000000) != 0) // bi2 negative
{
bi2Neg = true; bi2 = -bi2;
}
}
catch(Exception) {}
BigInteger result = new BigInteger();

if((result.data[lastPos] & 0x80000000) != 0)
{
if(bi1Neg != bi2Neg && result.data[lastPos] == 0x80000000) //
different sign
{
// handle the special case where multiplication produces
// a max negative number in 2's complement.
if(result.dataLength == 1)
return result;
else
{
bool isMaxNeg = true;
for(int i = 0; i < result.dataLength - 1 && isMaxNeg; i++)
{
if(result.data[i] != 0)
isMaxNeg = false;
9
}
if(isMaxNeg)
return result;
}
}
throw(new ArithmeticException("Multiplication overflow."));
}
// if input has different signs, then result is -ve
if(bi1Neg != bi2Neg)
return -result;
return result;
}
2.2.4. Phép chia

//Console.WriteLine("divisor = " + bi2 + "\ndividend = " + bi1);
if(dividend >= divisor)
{
ulong quotient = dividend / divisor;
result[resultPos++] = (uint)quotient;
outRemainder.data[pos] = (uint)(dividend % divisor);
}
pos ;
while(pos >= 0)
{
//Console.WriteLine(pos);
dividend = ((ulong)outRemainder.data[pos+1] << 32) +
(ulong)outRemainder.data[pos];
ulong quotient = dividend / divisor;
result[resultPos++] = (uint)quotient;
outRemainder.data[pos+1] = 0;
outRemainder.data[pos ] = (uint)(dividend % divisor);
//Console.WriteLine(">>>> " + bi1);
}
outQuotient.dataLength = resultPos;
int j = 0;
for(int i = outQuotient.dataLength - 1; i >= 0; i , j++)
outQuotient.data[j] = result[i];
for(; j < maxLength; j++)
11
outQuotient.data[j] = 0;
while(outQuotient.dataLength > 1 &&
outQuotient.data[outQuotient.dataLength-1] == 0)
outQuotient.dataLength ;
if(outQuotient.dataLength == 0)

bi2 = bi2 << shift;
/*
Console.WriteLine("bi1 Len = {0}, bi2 Len = {1}", bi1.dataLength,
bi2.dataLength);
Console.WriteLine("dividend = " + bi1 + "\ndivisor = " + bi2);
for(int q = remainderLen - 1; q >= 0; q )
Console.Write("{0:x2}", remainder[q]);
Console.WriteLine();
*/
int j = remainderLen - bi2.dataLength;
int pos = remainderLen - 1;
ulong firstDivisorByte = bi2.data[bi2.dataLength-1];
ulong secondDivisorByte = bi2.data[bi2.dataLength-2];
int divisorLen = bi2.dataLength + 1;
uint[] dividendPart = new uint[divisorLen];
while(j > 0)
{
ulong dividend = ((ulong)remainder[pos] << 32) +
(ulong)remainder[pos-1];
//Console.WriteLine("dividend = {0}", dividend);
ulong q_hat = dividend / firstDivisorByte;
ulong r_hat = dividend % firstDivisorByte;
//Console.WriteLine("q_hat = {0:X}, r_hat = {1:X}", q_hat, r_hat);
bool done = false;
while(!done)
{
done = true;
if(q_hat == 0x100000000 ||
(q_hat * secondDivisorByte) > ((r_hat << 32) + remainder[pos-
2]))

*/
result[resultPos++] = (uint)q_hat;
pos ;
j ;
}
outQuotient.dataLength = resultPos;
int y = 0;
14
for(int x = outQuotient.dataLength - 1; x >= 0; x , y++)
outQuotient.data[y] = result[x];
for(; y < maxLength; y++)
outQuotient.data[y] = 0;
while(outQuotient.dataLength > 1 &&
outQuotient.data[outQuotient.dataLength-1] == 0)
outQuotient.dataLength ;
if(outQuotient.dataLength == 0)
outQuotient.dataLength = 1;
outRemainder.dataLength = shiftRight(remainder, shift);
for(y = 0; y < outRemainder.dataLength; y++)
outRemainder.data[y] = remainder[y];
for(; y < maxLength; y++)
outRemainder.data[y] = 0;
15