galois_field_p.c

/*
* Cryptography and Network Security Assignment (CNWS)
* Topic  :  Finite Fields of the Form GF(p) [Galois Field]
* Name   :  Brijesh Bittu
* Roll   :  BE/1091/2010
* Branch :  ECE
*/

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

// to check whether the input is prime or not
int isPrime(int);

// to find the multiplicative inverse of a(mod p)
int multiplicativeInverse(int,int);

// format the output
void underScore(int);

// to calculate the addition table
void genAdditionTable(int*,int);

// to calculate the additive inverse of numbers 0,1,2,....,p-1
void genAdditiveInverse(int*,int*,int);

// to calculate the multiplication table
void genMultiplicationTable(int*,int);

/* to calculate the multiplicative inverse of numbers 0,1,2,....,p-1
*  using Extended Euclidean Algorithm
*/
void genMultiplicativeInverse(int*,int*,int);

int main(int argc, char const *argv[])
{
	int p,i,j;
	int *add,*mul,*addI,*mulI;
	printf("Enter a prime number p for GF(p): ");
	scanf("%d",&p);
	while(!isPrime(p)){
		printf("Enter a prime number p for GF(p): ");
		scanf("%d",&p);
	}
	genAdditionTable(add,p);
	genMultiplicationTable(mul,p);
	genAdditiveInverse(addI,add,p);
	genMultiplicativeInverse(mulI,mul,p);
	return 0;
}

int isPrime(int p){
	int i;
	int sq = sqrt(p);
	for(i=2;i<=sq;i++){
		if(p%i==0)
			return 0;
	}
	return 1;
}

int multiplicativeInverse(int a,int b){
	if(a==0) return -1;
	int b0 = b, t, q;
	int x0 = 0, x1 = 1;
	if(b==1) return 1;
	while(a>1){
		q = a/b;
		t = b, b = a%b, a = t;
		t = x0, x0 = x1 - q*x0, x1 = t;
	}
	if(x1<0)
		x1+=b0;
	return x1;
}

void underScore(int p){
	int i;
	printf("\n");
	for(i=0;i<=p;i++){
		printf("______");
	}
	printf("\n");
}

void genAdditionTable(int *add,int p){
	int i,j;
	printf("\nAddition table for p = %d\n\n", p);
	add = (int*)malloc(sizeof(int)*p*p);
	printf("  + | ");
	for(i=0;i<p;i++){
		printf("%3d | ", i);
	}
	underScore(p);
	for(i=0;i<p;i++){
		printf("%3d | ", i);
		for(j=0;j<p;j++){
			*((add + (p*(i)))+j) = (i+j)%p;
			printf("%3d | ", *((add + (p*(i)))+j));
		}
		printf("\n");
	}
	printf("\n");
}

void genAdditiveInverse(int *ai,int *a,int p){
	ai = (int*)malloc(sizeof(int)*p);
	int i;
	printf("\nAdditive Inverse table for p = %d:\n", p);
	printf("  w | -w \n");
	for(i=0;i<p;i++){
		if(i==0)
			*(ai+i) = 0;
		else
			*(ai+i) = p-i;
		printf("%3d |%3d\n", i,*(ai+i));
	}
}

void genMultiplicationTable(int *mul,int p){
	int i,j;
	printf("\nMultiplication table for p = %d\n\n", p);
	mul = (int*)malloc(sizeof(int)*p*p);
	printf("  * | ");
	for(i=0;i<p;i++){
		printf("%3d | ", i);
	}
	underScore(p);
	for(i=0;i<p;i++){
		printf("%3d | ", i);
		for(j=0;j<p;j++){
			*((mul + (p*(i)))+j) = (i*j)%p;
			printf("%3d | ", *((mul + (p*(i)))+j));
		}
		printf("\n");
	}
	printf("\n");
}

void genMultiplicativeInverse(int *ai,int *mul,int p){
	ai = (int*)malloc(sizeof(int)*p);
	int i;
	printf("\nMultiplicative Inverse table for p = %d:\n", p);
	printf("  w | w^(-1) \n");
	for(i=0;i<p;i++){
		*(ai+i) = multiplicativeInverse(i,p);
		printf("%3d |%3d\n", i,*(ai+i));
	}
}