bool testMillerRabin(unsigned long n)
{
    if (n == 2 || n == 3)
        return true;
    if (n < 2 || n % 2 == 0)
        return false;
 
    unsigned long t = n - 1;
    int s = 0;
    while (t % 2 == 0)
    {
        t /= 2;
        s += 1;
    }
 
    for (int i = 0; i < 10; i++)
    {
        unsigned long  a = (rand() % (n - 2)) + 2;
        unsigned long  x = modexp(a, t, n);
        if (x == 1 || x == n - 1)
            continue;
        for (int j = 1; j < s; j++)
        {
            x = modexp(x, 2, n);
            if (x == 1)
                return false;
            if (x == n - 1)
                break;
        }
        if (x != n - 1)
            return false;
    }
    return true;
}

Заказать работу у эксперта

IT_Exp

Эксперт

34794 / 4073 / 2104

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

Сообщений: 32,602

Блог

29.05.2020, 14:15

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

тест миллера-рабина, pascal -> c++
собсно, кто знает дельфи и с++, обьясните где я не прав пожалуйста=) дельфи: {IsPrime.Pas ver....

Реализация теста Рабина-Миллера для чисел порядка 2^512
Необходимо реализовать тест для таких вот БОЛЬШИХ чисел. Но с арифметикой больших чисел на C\C++ не...

Тест Миллера-Рабина
Добрый день всем. Алгоритм для теста взял с википедии. Вот он: Ввод: m > 2, нечётное натуральное...

Тест простоты Миллера-Рабина
Помогите написать программу по этому алгоритму Входные данные: целое нечётное число n ≥3,...

	29.05.2020, 14:15

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

BasicMan

Эксперт

29316 / 5623 / 2384

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

Сообщений: 30,364

Блог

29.05.2020, 14:15

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

Тест Миллера-Рабина. Как получить число t из формулы
Что то я никак не могу понять как получить число t из формулы m-1={2}^{s}*t. Делаю по алгоритму...

алгоритм Миллера-Рабина проверки простоты многоразрядных чисел.
надо составить алгоритм Миллера-Рабина проверки простоты многоразрядных чисел. Я составил, ...

Индексы Миллера Кристаллография
Боже поясните за индексы Миллера.Человеческим языком расскажите пожалуйста что они делают и как...

Генератор псевдослучайных чисел Парка-Миллера
Здравствуйте! Как мне решить данную задачу? Минимальный генератор Парка- Миллера Простейшая...

Алгоритм Миллера и Мюллера (Mueller-Muller)
Здравствуйте. В описании алгоритма (например, здесь:...

методы борьбы с эффектом Миллера на mosfet
Привет. Столкнулся с проблемой измерение затухание ультразвукового сигнала в среде. При разных...

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

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

Новые блоги и статьи
Элементы алгоритмизации hw_wired 28.01.2025 Основы алгоритмизации В современном мире алгоритмы играют фундаментальную роль в развитии информационных технологий и программирования. Понимание основ алгоритмизации является ключевым элементом в. . .	Человек и информация hw_wired 28.01.2025 Введение: роль информации в познании мира В современном мире информация играет фундаментальную роль в процессе познания окружающей действительности. Она представляет собой совокупность сведений об. . .	Компьютер и информация hw_wired 28.01.2025 Эволюция вычислительных машин История развития вычислительной техники начинается задолго до появления первых электронных устройств. Человечество всегда стремилось упростить процесс вычислений и. . .	Информационные технологии hw_wired 28.01.2025 Введение в современные технологии работы с информацией В современном мире информационные технологии стали неотъемлемой частью практически всех сфер человеческой деятельности. Они существенно. . .	Информация вокруг нас hw_wired 28.01.2025 Основные понятия информации В современном мире понятие информации является фундаментальным и охватывает практически все сферы человеческой деятельности. Информация представляет собой совокупность. . .	Компьютер для начинающих hw_wired 28.01.2025 Введение в мир компьютерных технологий В современном мире информация стала одним из важнейших ресурсов человечества, определяющим развитие общества и технологий. Наша жизнь неразрывно связана с. . .
[golang] 189. Rotate Array alhaos 28.01.2025 Повороты рукоятки, целочисленный слайс нужно сдвинуть на целое положительное число. Мне очень нравится решение на GO / / https:/ / leetcode. com/ studyplan/ top-interview-150/ package topInterview . . .	КуМир: решение задач на матрицы bytestream 28.01.2025 КуМир представляет собой среду для обучения программированию, которая включает в себя мощные инструменты для работы с матрицами. Матрица в программировании - это двумерный массив, состоящий из. . .	КуМир: решение задач на строки bytestream 28.01.2025 В системе программирования КуМир работа со строковыми данными является одним из важнейших аспектов создания программ. Строки представляют собой последовательности символов, заключенные в кавычки,. . .	КуМир: решение геометрических задач bytestream 28.01.2025 Программирование геометрических задач в среде КуМир становится всё более актуальным в обучении школьников и студентов. КуМир — это разработанная в России обучающая программная среда, предназначенная. . .	КуМир, исполнитель Водолей: Задачи и решения bytestream 28.01.2025 КуМир — это образовательная среда для обучения программированию. Она предлагает пользователям разнообразные инструменты для разработки и отладки программ, что особенно ценно для студентов и. . .	КуМир, исполнитель Чертежник: Решение задач bytestream 28.01.2025 КуМир (Комплект Учебных МИРов) представляет собой образовательную среду для обучения основам программирования и алгоритмизации. Исполнитель Чертежник работает на координатной плоскости, где может. . .

Наверх