[原创] RSA加密源代码

[这个贴子最后由x86在 2005/03/23 01:09pm 第 1 次编辑]

为了方便大家，我已经打包上传了，在visual c++6.0编译通过！！！！

#ifndef STACK_H
#define STACK_H
class node{
public:
unsigned char c;
node* next;
node(char cc,node* n=NULL){c=cc;next=n;}
node(node* n=NULL){next=n;}
};
class stack:public node{
private:
node* head;
int length;
public:
stack(){head=NULL;length = 0;}
~stack()
{
node* temp;
while(head!=NULL)
{
temp=head;
head=head->next;
delete head;
}
}
void push(const unsigned char& cc)
{
node* temp;
temp=head;
head=new node(cc,temp);
++length;
}
bool pop(unsigned char& cc)
{
if(head==NULL)
return false;
node* temp;
temp=head;
head=head->next;
cc=temp->c;
delete temp;
--length;
return true;
}
int getLength()
{
return length;
}
};
#endif

[ 本帖最后由 chinanic 于 2007-8-25 13:43 编辑 ]

x86 该用户已被删除

沙发

x86发表于 2005-3-22 19:55 | 只看该作者

RSA加密源代码

#ifndef INTNODE_H
#define INTNODE_H
class intNode{
public:
unsigned int num;
intNode *next;
intNode();
intNode(unsigned int para);
intNode(unsigned int para, intNode* p);
intNode(intNode* p);
~intNode();
void* operator new(size_t);
void operator delete(void*);
void clear();
private:
static intNode* freelist;
};
intNode* intNode::freelist = NULL;
//constructor implement
intNode::intNode()
{
num = 0;
next = NULL;
}
intNode::intNode(unsigned int para)
{
num = para;
next = NULL;
}
intNode::intNode(unsigned int para, intNode* p)
{
num = para;
next = p;
}
intNode::intNode(intNode* p)
{
num = 0;
next = p;
}
//disconstruct
intNode::~intNode()
{}
//overload for new operator
void* intNode::operator new(size_t)
{
if(freelist == NULL)
return ::new intNode;//Create space
intNode* temp;//can take from freelist
temp = freelist;
freelist = freelist->next;
return temp;//return the link
}
//over load for delete operator
void intNode::operator delete(void* ptr)
{
((intNode*) ptr)->next = freelist;//put on freelist
freelist = (intNode*) ptr;
}
//delete the freelist
void intNode::clear()
{
intNode* temp;
temp = freelist;
while(freelist != NULL)
{
temp = freelist;
freelist = freelist->next;
::delete temp;
}
}
#endif

复制代码

[ 本帖最后由 chinanic 于 2007-8-25 13:43 编辑 ]

TOP

x86 该用户已被删除

板凳

x86发表于 2005-3-22 19:56 | 只看该作者

RSA加密源代码

