#include<stdio.h>
#include<conio.h>
#include<iostream>
using namespace std;
int mod(int r2, int r1)
{
int i,j,q,r,t1=0,t2=1,t;
i=r2;j=r1;
cout<<"Expression being evaluated is "<<r2<<"^-1 MOD "<<r1<<endl;
do
{
for(q=1;;q++)
{
t=q*r2;
if(t>r1) { q--; break;}
}
r=r1-(q*r2);
t=t1-(q*t2);
r1=r2;
r2=r;
t1=t2;
t2=t;
if(r2==0) {break;}
}while(r2!=0);
if(r1==1)
{
cout<<"Inverse exists"<<endl;
if(t1>0) cout<<"The inverse is "<<t1<<endl;
else {t1=t1+j; cout<<"The inverse is "<<t1<<endl;}
}
else
{
cout<<"The inverse doesnt exist"<<endl;
}
return t1;
}
int gcd(int a, int b)
{
if (a == 0)
return b;
return gcd(b%a, a);
}
int bif(int n)
{
unsigned int result = 1;
for (int i=2; i<n; i++)
if (gcd(i, n) == 1)
result++;
return result;
}
int cp(int n)
{
int i,c=0;
for(i=1;i<=n/2;i++)
{
if(n%i==0) c++;
}
if(c==1) return 1;
else return 0;
}
int main()
{
int phi,i,n,p=3,q=11,e,d;
srand(time(NULL));
/*for(;;)
{
p=rand()%1000;
//cout<<"Random p "<<p<<endl;
if(cp(p)==1) break;
//cout<<"prime check for p "<<cp(p)<<endl;
}
for(;;)
{
q=rand()%1000;
//cout<<"Random p "<<p<<endl;
if(cp(q)==1) break;
//cout<<"prime check for p "<<cp(p)<<endl;
}*/
cout<<"p is "<<p<<endl;
cout<<"q is "<<q<<endl;
n=p*q;
if(n==1) phi=0;
else if(cp(n)==1) phi=n-1;
else
{
phi=bif(n);
}
cout<<"Phi has been calculated"<<endl;
label: for(;;)
{
//cout<<"working"<<endl;
e=rand();
if(e>1&&e<phi&&gcd(e,phi)==1) break;
}
cout<<"e has been calculated"<<endl;
d=mod(e,phi);
//if((e*d)%n!=1) goto label;
cout<<"The public key is "<<e<<" and "<<n<<endl;
cout<<"The private key is "<<d<<endl;
getch();
return 0;
}
