What is the best algorithm to determine if N is a prime number (if N is [2 <= N <= 2^63-1])?

Question

I tried using the Miller-Rabin algorithm, but it can't detect very large numbers.

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

long long mulmod(long long a, long long b, long long mod)
{
    long long x = 0,y = a % mod;
    while (b > 0)
    {
        if (b % 2 == 1)
        {    
            x = (x + y) % mod;
        }
        y = (y * 2) % mod;
        b /= 2;
    }
    return x % mod;
}

long long modulo(long long base, long long exponent, long long mod)
{
    long long x = 1;
    long long y = base;
    while (exponent > 0)
    {
        if (exponent % 2 == 1)
        {
            x = (x * y) % mod;  
        }
        y = (y * y) % mod;
        exponent = exponent / 2;
    }
    return x % mod;
}

int Miller(unsigned long long int p, int iteration)
{
    int i;
    long long s;
    if (p < 2)
    {
        return 0;
    }
    if (p != 2 && p % 2==0)
    {
        return 0;
    }
    s = p - 1;
    while (s % 2 == 0)
    {
        s /= 2;
    }
    for (i = 0; i < iteration; i++)
    {
        long long a = rand() % (p - 1) + 1, temp = s;
        long long mod = modulo(a, temp, p);
        while (temp != p - 1 && mod != 1 && mod != p - 1)
        {
            mod = mulmod(mod, mod, p);
            temp *= 2;
        }
        if (mod != p - 1 && temp % 2 == 0)
        {
            return 0;
        }
    }
    return 1;
}

int main()
{
    int iteration = 5, cases;
    unsigned long long int num;
    scanf("%d", &cases);
    for(int i = 0; i < cases; i++)
    {
        scanf("%llu", &num);
        if(Miller(num, iteration))
        {
            printf("YES\n");    
        } 
        else
        {
            printf("NO\n");
        }   
    }
    return 0;
}

Output examples:

10 //cases
1
NO
2
YES
3
YES
4
NO
5
YES
1299827
YES
1951
YES
379
YES
3380
NO
12102
NO

I am trying to do my homework by creating a program that tells if a number is prime or not, print out YES if prime, NO if not. However, every time I submit the code to the online judge it just says "Wrong answer", when even my last attempt to do the assignment was without any efficient algorithm it says "Time limit exceeded".

Is there any way to determine if N is a prime number or not when N is [2 <= N <= 2^63-1]?

Answer 1

OP's code has many possibilities of overflowing 63-bit math. e.g. x * y in x = (x * y) % mod;

At a minimum, recommend to go to unsigned math. e.g.: long long --> unsigned long long or simply uintmax_t.

For a mulmod() that does not overflow: Modular exponentiation without range restriction.

---

I'll look more into this later. GTG.