#if !defined DESPROCESS_H
#define DESPROCESS_H
#if _MSC_VER > 1000
#pragma once
#endif//_MSC > 1000
#include<iostream>
#include<string>
#include<iomanip>
#include<cstdio>
using namespace std;
const static int maxlen = 60000;
//IP
const static int ip[64] = {
58, 50, 42, 34, 26, 18, 10, 2,
60, 52, 44, 36, 28, 20, 12, 4,
62, 54, 46, 38, 30, 22, 14, 6,
64, 56, 48, 40, 32, 24, 16, 8,
57, 49, 41, 33, 25, 17, 9, 1,
59, 51, 43, 35, 27, 19, 11, 3,
61, 53, 45, 37, 29, 21, 13, 5,
63, 55, 47, 39, 31, 23, 15, 7};
//the reverse of IP
const static int fp[64] = {
40, 8, 48, 16, 56, 24, 64, 32,
39, 7, 47, 15, 55, 23, 63, 31,
38, 6, 46, 14, 54, 22, 62, 30,
37, 5, 45, 13, 53, 21, 61, 29,
36, 4, 44, 12, 52, 20, 60, 28,
35, 3, 43, 11, 51, 19, 59, 27,
34, 2, 42, 10, 50, 18, 58, 26,
33, 1, 41, 9, 49, 17, 57, 25};
//E matrix
const static int e[48] = {
32, 1, 2, 3, 4, 5,
4, 5, 6, 7, 8, 9,
8, 9, 10, 11, 12, 13,
12, 13, 14, 15, 16, 17,
16, 17, 18, 19, 20, 21,
20, 21, 22, 23, 24, 25,
24, 25, 26, 27, 28, 29,
28, 29, 30, 31, 32, 1};
//S box
const static int sbox[8][64] = {
//S1
14, 4, 13, 1, 2, 15, 11, 8,
3, 10, 6, 12, 5, 9, 0, 7,
0, 15, 7, 4, 14, 2, 13, 1,
10, 6, 12, 11, 9, 5, 3, 8,
4, 1, 14, 8, 13, 6, 2, 11,
15, 12, 9, 7, 3, 10, 5, 0,
15, 12, 8, 2, 4, 9, 1, 7,
5, 11, 3, 14, 10, 0, 6, 13,
//S2
15, 1, 8, 14, 6, 11, 3, 4,
9, 7, 2, 13, 12, 0, 5, 10,
3, 13, 4, 7, 15, 2, 8, 14,
12, 0, 1, 10, 6, 9, 11, 5,
0, 14, 7, 11, 10, 4, 13, 1,
5, 8, 12, 6, 9, 3, 2, 15,
13, 8, 10, 1, 3, 15, 4, 2,
11, 6, 7, 12, 0, 5, 14, 9,
//S3
10, 0, 9, 14, 6, 3, 15, 5,
1, 13, 12, 7, 11, 4, 2, 8,
13, 7, 0, 9, 3, 4, 6, 10,
2, 8, 5, 14, 12, 11, 15, 1,
13, 6, 4, 9, 8, 15, 3, 0,
11, 1, 2, 12, 5, 10, 14, 7,
1, 10, 13, 0, 6, 9, 8, 7,
4, 15, 14, 3, 11, 5, 2, 12,
//S4
7, 13, 14, 3, 0, 6, 9, 10,
1, 2, 8, 5, 11, 12, 4, 15,
13, 8, 11, 5, 6, 15, 0, 3,
4, 7, 2, 12, 1, 10, 14, 9,
10, 6, 9, 0, 12, 11, 7, 13,
15, 1, 3, 14, 5, 2, 8, 4,
3, 15, 0, 6, 10, 1, 13, 8,
9, 4, 5, 11, 12, 7, 2, 14,
//S5
2, 12, 4, 1, 7, 10, 11, 6,
8, 5, 3, 15, 13, 0, 14, 9,
14, 11, 2, 12, 4, 7, 13, 1,
5, 0, 15, 10, 3, 9, 8, 6,
4, 2, 1, 11, 10, 13, 7, 8,
15, 9, 12, 5, 6, 3, 0, 14,
11, 8, 12, 7, 1, 14, 2, 13,
6, 15, 0, 9, 10, 4, 5, 3,
//S6
12, 1, 10, 15, 9, 2, 6, 8,
0, 13, 3, 4, 14, 7, 5, 11,
10, 15, 4, 2, 7, 12, 9, 5,
6, 1, 13, 14, 0, 11, 3, 8,
9, 14, 15, 5, 2, 8, 12, 3,
7, 0, 4, 10, 1, 13, 11, 6,
4, 3, 2, 12, 9, 5, 15, 10,
11, 14, 1, 7, 6, 0, 8, 13,
//S7
4, 11, 2, 14, 15, 0, 8, 13,
3, 12, 9, 7, 5, 10, 6, 1,
13, 0, 11, 7, 4, 9, 1, 10,
14, 3, 5, 12, 2, 15, 8, 6,
1, 4, 11, 13, 12, 3, 7, 14,
10, 15, 6, 8, 0, 5, 9, 2,
6, 11, 13, 8, 1, 4, 10, 7,
9, 5, 0, 15, 14, 2, 3, 12,
//S8
13, 2, 8, 4, 6, 15, 11, 1,
10, 9, 3, 14, 5, 0, 12, 7,
1, 15, 13, 8, 10, 3, 7, 4,
12, 5, 6, 11, 0, 14, 9, 2,
7, 11, 4, 1, 9, 12, 14, 2,
0, 6, 10, 13, 15, 3, 5, 8,
2, 1, 14, 7, 4, 10, 8, 13,
15, 12, 9, 0, 3, 5, 6, 11
};
//P
const static int p[32] = {
16, 7, 20, 21,
29, 12, 28, 17,
1, 15, 23, 26,
5, 18, 31, 10,
2, 8, 24, 14,
32, 27, 3, 9,
19, 13, 30, 6,
22, 11, 4, 25,
};
//PC--1
const static int pc1[56] = {
57, 49, 41, 33, 25, 17, 9,
1, 58, 50, 42, 34, 26, 18,
10, 2, 59, 51, 43, 35, 27,
19, 11, 3, 60, 52, 44, 36,
63, 55, 47, 39, 31, 23, 15,
7, 62, 54, 46, 38, 30, 22,
14, 6, 61, 53, 45, 37, 29,
21, 13, 5, 28, 20, 12, 4
};
//the digit every circle should left move
const static int ls[16] = {
1, 1, 2, 2, 2, 2, 2, 2, 1, 2, 2, 2, 2, 2, 2, 1};
//PC--2
const static int pc2[48] = {
14, 17, 11, 24, 1, 5,
3, 28, 15, 6, 21, 10,
23, 19, 12, 4, 26, 8,
16, 7, 27, 20, 13, 2,
41, 52, 31, 37, 47, 55,
30, 40, 51, 45, 33, 48,
44, 49, 39, 56, 34, 53,
46, 42, 50, 36, 29, 32
};
class DESProcess
{
public:
DESProcess();
~DESProcess();
void setBits(const unsigned int& r, const unsigned int& l);
void setKey(const unsigned int& r, const unsigned int& l);
//the desEnCode() function read prlaintext in the form
//of charactors from the M file and write the cryphcoraphy in the form of
//integer to the C File.
//the desDeCode() is just reverse.
void desEnCode();
void desDeCode();
void outputBits(unsigned int& r, unsigned int& l);
private:
char mch[8];
bool bits[64];
bool constkey[64];
bool key[64];
bool tkey[48];
unsigned int right, left;
void desCoding(bool enCoding);
void intToBit();
void bitToInt();
void ipBits();
void reverseBits();
void DiffBits();
void fpBits();
void pc_1Key();
void lsKey(int length);
void BitsToKey();
void pc_2Key();
void sBoxKey();
void pKey();
};
#include"DESProcess.cpp"
#endif

复制代码

[ 本帖最后由 chinanic 于 2007-8-25 13:42 编辑 ]

TOP

x86 该用户已被删除

地板

x86发表于 2005-3-22 19:58 | 只看该作者

RSA加密源代码

