Large integer class

• Download demo program - 160 Kb
• Download source - 220 Kb

Introduction

This piece of code is an implementation of arithmetic theory. It contains all the basic arithmetic operations: addition, subtraction, multiplication and division, shift functions, GCD etc. The size of integers (always in binary double words, 32 bit) can vary from one digit to many decades of thousand digits. I implemented the basic operations with C++, but all compilers generate very slow machine code. For this reason, I tried to make the most speed-critical operations with the inline assembler of VC++. I think that the improvement in speed is significant.

Using the code

This code can be used for key generation for non symmetric cryptographic algorithms such RSA-DH etc. It can produce very fast, large probable primes (e.g., 4096 and above bits) for use in cryptography. I implemented a fast trial division with all primes up to 1000000 for each candidate prime prior to Miller Rabin test. I also implemented a kind of 'true' random generator based to hard disk's head movement. Look in the h and cpp files for more details.

You can find more details for each function in the CPP and header files.

//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)

Here is an example of prime searching using the trial divisions prior to using the Miller Rabin method:

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:

And another example of RSA key-pair generation:

    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;

History

• v1.0
  • Initial code release.
• v1.3
  • A lot of bugs fixed.
  • Speed improvement for all functions.
  • New functions implemented. Expmod, GCD, change radix representation etc.
  • Timer and counter functions added for counting efficiency.
• v1.4
  • Some bugs fixed.
  • Speed improvement for some functions (especially div1).
  • Barret modular reduction, Makeneg, Makepos, Miller-Rabin Test, DivTrial, IsOdd and GetLength implemented.
• v1.5
  • Some bugs fixed.
  • prefix, postfix, FromFile, ToFile, FromBuffer, ToBuffer, WipeOut, WipeOutAllGlobals, GetDigit, IsNeg, InvMod, GetRandomBits, MakeRandom implemented.