## 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.

#include <span class="code-string">"LargeIntegers.h" </span>
LINT z(-43),x(211); LINT p,q(1),w,m(-5),r;
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");
Bc();
x.Div1(&y,&m,&r);
Ac();
cout <<"div1 counter diff= "<< sc<<" counts."<<endl<< endl;
Bt();
x.Div1(&y,&m,&r);
At();
cout <<"div1 time diff= "<< sc<<" milliseconds."<<endl<< endl;
x=y+3;
x*=-4;
r=((y+3)-56)/m;
a=((b*c+3+w+r+t)*h/r/r/2+3)%f;

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;
LINT tmpkey1;
LINT tmpkey2;
rg: tmpkey1.MakeRandom(bits);
ag: tmpkey1.FirstPrimeAbove(5);
if((tmpkey1.MillerRabinTest(20))!=0) goto ag;
tmpkey2.MakeRandom(bits);
ag1: tmpkey2.FirstPrimeAbove(5);
if((tmpkey2.MillerRabinTest(20))!=0) goto ag1;
if (((PLINT)(&(tmpkey1-tmpkey2)))->GetLength()<(bits/32)) goto rg;
pbkmodulus= tmpkey1 * tmpkey2;
tmpkey1--;
tmpkey2--;
tmpkey1*=tmpkey2;
rg1: pbkexponent.MakeRandom(32);
pbkexponent.FirstPrimeAbove(50);
pbkexponent.Egcd(&tmpkey1,&tmpkey2);
if (tmpkey2!=1) goto rg1;
int rslt;
rslt=pbkexponent.InvMod(&tmpkey1,&prkexponent);
if (rslt!=0) goto rg1;
tmpkey1.WipeOut();
tmpkey2.WipeOut();
LINT::WipeOutAllGlobals();
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
- 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.