//the implementation of the DESProcess class
//construct and desconstruct of the DESProcess
DESProcess:ESProcess()
{
//give defalute value to every member
for(int i = 0; i < 8; i++)
mch = ';#';;
for(i = 0; i < 64; i++)
{
bits = false;
key = false;
constkey = false;
if(i < 48)
tkey = false;
}
right = left = 0;
}
DESProcess::~DESProcess()
{
}
void DESProcess::setBits(const unsigned int& r, const unsigned int& l)
{
right = r;
left = l;
}
void DESProcess::setKey(const unsigned int& r, const unsigned int& l)
{
right = r;
left = l;
intToBit();
for(int i = 0; i < 64; ++i)
constkey = bits;
}
void DESProcess::desEnCode()
{
intToBit();
desCoding(true);
bitToInt();
}
void DESProcess::desDeCode()
{
intToBit();
desCoding(false);
bitToInt();
}
void DESProcess:utputBits(unsigned int& r, unsigned int& l)
{
bitToInt();
r = right;
l = left;
}
void DESProcess::intToBit()
{
unsigned int con = 0x80000000; //the power of 2;
int i; //circle variable;
for(i = 0; i < 32; ++i)
{
if((con & right) != 0)
bits = true;
else
bits = false;
con >>= 1;
}
con = 0x80000000;
for(; i < 64; ++i)
{
if((con & left) != 0)
bits = true;
else
bits = false;
con >>= 1;
}
}
void DESProcess::bitToInt()
{
int i;
right = 0;
for(i = 0; i < 32; ++i)
{
right <<= 1;
if(bits)
right += 1;
}
left = 0;
for(; i < 64; ++i)
{
left <<= 1;
if(bits)
left += 1;
}
}
//descoding process
void DESProcess::desCoding(bool enCoding)
{
ipBits();
int i;//cicle variable
for(i = 0; i < 64; ++i)
key = constkey;
pc_1Key();
int sum = 0;
for(i = 0; i < 16; ++i)
sum += ls;
if(! enCoding)
lsKey(sum);
else
lsKey(ls[0]);
for(i = 0; i < 16; ++i)
{
BitsToKey();
pc_2Key();
sBoxKey();
pKey();
DiffBits();
if(i < 15)
{
if(enCoding)
lsKey(ls[i + 1]);
else
lsKey(0 - ls[15 - i]);
reverseBits();
}
}
fpBits();
}
//IP Permute
void DESProcess::ipBits()
{
bool temp[64];
for(int i = 0; i < 64; ++i)
temp = bits;
for(i = 0; i < 64; ++i)
bits = temp[ip - 1];
}
//exchange the front and tail
void DESProcess::reverseBits()
{
bool temp[32];
for(int i = 0; i < 32; ++i)
{
temp = bits;
bits = bits[32 + i];
bits[32 + i] = temp;
}
}
//Bits and tkey different or
void DESProcess:iffBits()
{
for(int i = 0; i < 32; ++i)
bits = ( (! bits) && tkey) || ( (! tkey) && bits);
}
//ip';s contradictory permulate
void DESProcess::fpBits()
{
bool temp[64];
for(int i = 0; i < 64; ++i)
temp = bits;
for(i = 0; i < 64; ++i)
bits = temp[fp - 1];
}
//pc-1 permulate
void DESProcess::pc_1Key()
{
bool temp[64];
for(int i = 0; i < 64; ++i)
temp = key;
for(i = 0; i < 56; ++i)
key = temp[pc1 - 1];
}
//left shift the key with parameter length
void DESProcess::lsKey(int length)
{
bool temp[28];
int i;//circle variable
length = length + 28;
for(i = 0; i < 28; ++i)
temp = key;
for(i = 0; i < 28; ++i)
key = temp[(i + length) % 28];
for(i = 0; i < 28; ++i)
temp = key[28 + i];
for(i = 0; i < 28; ++i)
key[28 + i] = temp[(i + length) % 28];
}
//expand the right part to the tkey
void DESProcess::BitsToKey()
{
for(int i = 0; i < 48; ++i)
tkey = bits[31 + e];
}
//pc_2 permulate and different or
void DESProcess::pc_2Key()
{
for(int i = 0; i < 48; ++i)
tkey = ((! tkey) && key[pc2 - 1]) || ((! key[pc2 - 1]) && tkey);
}
//sBox permulate the key
void DESProcess::sBoxKey()
{
const int pow_2[4] = {1, 2, 4, 8};
int i,j;
bool temp[48];
for(i = 0; i < 48; ++i)
temp = tkey;
int tempint;
for(i = 0; i < 8; ++i)
{
tempint = 0;
for(j = 0; j < 4; ++j)
if(temp[i * 6 + 4 - j])
tempint += pow_2[j];
if(temp[i * 6 + 5])
tempint += 16;
if(temp[i*6])
tempint += 32;
tempint = sbox[tempint];
for(j = 0; j < 4; ++j) //number change to tkey
tkey[i * 4 + j] = ((tempint & pow_2[3 - j]) != 0);
} //end of for{}
}
//p permulate
void DESProcess::pKey()
{
bool temp[32];
for(int i = 0; i < 32; ++i)
temp = tkey;
for(i = 0; i < 32; ++i)
tkey = temp[ p - 1];
}

复制代码

[ 本帖最后由 chinanic 于 2007-8-25 13:42 编辑 ]

TOP

x86 该用户已被删除

5楼

x86发表于 2005-3-22 20:00 | 只看该作者

RSA加密源代码

#ifndef PREDEFINE_H
#define PREDEFINE_H
#include<cmath>
#include"stack.h"
#include"intNode.h"
const unsigned int FULL = 0xFFFFFFFF;
const unsigned int MAXDEC = 1000000000;
const static unsigned char HArray[] = {';0';, ';1';, ';2';, ';3';, ';4';, ';5';, ';6';, ';7';, ';8';, ';9';,
';A';, ';B';, ';C';, ';D';, ';E';, ';F';};
const static unsigned int sta_p[] = {2, 7, 3, 5, 97, 39, 3, 37, 1109, 1877};
const static unsigned int r_laimda = 0x48c27395;
const static unsigned int r_c = 23;
const static double r_M = 100000000.;
const static double r_MM = 30000000.;
const static double r_cc = 113.;
const static double r_l = 8.;
unsigned int hdigit(unsigned char c)
{
unsigned char hi,lo;
hi = c >> 4;
lo = c & 0x0f;
if(hi == 0x04)
return (int)(lo + 0x09);
if(hi == 0x06)
return (int)(lo + 0x09);
return (unsigned int)lo;
}
void multi(const unsigned int& p1,const unsigned int& p2, unsigned int& high, unsigned int& low)
{
unsigned int h1;
unsigned int h2;
unsigned int l1;
unsigned int l2;
h1 = (p1 >> 16);
h2 = (p2 >> 16);
l1 = (p1 & 0xFFFF);
l2 = (p2 & 0xFFFF);
high = h1 * h2;
low = l1 * l2;
unsigned int temp;
unsigned int re;
temp = h1 * l2;
re = ((temp & 0xFFFF) << 16);
high += (temp >> 16);
temp = h2 * l1;
re += ((temp & 0xFFFF) << 16);
if(re < ((temp & 0xFFFF) << 16))
++high;
high += temp >> 16;
low += re;
if(low < re)
++high;
}
intNode* backToFront(intNode* p)
{
intNode* t1 = NULL;
intNode* t2;
while(p != NULL)
{
t2 = p->next;
p->next = t1;
t1 = p;
p = t2;
}
return t1;
}
int FindZeroBit(unsigned int num)
{
int cc = FULL >> 4;
int Fbit = 3;
while(num < cc)
{
cc >>= 4;
Fbit += 4;
}
cc = FULL >> Fbit;
while((cc & num) != num)
{
--Fbit;
cc = FULL >> Fbit;
}
return Fbit;
}
bool TheLastNode(intNode*& t)
{
if(t == NULL)
return false;
while(t->next != NULL)
t = t->next;
return true;
}
#endif

