Помогите найти ошибку в реализации теста простоты, Миллер-Рабин - Visual C++

Visual C++

Форум программистов и сисадминов Киберфорум

Войти

Регистрация
Восстановить пароль

@Splendid 0 / 0 / 1 Регистрация: 27.03.2008 Сообщений: 75

	Помогите найти ошибку в реализации теста простоты, Миллер-Рабин 11.06.2008, 09:48. Показов 2670. Ответов 0 Метки нет (Все метки) Помогите найти ошибку, пожалуйста! На нечетных числах просто зависает.... Добавлено через 1 час 12 минут а вот сам алгоритм: Вероятностный тест Миллера-Рабина Пусть n — нечетное и n − 1 = 2st, t — нечетное. Если число n является простым, то при всех a > 1 выполняется сравнение an−1 ≡ 1 (mod n) Поэтому, рассматривая элементы {at, a2t, …, a2s−1t} можно заметить, что либо среди них найдется равный −1 (mod n), либо at ≡ 1 (mod n). На этом замечании основан следующий вероятностный тест простоты: выбираем случайное число a из интервала {1, 2, …, n−1} и проверяем с помощью алгоритма Евклида условие (a, n) = 1; если оно не выполняется, то ответ «n — составное»; вычисляем at (mod n); если at ≡ ±1 (mod n), то переходим к п. 1; вычисляем a2t, …, a2s−1t до тех пор, пока не появится −1; если ни одно из этих чисел не равно −1, то ответ «n — составное»; если мы достигли −1, то ответ неизвестен (и тест можно повторить еще раз). Добавлено через 8 минут здесь и а - в степени и t в степени Добавлено через 20 часов 20 минут Спасибо, разобралась - код за ненадобностью убрала. 0

Programming

Эксперт

39485 / 9562 / 3019

Регистрация: 12.04.2006

Сообщений: 41,671

Блог

11.06.2008, 09:48

Ответы с готовыми решениями:

Помогите найти ошибку в реализации графика
Помогите с графиком. Одна из частей программы это демонстрация графика, я вроде как код написал номне выдает ошибку. Помогите мне....

Помогите найти ошибку в реализации типа "Дробь"
Есть задание: Реализовать класс: “Дробь”. В методе run() осуществить вычисление суммы числителя и знаменателя. Вопрос: 1. Правильно ли я...

Следует выбрать эффективный алгоритм (по времени) теста простоты числа
Следует выбрать эффективный алгоритм (по времени) теста простоты числа. На исследование вам дается два алгоритма: 1. Перебор делителей...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.

inter-admin

Эксперт

29715 / 6470 / 2152

Регистрация: 06.03.2009

Сообщений: 28,500

Блог

11.06.2008, 09:48

Помогаю со студенческими работами здесь

Найти ошибку в реализации Interface
Всем добрый день. С С# знаком недавно, пытаюсь реализовать интерфейс, но что-то не могу понять. как правильно сделать. Итак, есть...

Не могу найти ошибку в реализации алгоритма
Нужно перевести алгоритм в код. Вот мой код, но он не работает: double a = -10; double b = 10; ...

Найти ошибку в реализации метода Гаусса
Нужно решить матрицу методом гауза вот код: #include "iostream" #include "math.h" #include "stdlib.h" #include...

Найти ошибку в реализации файлового ввода-вывода
Ошибка заключается в том, что на этом промежутке while(fread(&a,sizeof(int),1,f)) { if(a!=0)fwrite(&a,sizeof(int),1,g); ...

Помогите найти ошибки в реализации класса «Очередь»
Класс «Очередь». Методы: добавление элемента, удаление элемента, удаление из очереди всех элементов, равных заданному значению. начал...

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

Или воспользуйтесь поиском по форуму:

Новые блоги и статьи Все статьи Все блоги /
Автоматическое создание документа при проведении другого документа Maks 29.03.2026 Реализация из решения ниже выполнена на нетиповых документах, разработанных в конфигурации КА2. Есть нетиповой документ "ЗаявкаНаРемонтСпецтехники" и нетиповой документ "ПланированиеСпецтехники". В. . .	Настройка движения справочника по регистру сведений Maks 29.03.2026 Решение ниже реализовано на примере нетипового справочника "ТарифыМобильнойСвязи" разработанного в конфигурации КА2, с целью учета корпоративной мобильной связи в коммерческом предприятии. . . .	Автозаполнение реквизита при выборе элемента справочника Maks 27.03.2026 Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. При выборе "Спецтехники" (Тип Справочник. Спецтехника), заполняется. . .	Сумматор с применением элементов трёх состояний. Hrethgir 26.03.2026 Тут. https:/ / fips. ru/ EGD/ ab3c85c8-836d-4866-871b-c2f0c5d77fbc Первый документ красиво выглядит, но без схемы. Это конечно не даёт никаких плюсов автору, но тем не менее. . . всё может быть. . .
Автозаполнение реквизитов при создании документа Maks 26.03.2026 Программный код из решения ниже размещается в модуле объекта документа, в процедуре "ПриСозданииНаСервере". Алгоритм проверки заполнения реализован для исключения перезаписи значения реквизита,. . .	Команды формы и диалоговое окно Maks 26.03.2026 1. Команда формы "ЗаполнитьЗапчасти". Программный код из решения ниже на примере нетипового документа "ЗаявкаНаРемонтСпецтехники" разработанного в конфигурации КА2. В качестве источника данных. . .	Кому нужен AOT? DevAlt 26.03.2026 Решил сделать простой ланчер Написал заготовку: dotnet new console --aot -o UrlHandler var items = args. Split(":"); var tag = items; var id = items; var executable = args;. . .	Отправка уведомления на почту при создании или изменении элементов справочника Maks 24.03.2026 Программная отправка письма электронной почты на примере типового справочника "Склады" в конфигурации БП3. Перед реализацией необходимо выполнить настройку системной учетной записи электронной. . .

Наверх