[cpp]
Code:
/*****************************************************************
大数运算库头文件：BigInt.h
作者：afanty@vip.sina.com
版本：1.2 (2003.5.13)
说明：适用于MFC，1024位RSA运算
*****************************************************************/
//允许生成1120位（二进制）的中间结果[......]
Input: n > 3, an odd integer to be tested for primality;
Input: k, a parameter that determines the accuracy of the test
Output: composite if n is composite, otherwise probably prime
write n − 1 as 2s·d with d odd by factoring p[......]
转载自：http://hi.baidu.com/imake/blog/item/f215818b9d7414d0fc1f1039.html
再次膜拜ing
约定：
x%y为x取模y，即x除以y所得的余数，当x<y时，x%y=x，所有取模的运算对象都为整数。
x^y表示x的y次方。
乘方运算的优先级高于乘除和取模，加减的优先级最低。
见到x^y/z这样，就先算乘方，再算除法。
A/B，称为A除以B，也称为B除A。
若A%B=0，即称为A可以被B整除，也称B可以整除A。
A*B表[......]
关于c大数求余
(a * b) % c = ((a % c) * (b % c)) % c
(a + b) % c = ((a % c) + (b % c)) % c
应用这些原理
大数用字符数组保存，对每一位进行求余
大数可以分开算：
比如：
m=123
123 = (1*10 + 2)*10 + 3
m%n = 123%n = (((1%n * 10%n + 2%n)%n * 10%n) % n + 3%n)%n
这样每一步都不会溢出了[......]
[cpp]
#include <stdio.h>
#include <stdlib.h>
void swap(int *a,int *b)
{
int tmp = *a;
*a = *b;
*b = tmp;
}
//对arr数组做从下标0到下标q的划分
int partition(int *arr,int p,int q)
{
int low = p+1,high = q;
int x = arr[p];
while(low<high)
{
if(a[......]