Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 22, средняя оценка - 4.82
Phoenix777
Сообщений: n/a
#1

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

20.04.2008, 13:48. Просмотров 2732. Ответов 0
Метки нет (Все метки)

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

Код
for (i=0; i<k; i++)
{
выбрать a из [2,...,n-1];
b=a^(n-1)modn;
{напечатать (составное, 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). Не могу найти причину, пожалуйста подскажите, если знаете, спасибо.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
20.04.2008, 13:48     Затруднения в реализации теста Ферма
Посмотрите здесь:
Отделение интерфейса от реализации класса: компиляция кода реализации C++
Теорема ферма для n>2 C++
C++ Работа с библиотекой miracl: тест Ферма на простоту
C++ затруднения с ShowMessage
C++ Затруднения в программе
C++ Затруднения с циклом do-while
Затруднения по динамическим переменным C++
Затруднения с ответом по теоретической части C++
Затруднения с Wise Installer"ом C++
switch есть небольшие затруднения C++
Затруднения с выводом системного времени в программе C++
C++ Затруднения с итерацией и подсчетом количеста функций

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru