大整数类

• 下载演示程序 - 160 Kb
• 下载源代码 - 220 Kb

引言

这段代码是对数论的实现。它包含所有基本的算术运算：加法、减法、乘法和除法、移位函数、GCD 等。整数的大小（始终以双字二进制形式，32 位）可以从一位到数千位的规模不等。我使用 C++ 实现了基本运算，但所有编译器生成的机器代码都非常慢。因此，我尝试使用 VC++ 的内联汇编器来完成最关键的速度运算。我认为速度的提升是显著的。

使用代码

这段代码可用于非对称加密算法（如 RSA-DH 等）的密钥生成。它可以为密码学生成非常快速、大型的概率素数（例如，4096 位及以上）。我在使用 Miller Rabin 测试之前，对每个候选素数实现了快速试除法，除数是所有小于 1000000 的素数。我还基于硬盘头部的移动实现了一种“真正”的随机数生成器。有关更多详细信息，请查看 h 和 cpp 文件。

您可以在 CPP 和头文件中找到每个函数的更多详细信息。

//all the code is writen for IA-32 architecture proccesors (486 to pentium 4)

//you can define (and allocate space for) a Large Integer with many ways 

//note that LINT x; is equal to 'x=0'

#include "LargeIntegers.h" 

LINT z(-43),x(211); LINT p,q(1),w,m(-5),r;
//before you put the value from a string to a Linteger, 

//you must call before the 

//global function SetRadix(radix) 

//for radix 0 up to 36 

//the default value for radix 

//(you do not need to call the function )is 10 

//The string scaning, stops to the first character <'0' 

//or >radix or ==0. The minus sign 

// can be at first position only. 

SetRadix(2);
LINT y("100000000000000000000000000000000000000000000000001"); 
LINT df(md);
LINT a("-1000000000000000"),b(20),c(30),d("1000000000000000"); 
SetRadix(10); 
PLINT a6= new LINT(45); 
delete a6;
LINT a1("-112334567896541248490");
SetRadix(16);
LINT a2("-BAC45FDE78912456FF");
//the memory allocated for each LINT depends 

//to MAXLEN in header file (in dwords 32bit )


//You can count the time difference (in millisecs) 

//or the proccesor clocks difference

//at any point of your code by puting before 

//the global Bc(); for proccesor clocks, or Bt();

//for time difference. After the block of code 

//you want to measure the efficiency, you must call

//the global Ac(); for proccesor clocks, or At(); for time difference.

//the result is stored as string to global variable sc.

//here is an example:

Bc();
x.Div1(&y,&m,&r);
Ac();
cout <<"div1 counter diff= "<< sc<<" counts."<<endl<< endl;
//or 

Bt();
x.Div1(&y,&m,&r);
At();
cout <<"div1 time diff= "<< sc<<" milliseconds."<<endl<< endl;
//With the overload arithmetic operators you 

//can use the LINTs as common integers:

x=y+3;
x*=-4;
r=((y+3)-56)/m;
//No complex operations allowed such r= a*x+b*y+c%z..... or f=(a+b)*(c-d)

//because this class can't keep intermediate temporary 

//results for any comlex operation e.g.(a+b)

//You can use this type of complex operation: 


a=((b*c+3+w+r+t)*h/r/r/2+3)%f;
//You can use and the public functions of the class. eg x.Egcd(&y,&m);

//efklidis gcd algorytm. Is equal to m=gcd(x,y)

这是一个使用试除法在 Miller Rabin 方法之前搜索素数的例子

cout <<"give me an odd large number >100000" 
       " and i shall return you the first ten probably primes"\
       " (Miller-Rabin tested with conf factor= 10) :" ;
bg: cin >> buf;
LINT d(buf);
if (d<100001)
  {cout <<"not below 100000 because i use trial" 
          " divisions up to 100000. Retry :" ;goto bg;} 
int times=10;
if(!d.IsOdd())d+=1;
rt: times--;
rt1:if (times<0)goto cnt;
d+=2; if(d.DivTrial(100000)!=0)goto rt1;
if(d.MillerRabinTest(10)==0)cout <<endl<<d<<endl;
else goto rt1;
goto rt; cnt:

另一个 RSA 密钥对生成示例

    unsigned int bits;
    cout <<"give number of bits and i shall generate" 
           " you an RSA key pair (rounded to next 32bits) :" ;
    cin >> bits;
    cout<<endl<<endl;

    LINT pbkmodulus,pbkexponent;
    LINT prkexponent;


    bits/=2;//because the bits value is for modulus not for primes

    LINT tmpkey1;
    LINT tmpkey2;
    //generate p and q

rg:    tmpkey1.MakeRandom(bits);
ag:    tmpkey1.FirstPrimeAbove(5);
    if((tmpkey1.MillerRabinTest(20))!=0) goto ag;
    //make 'sure' this is a 'prime'


    tmpkey2.MakeRandom(bits);
ag1:     tmpkey2.FirstPrimeAbove(5);
    if((tmpkey2.MillerRabinTest(20))!=0) goto ag1;
    //make 'sure' this is a 'prime'


    if (((PLINT)(&(tmpkey1-tmpkey2)))->GetLength()<(bits/32)) goto rg;
    //if the difference is quiet small find some other keys


    //now we have the keys and calculate modulus 

    pbkmodulus= tmpkey1 * tmpkey2;

    //calculate (p-1)*(q-1)

    tmpkey1--;
    tmpkey2--;
    tmpkey1*=tmpkey2;//(p-1)*(q-1)


    //generate exponent for encryption. 

    //I decide to use a random 32 bit prime eg 1073741827;

rg1:     pbkexponent.MakeRandom(32);
    pbkexponent.FirstPrimeAbove(50);
    //gcd test must return one

    pbkexponent.Egcd(&tmpkey1,&tmpkey2);
    if (tmpkey2!=1) goto rg1;
    //if result of gcd !1 then regenerate another number


    //generate exponent for decryption.

    int rslt;
    rslt=pbkexponent.InvMod(&tmpkey1,&prkexponent);
    if (rslt!=0) goto rg1;//if there is not exist, repeat proccess


    tmpkey1.WipeOut();//clear

    tmpkey2.WipeOut();//clear

    LINT::WipeOutAllGlobals();//clear all variables used for key generation

    // usually for security reasons


////////////////////end of key generation ////////////////////////////


    SetRadix(16);
    cout<<"public exponent:  "<<endl<<pbkexponent<<endl<<endl;
    cout<<"private exponent: "<<endl<<prkexponent<<endl<<endl;
    cout<<"modulus:          "<<endl<<pbkmodulus<<endl<<endl;

历史

• v1.0
  • 初始代码发布。
• v1.3
  • 修复了许多错误。
  • 所有函数的速度改进。
  • 实现了新函数。Expmod、GCD、改变基数表示等。
  • 添加了计时器和计数器函数以计算效率。
• v1.4
  • 修复了一些错误。
  • 某些函数（尤其是 div1）的速度改进。
  • 实现了 Barret 模减少、Makeneg、Makepos、Miller-Rabin 测试、DivTrial、IsOdd 和 GetLength。
• v1.5
  • 修复了一些错误。
  • 实现了 prefix、postfix、FromFile、ToFile、FromBuffer、ToBuffer、WipeOut、WipeOutAllGlobals、GetDigit、IsNeg、InvMod、GetRandomBits、MakeRandom。