Помогите найти ошибку, пожалуйста!
На нечетных числах просто зависает....


Это сообщение отредактировал(а) Splendid - 11.6.2008, 08:51

Splendid, 
функция involution_on_mod не понятно что возвращает

если я правильно понял - программа должна определять взаимную простоту 2х чисел?


Это сообщение отредактировал(а) rrrFer - 10.6.2008, 12:10

нет, программа должна проверять число на простоту

Добавлено через 47 секунд
но вычисление НОД там тоже присутствует, как часть алгоритма

Добавлено через 1 минуту и 46 секунд
вот сам алгоритм теста:

Вероятностный тест Миллера-Рабина

Пусть n — нечетное и n − 1 = 2st, t — нечетное. 
Если число n является простым, то при всех a > 1 выполняется сравнение 
an−1 ≡ 1 (mod n) 
Поэтому, рассматривая элементы {at, a2t, …, a2s−1t} можно заметить, что либо среди них найдется равный −1 (mod n), либо at ≡ 1 (mod n). 
На этом замечании основан следующий вероятностный тест простоты:
1.    выбираем случайное число a из интервала {1, 2, …, n−1} и проверяем с помощью алгоритма Евклида условие (a, n) = 1; 
2.    если оно не выполняется, то ответ «n — составное»; 
3.    вычисляем at (mod n); 
4.    если at ≡ ±1 (mod n), то переходим к п. 1; 
5.    вычисляем a2t, …, a2s−1t до тех пор, пока не появится −1; 
6.    если ни одно из этих чисел не равно −1, то ответ «n — составное»; 
7.    если мы достигли −1, то ответ неизвестен (и тест можно повторить еще раз).

Добавлено через 10 минут и 23 секунды
здесь и а - в степени и t в степени

Splendid, 


а насчет того алгоритма, котоый вы написали...два первых шага уже обеспечивают  вероятность неправильной работы программы в ряде случаев:
1.    выбираем случайное число a из интервала {1, 2, …, n−1} и проверяем с помощью алгоритма Евклида условие (a, n) = 1; 
2.    если оно не выполняется, то ответ «n — составное»; 

а в чем неправильность?

Splendid, 
число случайное...

т.е. мне нужно как-то прикрутить сюда еще генератор случ.чисел?

Splendid, зачем генератор? Просто функции rand() будет достаточно (только srand на забудь вызвать в начале программы, передав текущее время в качестве параметра).

bsa, а можно пример, никогда этой функцией не пользовалась...

Splendid, 

если srand не вызывать, то работать будет, но числа будут одни и теже каждый раз...(т.е. генерируютсяи вроде-бы случайные, но при любом запуске программы одинаковые). Можно также использовать randomize() и random(), но не все компиляторы их поддерживают

Это сообщение отредактировал(а) rrrFer - 10.6.2008, 14:33

понятно, спасибо!
Но это дела не изменило, все равно работает не так, может Вы опытным взглядом еще какую-нить ошибку видите?

Спасибо! с ошибками разобралась, код за ненадобностью убрала

Splendid, ИМХО не стоило убирать код. Возможно кто-то тоже встретиться с этой проблемой.