Eucledian Algorithm for Linear Congruence (C version)

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

typedef struct t_eucledian_field {
    int a;
    int b;
    int a_per_b;
    int x;
    int y;
    struct t_eucledian_field* next;
    struct t_eucledian_field* prev;
} EucledianField;

typedef EucledianField* EucledianTableEntry;
EucledianTableEntry FindFirst(EucledianTableEntry anchor);
EucledianTableEntry FindLast(EucledianTableEntry anchor);
void FreeField(EucledianTableEntry anchor);
EucledianTableEntry CalculateGreatestCommonDenom(int xa, int yb);
EucledianTableEntry EucledianAlgorithm(int xa, int yb);

typedef struct t_rsa_coder {
    int p;
    int q;
    int n; // n = p * q
    int e; // relative prime to (p-1)*(q-1)
    int d; // (e*d) % (p-1)*(q-1) = 1
    // n and e are public
    // p, q, d are private
} RsaCoder;
typedef RsaCoder* Coder;

Coder GenerateCoder(int p, int q);
int modpower(int x, unsigned int y, int p);
int code(int signal, Coder rsa);
int decode(int signal, Coder rsa);
char prime(int n);

int main(void) {
    // your code goes here
    /*EucledianTableEntry a = EucledianAlgorithm(2070,125);
    EucledianTableEntry to_delete = a;
    do {
        printf("A: %d \t B: %d \t A\\B: %d \t X: %d \t Y: %d \n",a->a,a->b,a->a_per_b,a->x,a->y);
        //to_delete = a;
        a = a->next;
        //free(to_delete);
    }while (a);
    FreeField(to_delete);*/
    Coder a;
    int p;
    int q;
    srand(time(NULL));
    p = 3 + rand() % 13;
    q = rand() % (p - 3);
    a = GenerateCoder(p,q);
    printf("Coder:\n P=%d \n Q=%d \n N=%d \n E=%d \n D=%d\n\n",a->p, a->q, a->n, a->e, a->d);
    printf("Coding and decoding: 2 -> %d -> %d\n",code(2,a),decode(code(2,a),a) );
    return 0;
}
EucledianTableEntry FindFirst(EucledianTableEntry anchor)
{
    EucledianTableEntry tmp = anchor;
    if(!anchor->prev) return tmp; // Already first
    do
    {
        tmp = tmp->prev;
    } while(tmp->prev);
    return tmp;
}
EucledianTableEntry FindLast(EucledianTableEntry anchor)
{
    EucledianTableEntry tmp = anchor;
    if(!anchor->next) return tmp; // Already last
    do
    {
        tmp = tmp->next;
    } while(tmp->next);
    return tmp;
}
void FreeField(EucledianTableEntry anchor)
{
    EucledianTableEntry tmp = FindFirst(anchor);
    do
    {
        tmp = tmp->next;
        free(tmp->prev);
    } while(tmp->next);
    free(tmp);
}
EucledianTableEntry CalculateGreatestCommonDenom(int xa, int yb)
{
    EucledianTableEntry first=0,tmp=0,anchor=0;
    first = (EucledianTableEntry)malloc(sizeof(EucledianField));
    tmp = first;
    if(xa > yb)
    {
    tmp->a = xa;
    tmp->b = yb;
    }
    else
    {
        tmp->a = yb;
        tmp->b = xa;
    }
    tmp->a_per_b = tmp->a / tmp->b;
    tmp->x = 0;
    tmp->y = 0;
    tmp->prev = 0;
    tmp->next = 0;
    //printf("A: %d \t B: %d \t A\\B: %d\n",tmp->a,tmp->b,tmp->a_per_b);
    do {
        anchor = tmp;
        tmp = (EucledianTableEntry)malloc(sizeof(EucledianField));
        anchor->next = tmp;
        tmp->prev = anchor;
        tmp->next = 0;
        tmp->a = anchor->b;
        tmp->b = anchor->a % anchor->b;
        if(tmp->b) tmp->a_per_b = tmp->a / tmp->b;
        else tmp->a_per_b = 1;
        tmp->x = 0;
        tmp->y = 0;
        //printf("A: %d \t B: %d \t A\\B: %d\n",tmp->a,tmp->b,tmp->a_per_b);
    } while(tmp->b);
    return first;
}
EucledianTableEntry EucledianAlgorithm(int xa, int yb)
{
    EucledianTableEntry first=0,anchor=0;
    first = CalculateGreatestCommonDenom(xa,yb);
    anchor = FindLast(first); // We start from the end.
    anchor->x = anchor->a;
    anchor->y = anchor->b;
    anchor = anchor->prev;
    do {
        anchor->x = anchor->next->y;
        anchor->y = anchor->next->x - (anchor->a_per_b * anchor->next->y);
        anchor = anchor->prev;
    } while(anchor);
    return first;
}
/* Iterative Function to calculate (x^y)%p in O(log y) */
int modpower(int x, unsigned int y, int p)
{
    int res = 1;      // Initialize result

    x = x % p;  // Update x if it is more than or
                // equal to p

    while (y > 0)
    {
        // If y is odd, multiply x with result
        if (y & 1)
            res = (res*x) % p;

        // y must be even now
        y = y>>1; // y = y/2
        x = (x*x) % p;
    }
    return res;
}

Coder GenerateCoder(int p, int q)
{
    Coder temp;
    EucledianTableEntry counter;
    temp = (Coder)malloc(sizeof(RsaCoder));
    temp->p = primize(p);
    temp->q = primize(q);
    if(temp->q == temp->p)
    {
        temp->q = primize(temp->p+2);
    }
    if(temp->q < temp->p) temp->e = primize(temp->p + 2);
    else temp->e = primize(temp->q + 2);
    temp->n = temp->q * temp->p;
    counter = EucledianAlgorithm((temp->p - 1) * (temp->q - 1),temp->e);
    temp->d = counter->y;
    if(temp->d < 0) temp->d += counter->a;
    FreeField(counter);
    return temp;
}
int code(int signal, Coder rsa)
{
    return modpower(signal,rsa->e,rsa->n);
}
int decode(int signal, Coder rsa)
{
    return modpower(signal,rsa->d,rsa->n);
}
char prime(int n)
{
    int i;
    char flag = 0;
    for(i=2; i<=n/2; ++i)
    {
        // condition for nonprime number
        if(n%i==0)
        {
            flag=1;
            break;
        }
    }
    return !flag;
}
int primize(int n)
{
    int tmp = n;
    if(prime(tmp)) return tmp;
    else
    {
        do
        {
            ++tmp;
        } while(!prime(tmp));
    }
    return tmp;
}