复制代码

[ 本帖最后由 chinanic 于 2007-8-25 13:42 编辑 ]

TOP

x86 该用户已被删除

6楼

x86发表于 2005-3-22 20:01 | 只看该作者

RSA加密源代码

#ifndef BIGINT_H
#define BIGINT_H
#include"predefine.h"
class BigInt{
public:
BigInt();
~BigInt();
void setZero();
void loadDEC(const char* str, const int length);//
void loadHEX(const char* str, const int length);//
void loadSTR(const char* str, const int length);
char* outputDEC(int& length);
char* outputHEX(int& length);
char* outputSTR(int& length);
BigInt operator + (const BigInt& p) const;
BigInt operator + (const unsigned int& p) const;
BigInt operator - (const BigInt& p) const;
BigInt operator - (const unsigned int& p) const;
BigInt operator * (const BigInt& p) const;
BigInt operator * (const unsigned int& p) const;
BigInt operator / (const BigInt& p);
BigInt operator / (const unsigned int& p);
BigInt operator % (const BigInt& p) const;
unsigned int operator % (const unsigned int& p) const;
bool operator > (const BigInt& p) const;
bool operator > (const unsigned int p) const;
bool operator == (const BigInt& p) const;
bool operator != (const BigInt& p) const;
BigInt& operator <<= (int iBit);
BigInt& operator >>= (int iBit);
BigInt& operator += (const unsigned int& p);
BigInt& operator = (const BigInt& p);
BigInt& operator = (const unsigned int& p);
BigInt& operator ++ ();
BigInt& operator -- ();
bool BIlisZero() const;
int BICompareABS(const BigInt& p) const;
int BICompareABS(const unsigned int& p) const;
BigInt BIdivision(const BigInt& p, BigInt& pr);
unsigned int getLast32Bit();
void copy(const BigInt& p);
void add(const BigInt& p, BigInt& temp) const;
void minuse(const BigInt& p, BigInt& temp) const;
void add(const unsigned int& p,BigInt& temp) const;
void minuse(const unsigned int& p,BigInt& temp) const;
void clear();
void MakeClose(BigInt& p);
BigInt BIinverse(const BigInt& p) const;
int nodeNumber() const;
intNode* getHead() const;
void print(int choose);
//void MakeModMultTable(const BigInt& pp);
//BigInt MontMult(const BigInt& p1, const BigInt& p2, const BigInt pp);
//BigInt MontExpo(const BigInt& p1, const BigInt& p2, const BigInt pp);
private:
intNode* head;
bool positive;
friend BigInt BIgcd(const BigInt& p1, const BigInt& p2);
friend void BIswap(BigInt& a, BigInt& b);
friend BigInt BImodmul(const BigInt& p1, const BigInt& p2, const BigInt pp);
friend BigInt BImodmul2(const BigInt& p1, const BigInt& p2, const BigInt pp);
friend void MakeModBaseTable(const BigInt& pp);
friend BigInt BImodexp2(const BigInt& p1, const BigInt& p2, const BigInt pp);
friend BigInt BImodexp(const BigInt& p1, const BigInt& p2, const BigInt pp);
friend BigInt BImodpow2(const BigInt& p1, const BigInt& pp, const int& d);
friend void MakePreTable(const BigInt& p, const BigInt& pp);
};
#include"BigInt.cpp"
#endif

复制代码

[ 本帖最后由 chinanic 于 2007-8-25 13:42 编辑 ]

TOP

x86 该用户已被删除

7楼

x86发表于 2005-3-22 20:03 | 只看该作者

RSA加密源代码

