математика — проблема первичности Миллера-Рабина в переполнении стека

Я пытался реализовать алгоритм из википедии и хотя он никогда не выводит составные числа в виде простых чисел, он выводит около 75% простых чисел в виде составных.

До 1000 это дает мне вывод для простых чисел:

3, 5, 7, 11, 13, 17, 41, 97, 193, 257, 641, 769

Насколько я знаю, моя реализация точно так же, как алгоритм псевдокода. Я отладил его построчно, и он вывел все ожидаемые значения переменных (я следовал вместе со своим калькулятором). Вот моя функция:

bool primeTest(int n)
{
int s = 0;
int d = n - 1;

while (d % 2 == 0)
{
d /= 2;
s++;
}

// this is the LOOP from the pseudo-algorithm
for (int i = 0; i < 10; i++)
{
int range = n - 4;
int a = rand() % range + 2;
//int a = rand() % (n/2 - 2) + 2;
bool skip = false;
long x = long(pow(a, d)) % n;

if (x == 1 || x == n - 1)
continue;

for (int r = 1; r < s; r++)
{
x = long(pow(x, 2)) % n;

if (x == 1)
{
// is not prime
return false;
}
else if (x == n - 1)
{
skip = true;
break;
}
}

if (!skip)
{
// is not prime
return false;
}
}

// is prime
return true;
}

Любая помощь будет оценена D:

РЕДАКТИРОВАТЬ: Вот вся программа, отредактированная, как вы, ребята, предложили, — и теперь вывод еще более нарушен

bool primeTest(int n);

int main()
{
int count = 1;     // number of found primes, 2 being the first of course
int maxCount = 10001;
long n = 3;
long maxN = 1000;
long prime = 0;

while (count < maxCount && n <= maxN)
{
if (primeTest(n))
{
prime = n;
cout << prime << endl;
count++;
}

n += 2;
}

//cout << prime;
return 0;
}

bool primeTest(int n)
{
int s = 0;
int d = n - 1;

while (d % 2 == 0)
{
d /= 2;
s++;
}

for (int i = 0; i < 10; i++)
{
int range = n - 4;
int a = rand() % range + 2;
//int a = rand() % (n/2 - 2) + 2;
bool skip = false;
//long x = long(pow(a, d)) % n;
long x = a;
for (int z = 1; z < d; z++)
{
x *= x;
}

x = x % n;

if (x == 1 || x == n - 1)
continue;

for (int r = 1; r < s; r++)
{
//x = long(pow(x, 2)) % n;
x = (x * x) % n;

if (x == 1)
{
return false;
}
else if (x == n - 1)
{
skip = true;
break;
}
}

if (!skip)
{
return false;
}
}

return true;
}

Теперь вывод простых чисел от 3 до 1000 (как и раньше) составляет:

3, 5, 17, 257

Теперь я вижу, что x становится слишком большим и просто превращается в мусорное значение, но я не видел этого, пока не удалил часть «% n».