Затруднения в реализации теста Ферма

[Phoenix777]

В книге Смарта был дан следующий алгоритм для реализации теста Ферма на псевдокоде (число является псевдопростым, если a^N-1=mod(n) - может быть и составным с некоторой вероятностью и 100% составным в противном случае):

for (i=0; i<k; i++)
{
выбрать a из [2,...,n-1];
b=a^(n-1)modn;
if (b!=1)
{
напечатать (составное, a)
exit;
}
}

напечатать правдоподобно простое

Вот моя реализация на C++:

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

using namespace std;

int main()
{
int n; //проверяемое число  
int i; //счетчик циклов
int k; //количество циклов
int a; //основание
int b;
cout << "Test Ferma" << endl << "Enter number: ";
cin >>n;
cout << "Kolichestvo tsiklov: ";
cin >>k;
bool sim_prime; 
sim_prime=true; //предположение, что число n правдоподобно простое  
int rand_2toN(int n);
for (i=0; i<k; i++) //проверка на простоту
{
a=rand_2toN(n)+1;  // выбор случайного основания от 2 до n-1
b=(static_cast<int>(pow(a, n-1)))%n;     
if (b!=1)
{
sim_prime=false;
break;
}
}
if (sim_prime)
cout << "Chislo pravdopodobno prostoe";
else
cout << "Chislo sostavnoe " << a << " - svidetel'";
cin.get();
cin.get();
return 0;
}
int rand_2toN(int n)
{
return rand() %n-3;   
}

Методом проб понял, что проблема заключается в вычислении цикла - значение a^N-1(modn) ((static_cast<int>(pow(a, n-1)))%n) вычисляется неверно - получаются различные числа, отличные от единицы для простых чисел, а согласно Ферма a^N-1=1(modn). Не могу найти причину, пожалуйста подскажите, если знаете, спасибо.

moderator: Используйте тег <CODE>

[B_N]

Вы бы проверили не методом проб и ошибок, а отладчиком, разбив всё подозрительное выражение на составные части для удобства. Скорее всего проблема как раз в переходе от вещественных чисел к целым, попробуйте возводить в степень перемножением. Если не поможет, будем смотреть внимательно.

[Phoenix777]

Переписал строчку с преобразованием следующим образом, не помогло:

for (j=0; j<(n-1); j++)
{
m=m*a;    
}
b=m%n;