Обратное число по модулю / RSA

Пытаюсь реализовать генерацию параметров для алгоритма RSA, но при вычислении параметра d, где d = e^-1 mod f получаю неверный ответ. Это происходит непостоянно и иногда, при новом запуске программы я получаю верное значение d. Все параметры и результаты вычисления программы я проверял с помощью онлайн - калькуляторов. В чем может быть проблема?

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

#define uint64 unsigned long long

uint64 gcd(uint64 a, uint64 b);
uint64 exgcd(uint64 a, uint64 b, uint64* x, uint64* y);
uint64 modInv(uint64 a, uint64 m);

int main()
{
    // Инициализация p

    uint64 p = 1009;
    printf("p: %llu\n\n", p);

    // Инициализация q

    uint64 q = 1013;
    printf("q: %llu\n\n", q);

    // Вычисление n
    // n = p * q

    uint64 n = p * q;
    printf("N: %llu\n\n", n);

    // Вычисление f
    // f = (p - 1) * (q - 1);

    uint64 f = (p - 1) * (q - 1);
    printf("f: %llu\n\n", f);

    // Вычисление e
    // e < f and gcd(e,f) == 1

    uint64 e;
    do
    {
        srand(time(NULL));
        e = 1 + (rand() % ((f - 1) - 1));
        sleep(1);

    }while (gcd(e, f) != 1);
    printf("e: %llu\n\n", e);

    // Вычисление d
    // d = e^-1 mod f

    uint64 d = modInv(e, f);
    printf("d: %llu\n", d);

    return 0;
}



// Алгоритм Евклида

uint64 gcd(uint64 a, uint64 b)
{
    while (b)
    {
        a %= b;
        uint64 tempVar = a;
        a = b;
        b = tempVar;
    }
    return a;
}

// Расширенный алгоритм Евклида

uint64 exgcd(uint64 a, uint64 b, uint64* x, uint64* y)
{
    if (a == 0)
    {
        *x = 0;
        *y = 1;
        return b;
    }

    uint64 x1;
    uint64 y1;
    uint64 gcd = exgcd(b % a, a, &x1, &y1);

    *x = y1 - (b / a) * x1;
    *y = x1;

    return gcd;
}

// Инверсия числа а по модулю m

uint64 modInv(uint64 a, uint64 m)
{
    uint64 x, y;
    uint64 g = exgcd(a, m, &x, &y);
    if (g != 1)
    {
        printf("\nNO SOLUTION\n");
        return 0;
    }
    else
    {
        uint64 res = (x % m + m) % m;
        return res;
    } 
}

UPD

Проблема была в использовании беззнакового типа данных у переменных в функциях exgcd() и modInv(). Изменение типа данных на знаковый long long решает проблему