Test Fermata

Witajcie,
Z góry zaznaczam, że jestem zielona zarówno z zakresu algorytmiki i C++. Mimo to porwałam się na zadanie ze spoj.pl PRIME_T. Chciałam wykorzystać test pierwszości Fermata, ale wynik mam błędny.
to mój kod:

#include <cstdio>
#include <cstdlib> //funkcje rand() i srand()
#include <ctime> //funkcja time()
#include <cmath>

int wylosuj(double p);

int main(){
 int k, a, p, t;
 bool result, unical=true, contiWhile=true;
 int tabRand[3];
 int index=0;
 std::srand (std::time(0)); //mieszanie
 fscanf(stdin, "%d", &t); //ilosc testow

 while(t!=0){
 fscanf(stdin, "%d", &p); //liczba sprawdzana
 result=true;
 k=20;
 //jezeli 1<p<=3 jest pierwsza
 if(p<=1) result=false;
 if(p>3){
   while(k!=0){ //wykonujemy dla k testow
     contiWhile=true;
     while(contiWhile){
     
        a=wylosuj(p-1); //losowanie liczby a
        for(int i=0; i<index; i++){
          if(tabRand[i]==a) unical=false;
        }
        if(unical){
          tabRand[index]=a;
          index++;
          contiWhile=false;
        }
     }
         
     //sprawdzanie warunku z twierdzenia
     if(fmod(pow(a, (p-1)),p)!=1){
       result=false; 
       break;
     }
     k--;     
   }
 }
 //rezultat
 if(result) fprintf(stdout, "TAK\n");
 else fprintf(stdout, "NIE\n");
 index=0;
 t--;
 }

return 0;
}

int wylosuj(double p){
  int max=(int)p;
  return (std::rand() %max)+1;
} 

np. podałam na wejściu liczbę 29. Program wylosował liczbę 27 (jako a).
27^29-1 mod 29=27.

Nie wiem co robię źle. Może ktoś byłby w stanie mi coś podpowiedzieć. Z góry dziękuję :)

nie przyglądałem się kodowi ale 27^28 to całkiem duża liczba - pewnie nie mieści się w pełnej dokładności w wykorzystywanym typie
poza tym test pierwszości Fermata nie daje 100% pewności że liczba jest pierwsza

BTW sprawdziłem i moje zgłoszenie do tego zadania (5 lat temu) wykorzystywało zwykłą pętlę i spokojnie zmieściło się w limicie czasowym - czyżbyś chciała ambitnie wejść do top20? ;>

co dziwne... poprawiłam swój program o metodę, która wymnaża wyliczone wcześniej modulo (takie potęgowanie i modulo razem), wyniki wychodzą mi prawidłowe, ale przekroczyłam dopuszczalny czas :/
@unikalna_nazwa dziękuję za poradę - przydała się. Jak zabraknie mi cierpliwości to też rozwiążę to zadanie metodą naiwną, ale póki co to walczę :)