#include <stdio.h>
#include <conio.h>
#include <stdlib.h>
#include <time.h>

int alg(unsigned long int, unsigned long int);
int extended_euclid(long , long );
char* binary_num (unsigned long int, int * );
unsigned long int crypt(unsigned long int, const char *, const unsigned long int, const int);
int* entering_num(int *);

int prost[64]={
1009,1039,1087,1117,1171,1217,1259,1297,
1327,1409,2027,2081,2113,2153,2221,2269,
2309,2351,2389,3019,3067,3121,3187,3229,
3299,3329,3371,3433,4007,4051,4099,4153,
4217,4253,4289,4357,4421,4463,5021,5081,
5119,5189,5237,5303,5381,5417,5449,5503,
5557,5623,6037,6079,6131,6197,6229,6277,
6323,6421,6481,6553,7001,7057,7127,7193};

unsigned long int emas[5]={3, 17, 33, 65, 65536};

int i, j;

int main(){
        unsigned long int n, e, fm, k=0, d, c, m=0;
        int p, q, size, size_mes, *mes;
        char *num_e;
        int nStartValue = time(NULL);
        srand(nStartValue);
//p и q - простые числа
        p=prost[random(64)];
        q=prost[random(64)];
        n=p*q;
        printf("p=%d, q=%d, n=%ld",p, q, n);
//fm - функция эйлера
        fm=(p-1)*(q-1);
        e=emas[random(4)];

        while(alg(fm, e)!=1){
                e=emas[random(4)];
                ++k;
                if(k>6){
                        printf("\nerror!!!\n");
                        getch();
                        return 0;
                }
        }

        d=extended_euclid(fm, e);
        num_e=binary_num(e, &size);
        printf("\nenter the information: ");
        mes=entering_num(&size_mes);
        i=0;
        while(i<size_mes){
                m=0;
                if((size_mes-i)<6)
                        for(; i<size_mes; ++i)
                                m=m*10+mes[i];
                else{
                        m=m*10+mes[i];
                        ++i;
                        m=m*10+mes[i];
                        ++i;
                        m=m*10+mes[i];
                        ++i;
                        m=m*10+mes[i];
                        ++i;
                        m=m*10+mes[i];
                        ++i;
                        m=m*10+mes[i];
                        ++i;
                }
                printf("\nm=%ld ", m);
                c=crypt(m, num_e, n, size);
                printf("\n%ld ", c);

        }
        //-------------------проверка-------------
        printf("\nalg=%ld, fm=%ld, e=%ld, d=%ld, m=%ld", alg(fm, e), fm, e, d, m);
        printf("\n");

        printf("\nc=%ld", c);
        //------------------конец проверки--------


        getch();
        return 0;
}

int alg(unsigned long int a, unsigned long int b){
unsigned long int c;
while(b){
        c=a%b;
        a=b;
        b=c;
}
return a;
}

int extended_euclid(long a, long b){
        long q, r, x1, x2, y1, y2, x, y, d;
        x2=1, x1=0, y2=0, y1=1;
        while(b>0){
                q=a/b;
                r=a-q*b;
                x=x2-q*x1;
                y=y2-q*y1;
                a=b;
                b=r;
                x2=x1;
                x1=x;
                y2=y1;
                y1=y;
        }
        y=y2;
        if(y<0)
                return -y;
        return y;
}

char* binary_num (unsigned long int a, int *size){
        int i=0, j, c;
        char *res, k;
        res=(char *)malloc(sizeof(char *));

        while(a){
                c=a%2;
                a=a/2;
                res[i]=c;
                ++i;
                res=(char *)realloc(res, sizeof(char *)*i);
        }
        res[i]='\0';
        *size=i;
        if(*size%2){
                for(i=0, j=*size-1; i!=j; ++i, --j){
                        k=res[j];
                        res[j]=res[i];
                        res[i]=k;
                }
        }
        else{
                for(i=0, j=*size-1; i!=*size/2; ++i, --j){
                        k=res[j];
                        res[j]=res[i];
                        res[i]=k;
                }
        }
        return (res);
}

unsigned long int crypt(unsigned long int m, const char *num, const unsigned long int n, const int size){
        unsigned long int c;
        c=m;
        i=0;
        if(num[i]==1)
                i=1;
        else
                i=0;
        for(; i<size; ++i){
                if(num[i]){
                        m=(m*m)%n;
                        m=(m*c)%n;
                }
                else{
                        m=(m*m)%n;
                }
        }
        return m;
}

int* entering_num(int *size){
        int *mas;
        char ch;
        mas=(int *)malloc(sizeof(int));
        for(i=0; (ch=getch())!='\r'; ){
                if ((ch=='\b')&&i){
			printf("\b \b");
			--i;
			continue;
			}
                        putchar(ch);
                        mas=(int *)realloc(mas, sizeof(int *)*(i+3));
                        mas[i]=ch/100;
                        mas[i+1]=(ch/10)%10;
                        mas[i+2]=ch%10;
                        i=i+3;
        }
        *size=i;
        return (mas);
}