11,486,288 members (76,571 online)

# Large integer class

, 23 Dec 2004 65.2K 2K 27
 Rate this:
A class with multiple precision integer arithmetic operations.

## 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 <span class="code-string">"LargeIntegers.h"
</span>
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
//for radix 0 up to 36
//(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.
LINT y("100000000000000000000000000000000000000000000000001");
LINT df(md);
LINT a("-1000000000000000"),b(20),c(30),d("1000000000000000");
PLINT a6= new LINT(45);
delete a6;
LINT a1("-112334567896541248490");
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 ////////////////////////////

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.

A list of licenses authors might use can be found here

## Share

Software Developer
Greece
No Biography provided

 First Prev Next
 Needs const-correctness Andrew Shepherd15-Aug-07 14:34 Andrew Shepherd 15-Aug-07 14:34
 Problem with VC7 RedDragon2k26-Dec-05 12:15 RedDragon2k 26-Dec-05 12:15
 Re: Problem with VC7 Vagelis Fortunas27-Dec-05 11:44 Vagelis Fortunas 27-Dec-05 11:44
 Re: Problem with VC7 RedDragon2k27-Dec-05 13:36 RedDragon2k 27-Dec-05 13:36
 great work but plz remove the bug taimur8219-Oct-05 23:39 taimur82 19-Oct-05 23:39
 ;another bug... Hyri22-Dec-04 8:32 Hyri 22-Dec-04 8:32
 Re: ;another bug... Vagelis Fortunas22-Dec-04 12:22 Vagelis Fortunas 22-Dec-04 12:22
 ;another bug... Hyri22-Dec-04 8:32 Hyri 22-Dec-04 8:32
 Important Bug! Hyri22-Dec-04 7:34 Hyri 22-Dec-04 7:34
 Re: Important Bug! Vagelis Fortunas22-Dec-04 12:01 Vagelis Fortunas 22-Dec-04 12:01
 Another One Can Be Found At: RedZenBird8-Dec-04 9:36 RedZenBird 8-Dec-04 9:36
 very nice mier25-Nov-04 6:34 mier 25-Nov-04 6:34
 Re: very nice Vagelis Fortunas25-Nov-04 11:36 Vagelis Fortunas 25-Nov-04 11:36
 nice! zilog71815-Nov-04 6:01 zilog718 15-Nov-04 6:01
 Last Visit: 31-Dec-99 19:00     Last Update: 26-May-15 0:23 Refresh 1