大三时候实现的，关于大整数（超过long范围）加减乘除操作的头文件，并包含了实现RSA加解密的函数

  1 #include<iostream>
  2 #include<time.h>
  3 #include<string.h>
  4 using namespace std;
  5 
  6 
  7 class BigNum{
  8 private:
  9     int *num;                                        //数值
 10     int *yu;                                        //余数
 11     int n;                                            //数值位数
 12     int YuNum;                                        //余数位数
 13     bool sym;                                        //正负，true为正
 14 public:
 15     BigNum(char *str){
 16         n = strlen(str);
 17         YuNum = 0;sym = true;
 18         num = new int[strlen(str)];
 19         for(int i = 0 ; i < strlen(str) ; i++)
 20             num[i] = str[strlen(str)-i-1]-'0';
 21     }
 22     BigNum(int A){
 23         int i,j;
 24         int a = A;
 25         for(i=0; a!=0; i++)
 26             a/=10;
 27         num = new int[i];
 28         a = A;
 29         for(j=0; j<i; j++){
 30             num[j] = a%10;
 31             a/=10;
 32         }
 33         n = i;
 34         YuNum = 0;
 35     }
 36     BigNum(bool a){
 37         YuNum = 0;sym = true;
 38         char *str = new char[256];
 39         cout<<"输入数以建立对象:"<<endl;
 40         cin>>str;
 41         n = strlen(str);
 42         num = new int[strlen(str)];
 43         for(int i = 0 ; i < strlen(str) ; i++)
 44             num[i] = str[strlen(str)-i-1]-'0';
 45     }
 46     BigNum(){
 47         sym = true;
 48         n = 0;
 49         YuNum = 0;
 50     }
 51     BigNum operator+(BigNum p){
 52         BigNum temp = BigNum();
 53         int i;
 54         if( this->sym + p.sym == 1){
 55             bool s;
 56             if(*this > p){
 57                 s = this->sym;
 58                 this->sym = p.sym;
 59                 temp = *this - p;
 60                 temp.sym = s;
 61             }
 62             else{
 63                 s = p.sym;
 64                 p.sym = this->sym;
 65                 temp = p - *this;
 66                 temp.sym = s;
 67             }
 68             return temp;
 69         }
 70         int c=0;                                                    //进位
 71         temp.n = max(this->n ,p.n );
 72         int *Num = new int[temp.n +1 ];
 73         for( i=0; i<min(this->n ,p.n); i++){
 74             Num[i]= (this->num[i] +p.num[i] +c) %10;
 75             c = (this->num[i]+p.num[i]+c)/10;
 76         }
 77         if(this->n > p.n)
 78             for( i = p.n ; i < temp.n ; i++){
 79                 Num[i] = (this->num[i]+c)%10;
 80                 c = (this->num[i]+c)/10;
 81             }
 82         else
 83             for( i=this->n;i<p.n;i++){
 84                 Num[i] = (p.num[i]+c)%10;
 85                 c = (p.num[i]+c)/10;
 86             }
 87         if(c>0){
 88             temp.n++;
 89             Num[temp.n-1]=c;
 90         }
 91         temp.num = new int[temp.n];
 92         for(int i=0;i<temp.n;i++)
 93             temp.num[i] = Num[i];
 94         return temp;
 95     }
 96     BigNum operator-(BigNum p){
 97         BigNum temp = BigNum();
 98         int i;
 99         if(this->sym + p.sym == 1){                            //异符号相减是两数绝对值相加，符号取减数
100             bool s = this->sym;
101             this->sym = p.sym;
102             temp = *this + p;
103             temp.sym = s;
104             return temp;
105         }
106         if(!(*this > p)){
107             temp = p - *this;                                //减法结果出现负数
108             temp.sym = false;
109             return temp;
110         }
111         int c=0;                                    //进位
112         int *Num = new int[this->n];
113         for( i=0;i<this->n;i++){
114             if(i<p.n){
115                 if(this->num[i]+c>=p.num[i]){
116                     Num[i] = this->num[i]+c-p.num[i];
117                     c=0;
118                 }
119                 else{
120                     Num[i] = this->num[i]+c+10-p.num[i];
121                     c=-1;
122                 }
123             }
124             else{
125                 if(this->num[i]+c>=0){
126                     Num[i] = this->num[i]+c;
127                     c = 0;
128                 }
129                 else{
130                     Num[i] = this->num[i]+c+10;
131                     c = -1;
132                 }
133             }
134         }
135         temp.n = this->n;
136         for( i=this->n-1;Num[i]==0&&i>=0;i--)
137             temp.n--;
138         temp.num = new int[temp.n];
139         for( i=0;i<temp.n;i++)
140             temp.num[i] = Num[i];
141         return temp;
142     }
143     BigNum operator*(BigNum p){
144         int i;
145         BigNum temp = BigNum();
146         if(this->sym + p.sym == 1)
147             temp.sym = false;
148         if(this->n==0 || p.n==0)
149             return temp;
150         int *Num = new int[p.n+this->n+1];                        //循环中可能会用到最后一个数
151         int c = 0;
152         for(i=0; i < this->n+p.n; i++)
153             Num[i] = 0;
154         for(i=0; i < p.n+this->n; i++){
155             for(int j=0; j < this->n; j++)
156                 for(int k=0; k < p.n; k++){
157                     if(i==j+k)
158                         c += this->num[j]*p.num[k];
159                 }
160             Num[i]+=c%10;
161             c=c/10;
162         }
163         for(i=this->n+p.n; Num[i] <= 0; )
164             i--;
165         temp.n=i+1;
166         temp.num = new int[temp.n];
167         for(i=0; i<temp.n; i++)
168             temp.num[i] = Num[i];
169         return temp;
170     }
171     bool operator> (BigNum p){                                //大于等于的效果，跟小于对立，只比较绝对值，不关心正负
172         if(this->n > p.n)
173             return true;
174         else if(this->n < p.n)
175             return false;
176         else{
177             for(int i=1 ; i <= p.n; i++){
178                 if(this->num[n-i] == p.num[n-i])
179                     continue;
180                 else if(this->num[n-i] <= p.num[n-i])
181                     return false;
182                 else
183                     return true;
184             }
185             return true;
186         }
187     }
188     BigNum operator/(BigNum p){
189         BigNum temp = BigNum();
190         int i,j,k;
191         temp.sym = this->sym + p.sym;
192         if(!(*this > p)){
193             temp.n = 0;
194             temp.yu = new int[this->n];
195             temp.YuNum = this->n;
196             for( i=0;i<this->n;i++)
197                 temp.yu[i] = this->num[i];
198             return temp;
199         }
200         int *Num = new int[this->n-p.n+1];
201         for( i=0;i<this->n-p.n+1;i++)                        //置零
202             Num[i] = 0;
203         BigNum mid = BigNum();                                    //让mid成为this的复制，在处理中要改变其中的值
204         mid.n = this->n;
205         mid.num = new int[mid.n];
206         for( i = 0; i < mid.n; i++)
207             mid.num[i] = this->num[i];
208         int m = mid.n - p.n;                                    //用首位相减法，跟人手酸除法的过程相似，需要改变mid中的数值和位数，m存储低位没用到的位数
209         mid.n = p.n;    mid.num += this->n - p.n;                //把mid置成跟p相同长度，开始相减，指针相应的向后移动
210         for( i = this->n - p.n +1-1;i >= 0;  ){
211             BigNum A = BigNum();                                //A是中间变量为了使mid的数值动态化
212             while( mid > p ){
213                 A = mid - p;
214                 for( k=0; k < A.n ; k++)
215                     mid.num[k] = A.num[k];
216                 for( k=A.n; k < mid.n; k++)
217                     mid.num[k] = 0;
218                 Num[i] +=1;
219                 for( j = mid.n-1; j >= 0 ;j--,mid.n-- )                //去掉开头的零
220                     if(mid.num[j] != 0)
221                         break;
222             }
223             if( m + mid.n<p.n || m == 0 && p >mid){                                        //剩下的数总和比P小，除法完成
224                 temp.yu = new int[m + mid.n];
225                 mid.num -= m;
226                 for( k = 0; k < m + mid.n ; k++)
227                     temp.yu[k] = mid.num[k];
228                 temp.YuNum = m + mid.n;
229                 //mid.n = this->n;
230                 int j = this->n - p.n + 1;
231                 for( ; j>0 ; j--)
232                     if(Num[j-1] != 0)
233                         break;
234                 temp.num = new int[j];
235                 for( k = 0;k < j ; k++ )
236                     temp.num[k] = Num[k];
237                 temp.n = j;
238                 return temp;
239             }
240             else{
241                 m -= p.n - mid.n;
242                 mid.num -= p.n - mid.n;
243                 i -= p.n - mid.n;
244                 mid.n = p.n;
245                 if( m > 0 && p > mid){                //借位
246                     m--;
247                     i--;
248                     mid.num--;
249                     mid.n++;
250                 }
251                 for( k = mid.n ; mid.num[k-1] == 0 && k >= 1 ; k--)
252                     mid.n--;
253             }
254         }
255         return temp;
256     }
257     void display(){
258         int i;
259         if( sym == false )
260             cout<<'-';
261         for( i=0 ;i < n; i++)
262             cout<<num[n-i-1];
263         if(YuNum > 0){
264             cout<<endl;
265             for( i=0; i < YuNum; i++)
266                 cout<<yu[YuNum-i-1]<<' ';
267         }
268         cout<<endl;
269     }
270     static void swap(BigNum &a,BigNum &b){
271         BigNum temp = a;
272         a = b;
273         b=temp;
274     }
275     static BigNum gcd(BigNum A,BigNum B){
276         int i;
277         BigNum temp;
278         BigNum a;a = A;
279         BigNum b;b = B;
280         while(true){
281             temp = a/b;
282             if( a>b )
283                 BigNum::swap( a,b );
284             free(b.num);
285             b.n = temp.YuNum;
286             b.num = new int[a.n];
287             for( i=0;i < temp.YuNum; i++){
288                 b.num[i] = temp.yu[i];
289             }
290             if(  temp.YuNum==0 )
291                 break;
292         }
293         return a;
294     }
295     void operator=(BigNum p){
296         int i;
297         this->~BigNum();
298         this->sym = p.sym;
299         this->n = p.n;
300         this->num = new int[this->n];
301         for( i=0; i< p.n; i++)
302             this->num[i] = p.num[i];
303         this->YuNum = p.YuNum;
304         this->yu = new int[this->YuNum];
305         for( i=0; i< p.YuNum; i++)
306             this->yu[i] = p.yu[i];
307     }
308     static BigNum inv(BigNum a, BigNum b){                                            //小的放在前面
309         BigNum a0 = a;
310         BigNum b0 = b;
311         BigNum t0;
312         BigNum t("1");
313         BigNum s0("1");
314         BigNum s;
315         BigNum q = a0 /b0;
316         BigNum r = a0 - (q * b0);
317         BigNum temp;
318         while( r > BigNum("1") ){
319             temp = t0 - (q * t);
320             t0 = t;
321             t = temp;
322             temp = s0 - (q * s);
323             s0 = s;
324             s = temp;
325             a0 = b0;
326             b0 = r;
327             q = a0 /b0;
328             r = a0 - (q * b0);
329         }
330         r = b0;
331         if( s.sym == false )
332             s = s + b;
333         return s;
334     }
335     bool operator==(BigNum p){
336         if( this->n == p.n ){
337             for(int i=0; i < p.n; i++)
338                 if( this->num[i] != p.num[i] )
339                     return false;
340             return true;
341         }
342         return false;
343     }
344     char* toChar(){
345         int i;
346         char *str = new char[this->n+2];
347         for(i=0; i<this->n; i++)
348             str[this->n-i-1] = '0'+this->num[i];
349         str[i] = '\0';
350         return str;
351     }
352     BigNum mod(BigNum n){
353         BigNum temp;
354         if(!(*this> n)){
355             temp.n = this->n;
356             temp.num = new int[temp.n];
357             for(; temp.n>0; temp.n--)
358                 temp.num[temp.n-1] = this->num[temp.n-1];
359             temp.n = this->n;
360         }
361         else{
362             BigNum y = *this /n;
363             temp.n = y.YuNum;
364             temp.num = new int[temp.n];
365             for( ; temp.n>0; temp.n--)
366                 temp.num[temp.n-1] = y.yu[temp.n-1];
367             temp.n = y.YuNum;
368         }
369         return temp;
370     }
371     static BigNum Square_and_Multiply(BigNum X, BigNum C, BigNum N){            //幂模运算z = x^c(mod n)
372         int i;
373         BigNum x = X;BigNum c = C;BigNum n = N;
374         BigNum two("2");
375         for(i=0; c.n>0; i++)
376             c = c /two;
377         bool *bol = new bool[i];
378         c = C;
379         for(i=0; c.n>0; i++){
380             c = c /two;
381             if(c.YuNum > 0)
382                 bol[i] = 1;
383             else
384                 bol[i] = 0;
385         }
386         BigNum z("1");
387         for( ; i >0; i--){
388             z = (z*z).mod(n);                        //只返回正数
389             if(bol[i-1] == 1)
390                 z = (z*x).mod(n);
391         }
392         return z;
393     }
394     static bool Miller_Rabin(BigNum X){                //Miller Rabin算法判断大数X是否为素数，是素数返回true
395         int i,k;
396         BigNum x = X;
397         BigNum two("2");
398         x = x - BigNum("1");
399         for(k=0; x.YuNum==0; k++){
400             x = x /two;
401         }
402         BigNum m = x*two + BigNum("1");
403         k= k- 1;
404         BigNum b = Square_and_Multiply(BigNum("2"),m,X);
405         x = X - BigNum("1");
406         if( b==BigNum("1"))    return true;
407         for(i=0; i<k; i++){
408             if( b==x)
409                 return true;
410             else
411                 b = Square_and_Multiply(b,two,X);
412         }
413         return false;
414     }
415     static BigNum create_prime(int m){
416         int i;
417         BigNum num("1");
418         BigNum one("1");
419         BigNum two("2");
420         srand(time(0));
421         for(i=0; i<m-1; i++){
422             num = num* two + BigNum(rand()).mod(two);
423         }
424         BigNum temp;
425         while(true){
426             temp = num;
427             for(i=1; temp>two; i++)
428                 temp = temp /two;
429             if(Miller_Rabin(num)&&i==m)
430                 return num;
431             else if(i>m){
432                 num = create_prime(m);
433                 return num;
434             }
435             else
436                 num = num+ two;
437         }
438     }
439 };

