12,350,134 members (27,903 online)
alternative version

66.8K views
27 bookmarked
Posted

# Large integer class

, 23 Dec 2004
 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>```

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

## You may also be interested in...

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