BigInt TableModBase[25];//for modlue multie
BigInt PreTable[16];
//constructor
BigInt::BigInt()
{
head = new intNode();
positive = true;
}
//disconstuctor
BigInt::~BigInt()
{
}
//set the number to 0
void BigInt::setZero()
{
intNode* temp;
while(head->next != NULL)
{
temp = head;
head = head->next;
delete temp;
}
positive = true;
head -> num = 0;
}
//load the number at the base of ten
void BigInt::loadDEC(const char* str, const int length)
{
unsigned int temp = 0;
unsigned int base = MAXDEC;
setZero();
int i = 0;
if(str[i] == ';-';)
{
positive = false;
++i;
}
for(; i < length; ++i)
{
temp *= 10;
temp += ((unsigned int) (str[i] - ';0';));
if((i + 1) % 9 == 0)
{
*this = *this * base;
*this += temp;
temp = 0;
}
}
base = (unsigned int)pow(10, (length % 9));
*this = * this * base;
*this += temp;
}
//load the number at the base of 16
void BigInt::loadHEX(const char* str, const int length)
{
unsigned int temp = 0;
unsigned char t;
setZero();
int i = 0;
if(str[i] == ';-';)
{
positive = false;
++i;
}
for(; i < length; ++i)
{
temp <<= 4;
t = (unsigned char) str[i];
temp |= hdigit(t);
if((i + 1) % 8 == 0)
{
*this <<= 32;
*this += temp;
temp = 0;
}
}
*this <<= (length % 8) * 4;
*this += temp;
}
//convert the string to big number
void BigInt::loadSTR(const char* str, const int length)
{
unsigned int temp = 0;
setZero();
int i = 0;
int mi = 1;
if(str[0] == ';-';)
{
positive = false;
++i;
mi = 0;
}
for(; i < length ; ++i)
{
temp <<= 8;
temp |= (unsigned int)str[i];
if( (i +mi) % 4 == 0)
{
*this <<= 32;
*this += temp;
temp = 0;
}
}
* this <<= (length % 4) * 8;
*this += temp;
}
//output the number at the base ten
char* BigInt::outputDEC(int& length)
{
unsigned int temp;
unsigned int base = MAXDEC;
int i;
unsigned char c = ';0';;
stack s;//the stack to store the charactors
BigInt a;
a.copy(*this);
unsigned char* ch;
if(a.BIlisZero())
{
ch = new unsigned char[1];
ch[0] = ';0';;
length = 1;
return (char*)ch;
}
while(! a.BIlisZero())
{
temp = a % base;
a = a / base;
for(i = 0; i < 9; ++i)
{
c = (unsigned char)((temp % 10) + ((unsigned int)';0';));
s.push(c);
temp /= 10;
}
}//convent the number at the base of ten to charactors and store the in the stack
c = ';0';;
while(c == ';0';)
s.pop(c);
length = s.getLength() + 1;
i = 0;
if(!positive)
++length;
ch = new unsigned char[length];
if(!positive)
{
++i;
ch[0] = ';-';;
}
for(; i < length; ++i)
{
ch[i] = c;
s.pop(c);
}//pop the characors and put the in the characotors
return (char*)ch;
}
//output the number at the base of 16
char* BigInt::outputHEX(int& length)
{
unsigned int temp;
BigInt a;
a.copy(*this);
stack s;
unsigned char c = ';0';;
int i;
unsigned char* ch;
if(a.BIlisZero())
{
ch = new unsigned char[1];
ch[0] = ';0';;
length = 1;
return (char*)ch;
}
while(!a.BIlisZero())
{
temp = a.getLast32Bit();
a >>= 32;
for(i = 0; i < 8; ++i)
{
c = HArray[temp & 0xF];
s.push(c);
temp >>= 4;
}
}//convent the number at the base of 16 to charactors and store the in the stack
c = ';0';;
while(c == ';0';)
s.pop(c);
length = s.getLength() + 1;
i = 0;
if(!positive)
++length;
ch = new unsigned char[length];
if(!positive)
{
++i;
ch[0] = ';-';;
}
for(; i < length; ++i)
{
ch[i] = c;
s.pop(c);
}//pop the characors and put the in the characotors
return (char*)ch;
}
//output the number at form of ASCII
char* BigInt::outputSTR(int& length)
{
unsigned int temp;
BigInt a;
a.copy(*this);
stack s;
unsigned char c;
int i;
unsigned char* ch;
if(a.BIlisZero())
{
ch = new unsigned char [1];
ch[0] = 0;
length = 1;
return (char*)ch;
}
while(! a.BIlisZero())
{
temp = a.getLast32Bit();
a >>= 32;
for(i = 0; i < 4; ++i)
{
c = (unsigned char)(temp & 0xFF);
s.push(c);
temp >>= 8;
}
}//convent the number at the base of 16 to charactors and store the in the stack
c = 0;
while(c == 0)
s.pop(c);
length = s.getLength() + 1;
ch = new unsigned char[length];
for(i = 0; i < length; ++i)
{
ch[i] = c;
s.pop(c);
}//pop the characors and put the in the characotors
return (char*)ch;
}
//reload the operator +
BigInt BigInt::operator + (const BigInt& p) const
{
BigInt temp;
if((positive && p.positive) || ((!positive) && (!p.positive)))
{
add(p, temp);
temp.positive = positive;
}
else
{
if( BICompareABS(p) > 0)
{
minuse(p,temp);
temp.positive = positive;
}
else
{
if( BICompareABS(p) == 0)
temp.setZero();
else
{
p.minuse(*this,temp);
temp.positive = ! positive;
}
}//end of second else
}//end of first else
return temp;
}
//reload the operator +
BigInt BigInt::operator + (const unsigned int& p) const
{
BigInt temp;
if(positive)
{
add(p, temp);
temp.positive = true;
}
else
{
temp.setZero();
if( BICompareABS(p) > 0)
{
minuse(p, temp);
temp.positive = false;
}
if(BICompareABS(p) < 0)
{
temp.head -> num = p - head->num;
temp.positive = true;
}
}
return temp;
}
BigInt BigInt::operator - (const BigInt& p) const
{
BigInt temp;
if((positive && (!p.positive)) || ((!positive) && p.positive))
{
add(p, temp);
temp.positive = positive;
}
else
{
if( BICompareABS(p) > 0)
{
minuse(p,temp);
temp.positive = positive;
}
else
{
if( BICompareABS(p) == 0)
temp.setZero();
else
{
p.minuse(*this,temp);
temp.positive = ! positive;
}
}//end of second else
}//end of first else
return temp;
}
BigInt BigInt::operator - (const unsigned int& p) const
{
BigInt temp;
if(!positive)
{
add(p, temp);
temp.positive = false;
}
else
{
temp.setZero();
if( BICompareABS(p) > 0)
{
minuse(p, temp);
temp.positive = true;
}
if(BICompareABS(p) < 0)
{
temp.head->num = p - head->num;
temp.positive = false;
}
}
return temp;
}
BigInt BigInt::operator * (const unsigned int& p) const
{
BigInt bin;
unsigned int high = 0;
unsigned int low = 0;
intNode* temp = head;
intNode* t1 = bin.head;
intNode* t2 = bin.head;
while(temp != NULL)
{
multi(p, temp->num, high, low);
t1->num += low;
if(t1->num < low)
++high;
t1->next = new intNode;
t2 = t1;
t1 = t1->next;
t1->num = high;
temp = temp->next;
}
if(t1->num == 0)
{
delete t1;
t2->next = NULL;
}
bin.positive = positive;
return bin;
}
BigInt BigInt::operator * (const BigInt& p) const
{
BigInt bin;
unsigned int high = 0;
unsigned int low = 0;
unsigned int carry = 0;
intNode* temp1 = head;
intNode* temp2 = p.head;
intNode* t1 = bin.head;
intNode* t2 = bin.head;
intNode* t3 = bin.head;
bin.positive = (positive && p.positive) || ((! positive) && (! p.positive));
while(temp1 != NULL)
{
t2 = t1;
temp2 = p.head;
while(temp2 != NULL)
{
multi(temp1->num, temp2->num, high, low);
t2->num += carry;
if(t2->num < carry)
carry = 1;
else
carry = 0;
t2->num += low;
if(t2->num < low)
++carry;
carry += high;
if(t2->next == NULL)
{
t3 = t2;
t2->next = new intNode;
}
t2 = t2->next;
temp2 = temp2->next;
}
t2->num = carry;
carry = 0;
temp1 = temp1 -> next;
t1 = t1->next;
}
if(t2->num == 0)
{
delete t2;
t3->next = NULL;
}
return bin;
}
BigInt BigInt::operator / (const BigInt& p)
{
BigInt d;
BigInt r;
r = BIdivision(p, d);
r.positive = (positive && p.positive) || ((!positive) && (!p.positive));
d.clear();
return r;
}
BigInt BigInt::operator / (const unsigned int& p)
{
BigInt d;
BigInt r;
BigInt pp;
pp = p;
r.positive = positive;
r = BIdivision(pp, d);
d.clear();
pp.clear();
return r;
}
BigInt BigInt::operator % (const BigInt& p) const
{
BigInt a, mb;
BigInt temp;
a.copy(*this);
a.positive = (p.positive && positive) || ((!p.positive) && (!positive));
if(a.BICompareABS(p) > 0)
{
mb.copy(p);
a.MakeClose(mb);
while(a.BICompareABS(mb) > 0)
mb <<= 1;
while(a.BICompareABS(p) > 0)
{
while(a.BICompareABS(mb) < 0)
mb >>= 1;
temp = a - mb;
a.copy(temp);
}
}
if(a.BICompareABS(p) == 0)
a.setZero();
mb.clear();
temp.clear();
return a;
}
unsigned int BigInt::operator % (const unsigned int& p) const
{
BigInt mb;
mb = p;
BigInt a;
a = (*this) % mb;
unsigned int temp;
temp = a.head->num;
mb.clear();
a.clear();
return temp;
}
bool BigInt::operator > (const BigInt& p) const
{
if(positive && (!p.positive))
return true;
if((!positive) && p.positive)
return false;
if(positive && (BICompareABS(p) > 0))
return true;
if(!positive && (BICompareABS(p) < 0))
return true;
return false;
}
bool BigInt::operator > (const unsigned int p) const
{
if(! positive)
return false;
if(BICompareABS(p) > 0)
return true;
return false;
}
bool BigInt::operator == (const BigInt& p) const
{
if(positive &&(! p.positive))
return false;
return (BICompareABS(p) == 0);
}
bool BigInt::operator != (const BigInt& p) const
{
if(positive && (! p.positive))
return true;
return (BICompareABS(p) != 0);
}
BigInt& BigInt::operator <<= (int iBit)
{
if(BIlisZero())
return *this;
int block = 0;
intNode* t1 = head;
intNode* t2 = head;
block = iBit / 32;
for(int i = 0; i < block; ++i)
{
t2 = new intNode(head);
head = t2;
}
iBit %= 32;
if(iBit == 0)
return *this;
unsigned int carry = 0;
unsigned int highF =((FULL >> (32 - iBit)) << (32 - iBit));
unsigned int high;
for(t2 = t1; t2->next != NULL; t2 = t2->next)
{
high = (t2->num & highF) >> (32 - iBit);
t2->num <<= iBit;
t2->num |= carry;
carry = high;
}
high = (t2->num & highF) >> (32 - iBit);
t2->num <<= iBit;
t2->num |= carry;
carry = high;
if(carry != 0)
t2->next = new intNode(carry);
return *this;
}
BigInt& BigInt::operator >>= (int iBit)
{
if(BIlisZero())
return *this;
int block = iBit / 32;
intNode* t = head;
for(int i = 0; (i < block) && (head != NULL); ++i)
{
t = head;
head = head->next;
delete t;
}
if(head == NULL)
{
head = new intNode;
return *this;
}
iBit %= 32;
if(iBit == 0)
return *this;
t = head;
if(t->next == NULL)
{
t->num >>= iBit;
return *this;
}
unsigned int low;
unsigned int lowF = ((FULL << (32 - iBit)) >> (32 - iBit));
unsigned int carry = 0;
for(t = head; t->next->next != NULL; t = t->next)
{
low = ((t->next->num & lowF) << (32-iBit));
t->num = ((t->num >> iBit) | low);
}
low = ((t->next->num & lowF) << (32-iBit));
t->num = ((t->num >> iBit) | low);
t->next->num >>= iBit;
if(t->next->num == 0)
{
delete t->next;
t->next = NULL;
}
return *this;
}
BigInt& BigInt::operator = (const BigInt& p)
{
positive = p.positive;
clear();
head = p.head;
return *this;
}
BigInt& BigInt::operator = (const unsigned int& p)
{
positive = true;
clear();
head = new intNode(p);
return *this;
}
BigInt& BigInt::operator ++ ()
{
intNode *t = head;
while(t->next != NULL)
{
++(t->num);
if(t->num != 0)
return *this;
t = t->next;
}
++(t->num);
if(t->num == 0)
t->next = new intNode(1);
return *this;
}
BigInt& BigInt::operator -- ()
{
intNode *t = head;
intNode *tt = head;
if(head->next == NULL)
{
--(t->num);
return *this;
}
while(t->next != NULL)
{
--(t->num);
if(t->num != FULL)
return *this;
tt = t;
t = t->next;
}
--(t->num);
if(t->num == 0)
{
delete t;
tt->next = NULL;
}
return *this;
}
bool BigInt::BIlisZero() const
{
return ((head->next == NULL) && (head->num == 0));
}
int BigInt::BICompareABS(const BigInt& p) const
{
intNode* t1 = head;
intNode* t2 = p.head;
int comp = 0;
while((t1 != NULL) && (t2 != NULL))
{
if(t1->num > t2->num)
comp = 1;
if(t1->num < t2->num)
comp = -1;
t1 = t1->next;
t2 = t2->next;
}
if(t1 != NULL)
comp = 1;
if(t2 != NULL)
comp = -1;
return comp;
}
int BigInt::BICompareABS(const unsigned int& p) const
{
if((head->next != NULL) || (head->num > p))
return 1;
if(head->num < p)
return -1;
return 0;
}
void BigInt::copy(const BigInt& p)
{
if(head == NULL)
head = new intNode;
intNode* t1 = head;
intNode* t2 = p.head;
positive = p.positive;
while(t2->next != NULL)
{
if(t1->next == NULL)
t1->next = new intNode;
t1->num = t2->num;
t1 = t1->next;
t2 = t2->next;
}
t1->num = t2->num;
t2 = t1->next;
t1->next = NULL;
while(t2 != NULL)
{
t1 = t2;
t2 = t2->next;
delete t1;
}
}
unsigned int BigInt::getLast32Bit()
{
if(head != NULL)
return head->num;
else
return 0;
}
void BigInt::add(const BigInt& p, BigInt& temp) const
{
if(temp.head == NULL)
temp.head = new intNode;
intNode* t1 = temp.head;
intNode* t2 = p.head;
intNode* t3 = head;
intNode* t4 = temp.head;
unsigned int carry = 0;
while((t2 != NULL) && (t3 != NULL))
{
if(t1->next == NULL)
t1->next = new intNode;
t1->num = carry;
carry = 0;
t1->num += t2->num;
if(t1->num < t2->num)
carry = 1;
t1->num += t3->num;
if(t1->num < t3->num)
carry = 1;
t4 = t1;
t1 = t1->next;
t2 = t2->next;
t3 = t3->next;
}
if(t2 == NULL)
t2 = t3;
while(t2 != NULL)
{
if(t1->next == NULL)
t1->next = new intNode;
t1->num = t2->num + carry;
if(t1->num < carry)
carry = 1;
else
carry = 0;
t4 = t1;
t2 = t2->next;
t1 = t1->next;
}
t1->num = carry;
if(t1->num == 0)
{
delete t1;
t4->next = NULL;
}
}
void BigInt::minuse(const BigInt& p, BigInt& temp) const
{
temp.copy(*this);
intNode* t1 = p.head;
intNode* t2 = temp.head;
unsigned int carry = 0;
while(t1 != NULL)
{
t2->num -= carry;
if((carry == 1) && (t2->num == FULL))
carry = 1;
else
carry = 0;
t2->num -= t1->num;
if((t2->num + t1->num) < t2->num)
carry = 1;
t2 = t2->next;
t1 = t1->next;
}
if(carry == 1)
{
while(t2 != NULL)
{
--(t2->num);
if(t2->num != FULL)
break;
t2 = t2->next;
}
}
for(t1 = temp.head; t1 != NULL; t1 = t1->next)
{
if(t1->num != 0)
t2 = t1;
}
t1 = t2->next;
t2->next = NULL;
while(t1 != NULL)
{
t2 = t1;
t1 = t1->next;
delete t2;
}
}
void BigInt::add(const unsigned int& p,BigInt& temp) const
{
temp.copy(*this);
intNode* t = temp.head;
t->num += p;
if(t->num >= p)
return;
if(t->next == NULL)
{
t->next->next = new intNode;
t->next->num = 1;
return;
}
t = t->next;
while(t->next != NULL)
{
++(t->num);
if(t->num != 0)
return;
t = t->next;
}
t->next = new intNode;
t->next->num = 1;
}
void BigInt::minuse(const unsigned int& p,BigInt& temp) const
{
temp.copy(*this);
intNode* t = temp.head;
t->num -= p;
if((t->num + p) > t->num)
return;
t = t->next;
while(t->next->next != NULL)
{
--(t->num);
if(t->num != FULL)
return;
t = t->next;
}
--(t->num);
if(t->num != FULL)
return;
--(t->next->num);
if(t->next->num == 0)
{
delete t->next;
t->next = NULL;
}
}
void BigInt::clear()
{
if(head == NULL)
return;
intNode* t;
while(head != NULL)
{
t = head;
head = head->next;
delete t;
}
}
void BigInt::MakeClose(BigInt& p)
{
intNode* t1 = head;
intNode* t2 = p.head;
while(t2 != NULL)
{
t1 = t1->next;
t2 = t2->next;
}
while(t1 != NULL)
{
t1 = t1->next;
t2 = new intNode(p.head);
p.head = t2;
}
}
BigInt BigInt::BIdivision(const BigInt& p, BigInt& pr)
{
int test = BICompareABS(p);
BigInt re;
if(test == 0)
{
pr.setZero();
++re;
return re;
}
if(test < 0)
{
pr.copy(*this);
return re;
}
BigInt t1;
BigInt t2;
t2.copy(p);
t1.copy(*this);
MakeClose(t2);
while(BICompareABS(t2) > 0)
t2 <<= 1;
while(BICompareABS(t2) < 0)
t2 >>= 1;
while((p.BICompareABS(t1) <= 0) || (p.BICompareABS(t2) <= 0))
{
if(t1.BICompareABS(t2) >= 0)
{
t1 = t1 - t2;
re <<= 1;
++re;
}
else
re <<= 1;
t2 >>= 1;
}
pr.copy(t1);
return re;
}
BigInt& BigInt::operator += (const unsigned int& p)
{
intNode* temp = head;
temp->num += p;
if(temp->num >= p)
return *this;
if(temp->next == NULL)
{
temp->next = new intNode(1);
return *this;
}
temp = temp->next;
while(temp->next != NULL)
{
++(temp->num);
if(temp->num != 0)
return *this;
temp = temp->next;
}
++(temp->num);
if(temp->num == 0)
temp->next = new intNode(1);
return *this;
}
BigInt BigInt::BIinverse(const BigInt& p) const
{
BigInt y, g0, g1, g2, v0, v1, v2;
g0.copy(p);
g1.copy(*this);
++v1;
while(! g1.BIlisZero())
{
y = g0.BIdivision(g1, g2);
g0.copy(g1);
g1.copy(g2);
v2 = y * v1;
while(v0.BICompareABS(v2) < 0)
v0 = v0 + p;
v0 = v0 - v2;
BIswap(v0,v1);
}
y.clear();
g0.clear();
g1.clear();
g2.clear();
v1.clear();
v2.clear();
return v0;
}
int BigInt::nodeNumber() const
{
intNode* t;
t = head;
int i = 0;
while(t != NULL)
{
t = t->next;
++i;
}
return i;
}
BigInt BIgcd(const BigInt& p1, const BigInt& p2)
{
BigInt a;
a.copy(p1);
BigInt b;
b.copy(p2);
while(! b.BIlisZero())
{
a = a % b;
BIswap(a, b);
}
b.clear();
return a;
}
void BIswap(BigInt& a, BigInt& b)
{
bool bo;
bo = a.positive;
a.positive = b.positive;
b.positive = bo;
intNode* temp;
temp = a.head;
a.head = b.head;
b.head = temp;
}
void MakeModBaseTable(const BigInt& pp)
{
TableModBase[0].copy(pp);
for(int i = 1; i < 25; ++i)
{
TableModBase[i].copy(TableModBase[i - 1]);
TableModBase[i] <<= 2;
}
}
BigInt BImodmul(const BigInt& p1, const BigInt& p2, const BigInt pp)
{
BigInt a, b, c, result;
int i;
intNode* t;
if(p1.BIlisZero())
return result;
if(p2.BIlisZero())
return result;
if(TableModBase[0] != pp)
MakeModBaseTable(pp);
a = p1 % pp;
b = p2 % pp;
b.head = t = backToFront(b.head);
while( t != NULL)
{
result <<= 32;
if(t->num != 0)
{
c = a * t->num;
result = result + c;
}
if(result.BICompareABS(pp) >= 0)
{
for(i = 24; i >= 0; --i)
{
while(result.BICompareABS(TableModBase[i]) >= 0)
result = result - TableModBase[i];
}
}
t = t->next;
}
a.clear();
b.clear();
c.clear();
return result;
}
BigInt BImodmul2(const BigInt& p1, const BigInt& p2, const BigInt pp)
{
BigInt pre_a[16], a, b, pp2, pp4, pp8, result;
unsigned int ma1, ma2;
int i, j, test;
intNode* t;
a.copy(p1);
b.copy(p2);
test = a.BICompareABS(pp);
if(test > 0)
a = a % pp;
if(test == 0)
return result;
if(a.BIlisZero())
return result;
test = b.BICompareABS(pp);
if(test > 0)
b = b % pp;
if(test == 0)
return result;
if(b.BIlisZero())
return result;
pre_a[0].setZero();
pre_a[1].copy(a);
for(i = 2; i < 16; ++i)
{
pre_a[i] = pre_a[i - 1] + a;
if(pre_a[i].BICompareABS(pp) > 0)
pre_a[i] = pre_a[i] - pp;
}
pp2.copy(pp);
pp2 <<= 1;
pp4.copy(pp2);
pp4 <<= 1;
pp8.copy(pp4);
pp8 <<= 1;
b.head = t = backToFront(b.head);
while(t != NULL)
{
ma1 = 0xF0000000;
for(i = 7; i >= 0; --i)
{
result <<= 4;
ma2 = t->num & ma1;
if(ma2 != 0)
{
j = (i << 2);
ma2 >>= j;
result = result + pre_a[ma2 & 0xf];
}
while(result.BICompareABS(pp8) > 0)
result = result - pp8;
while(result.BICompareABS(pp4) > 0)
result = result - pp4;
while(result.BICompareABS(pp2) > 0)
result = result - pp2;
while(result.BICompareABS(pp) > 0)
result = result - pp;
ma1 >>= 4;
}
t = t->next;
}
for(i = 0; i < 16; ++i)
pre_a[i].clear();
a.clear();
b.clear();
pp2.clear();
pp4.clear();
pp8.clear();
return result;
}
BigInt BImodexp(const BigInt& p1, const BigInt& p2, const BigInt pp)
{
BigInt a, b, result;
a = p1 % pp;
b.copy(p2);
if(a.BIlisZero())
return result;
if(b.BIlisZero())
{
++result;
return result;
}
++result;
do{
if((b.head->num & 1) == 1)
result = BImodmul(a, result, pp);
b >>= 1;
if(! b.BIlisZero())
a = BImodmul(a, a, pp);
}while(! b.BIlisZero());
a.clear();
b.clear();
return result;
}
BigInt BImodpow2(const BigInt& p1, const BigInt& pp, const int& d)
{
BigInt result;
int i;
result.copy(p1);
for(i = d; i > 0; --i)
result = BImodmul(result, result, pp);
return result;
}
void MakePreTable(const BigInt& p, const BigInt& pp)
{
int i;
PreTable[0].setZero();
++PreTable[0];
PreTable[1].copy(p);
for(i = 2; i < 16; ++i)
PreTable[i] = BImodmul2(PreTable[i - 1], p, pp);
}
BigInt BImodexp2(const BigInt& p1, const BigInt& p2, const BigInt pp)
{
BigInt a, b, result;
unsigned int tmp;
int iz, Lt, count, kZero;
if(p1.BIlisZero())
return result;
++result;
if(p2.BIlisZero())
return result;
a = p1 % pp;
b.copy(p2);
if(a.BICompareABS(PreTable[1]) != 0)
MakePreTable(a, pp);
Lt = b.nodeNumber();
count = 32 * Lt;
intNode* t = b.head;
if(! TheLastNode(t))
{
result.positive = false;
return result;
}
kZero = FindZeroBit(t->num);
b <<= kZero;
count -= kZero;
do{
tmp = (t->num & 0xF0000000);
if(count > 3)
{
tmp >>= 28;
b <<= 4;
count -= 4;
}
else
{
tmp >>= (32 - count);
b <<= count;
count = 0;
}
result = BImodmul2(result, PreTable[tmp & 0x0f], pp);
iz = 0;
if(count != 0)
{
while(((t->num & 0x80000000) != 0x80000000) && (count > 0))
{
b <<= 1;
--count;
++iz;
}
if(count > 3)
iz += 4;
else
iz += count;
result = BImodpow2(result, pp, iz);
}
}while(count != 0);
a.clear();
b.clear();
return result;
}
intNode* BigInt::getHead() const
{
return head;
}
void BigInt::print(int choose)
{
char* ch;
int lent;
switch(choose)
{
case 1:
ch = outputDEC(lent);
break;
case 2:
ch = outputHEX(lent);
break;
case 3:
ch = outputSTR(lent);
break;
default:
break;
}
for(int i = 0; i < lent; ++i)
cout << ch[i];
cout << endl;
delete[] ch;
}[/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i][/i]