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

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

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

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

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

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

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

Вот моя реализация на C++:
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#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++):

Отделение интерфейса от реализации класса: компиляция кода реализации - C++
Доброго времени суток, У меня возникла проблема с отделением интерфейса от реализации класса. Допустим, у меня есть три файла: 1....

Теорема ферма для n>2 - C++
Здравствуйте, возникла проблема при выполнении задания: Создайте приложение, которое покажет, что для выражения {a}^{n}+{b}^{n}={c}^{n}...

Работа с библиотекой miracl: тест Ферма на простоту - C++
начал разбираться с библиотекой miracl, дали задание написать реализацию теста Ферма на простоту, но возникают ошибки: error LNK2019:...

Затруднения в программе - C++
Здравствуйте. Когда писала программу столкнулась с вот таким вопросом от преподавателя: float time_max(int n, float *Uvx, float *t) ...

затруднения с ShowMessage - C++
Есть два поля ввода, в каждое из них должно вводится не пустое значение, иначе должна быть проверка ввода значений. Написал бодро первую...

Затруднения с циклом do-while - C++
Здравствуйте! Дано задание: Используя оператор цикла do-While, составить программу, которая вычисляет сумму уравнения , при этом х...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
20.04.2008, 13:48
Привет! Вот еще темы с ответами:

Затруднения по динамическим переменным - C++
Всем привет! Когда создаю динамическую переменную, то чтобы вывести ее значение, то пишу *переменная. Если выделяю массив, то обращаюсь...

switch есть небольшие затруднения - C++
Есть программа #include &lt;windows.h&gt; #include &lt;iostream.h&gt; int main() { char *ch; cout&lt;&lt;&quot;Enter ab,asd,voro or...

Затруднения с Wise Installer"ом - C++
Постоянно возникает одна и таже ошибка прои компиляции просто при пробном запуске или сохранении в Wise for Windows Installer 3.0,...

Затруднения с ответом по теоретической части - C++
Здравствуйте! К вам вопрос по теоретической части, на который есть предпосылки в интернете, но ответа сформулированного нет. Цикл while в ...


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

Или воспользуйтесь поиском по форуму:
Ответ Создать тему
Опции темы

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