Click here to Skip to main content
Click here to Skip to main content

Large integer class

, 23 Dec 2004
Rate this:
Please Sign up or sign in to vote.
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 
//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.

License

This article has no explicit license attached to it but may contain usage terms in the article text or the download files themselves. If in doubt please contact the author via the discussion board below.

A list of licenses authors might use can be found here

Share

About the Author

Vangelis Fortounas
Software Developer
Greece Greece
No Biography provided

Comments and Discussions

 
GeneralNeeds const-correctness PinmemberAndrew Shepherd15-Aug-07 13:34 
GeneralProblem with VC7 PinmemberRedDragon2k26-Dec-05 11:15 
GeneralRe: Problem with VC7 PinmemberVagelis Fortunas27-Dec-05 10:44 
GeneralRe: Problem with VC7 PinmemberRedDragon2k27-Dec-05 12:36 
Generalgreat work but plz remove the bug Pinmembertaimur8219-Oct-05 22:39 
General;another bug... PinmemberHyri22-Dec-04 7:32 
GeneralRe: ;another bug... PinmemberVagelis Fortunas22-Dec-04 11:22 
General;another bug... PinmemberHyri22-Dec-04 7:32 
GeneralImportant Bug! PinmemberHyri22-Dec-04 6:34 
GeneralRe: Important Bug! PinmemberVagelis Fortunas22-Dec-04 11:01 
GeneralAnother One Can Be Found At: PinmemberRedZenBird8-Dec-04 8:36 
Generalvery nice Pinmembermier25-Nov-04 5:34 
GeneralRe: very nice PinmemberVagelis Fortunas25-Nov-04 10:36 
Generalnice! Pinmemberzilog71815-Nov-04 5:01 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

| Advertise | Privacy | Mobile
Web02 | 2.8.140821.2 | Last Updated 23 Dec 2004
Article Copyright 2004 by Vangelis Fortounas
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid