Untitled

#include <stdio.h>

#include <string.h>

 

void dec2bin(int dec, char *bin);

int SaM(int x, int p, char *b_bin);

 

int main(int argc, char *argv[]) {

        int a, b, m, result;

        char b_bin[32];

 

        if (argc != 4) {

                fprintf(stderr, "Usage: %s [a] [b] [m]\n for a^b mod m", argv[0]);

                return -1;

        }

         

        a = atoi(argv[1]);

        b = atoi(argv[2]);

        m = atoi(argv[3]);

 

        memset(b_bin, 0, 32);

         

        dec2bin(b, b_bin);

        printf("######################################\n*Binary value of %d is %s\n######################################\n\n", b, b_bin);

        printf("######################################\n*I am now calculating %d^%d mod %d \n######################################\n", a, b, m);

        result = SaM(a, m, b_bin);

        printf("######################################\n*My result is %d\n######################################\n", result);

        return 1;

}

 

void dec2bin(int dec, char *bin) {

         

        /* This function returns the binary value of the given integer in the following pattern:

         * least significant bit --------------------> most significant bit  

         */

 

        int i = 0;

        while ( dec > 0 ) {

                if(dec % 2 == 0)

                        bin[i] = '0';

                if(dec % 2 == 1)

                        bin[i] = '1';

                dec = dec / 2;

                i++;

        }

}

 

int SaM(int x, int m, char *y_bin) {

 

        /* This implements the actual square and multiply algorithm for x^y, the problem is that the bin algorithm above returns the bit sequence in the wrong order, so we need to run backwards here

         */

        int MsB=0;

        while (y_bin[++MsB] != '\0');

        int i, a;  

        a = x;

        for (i = MsB-2; i >= 0; i--) {

                x = (x*x) % m;

                if (y_bin[i] == '1')  

                        x = (a*x) % m;

         

                printf("got an %c my result is %d \n", y_bin[i], x);

        }

         

        return x;

 

}