以上是BigNum.h的源码，下面是应用范例：

 1 #include"BigNum.h"
 2 #include<fstream>
 3 
 4 void main(){
 5     char *str = new char[256];
 6     cout<<"输入密钥";cin>>str;
 7     BigNum c = BigNum(str);
 8     cout<<"输入n";cin>>str;
 9     BigNum n = BigNum(str);
10     ifstream in("data.txt");
11     ofstream out("result.txt");
12     BigNum x;
13     BigNum y;
14     char g;
15     while(!in.eof()){
16         in.get(str,100,' ');
17         if(!(in.eof()))
18             in.get(g);
19         x = BigNum( str );
20         y = BigNum::Square_and_Multiply(x, c, n);
21         out<<y.toChar()<<' ';
22         y.display();
23     }
24     /*string ss;
25     BigNum data;
26     BigNum yu;                                                //余数
27     BigNum sh;                                                //商
28     BigNum one("1");
29     while( !in.eof() ){
30         in>>num;
31         sh = BigNum("1");
32         data = BigNum(num);
33         for( BigNum i = BigNum("1") ; k >i; i =i +one){
34             sh = sh * data;
35             yu = sh / n;
36             //free(temp->num);
37             sh.~BigNum();
38             sh =BigNum();
39             sh.n =yu.YuNum;
40             sh.num = new int[sh.n];
41             for(int j = 0; j < yu.YuNum ; j++){
42                 sh.num[j] = yu.yu[j];
43             }
44             //free(temp->yu);temp->YuNum =0;
45         }
46         sh.display();
47         out<<sh.toChar()<<' ';
48     }*/
49     in.close();
50     out.close();
51     getchar();
52     getchar();
53 }

其中需要文件data.txt（对其中的数据进行加密）：

599973434 2978448901 1049145034