Сайт о программировании, математике и моделировании
Записи с метками тест Рабина-Миллера
Исследование зависимости времени выполнения программы от количества цифр в числе
1 Декабрь
Исследуем зависимость времени выполнения программы от количества цифр в числе. Для этого сначала сгенерируем случайные числа длинной от двух до 100 цифр (по десять каждой длинны). Далее начнем проверять числа методом Рабина-Миллера и находить среднее значение выполнения теста для каждых чисел с одинаковым количеством цифр. В результате получим данные, которые затем занесем в программу MS Excel для дальнейшей обработки и построения графика зависимости времени выполнения реализованного теста Рабина-Миллера от количества цифр в числе. Читать дальше >
Исследование разработанной программы реализации вероятностного алгоритма Рабина Миллера
1 Декабрь
В этом разделе будут приведены примеры работы разработанной программы.
Пример №1 (рис. 1)
В текстовый файл вводится число 1999999888888777777.
А = 1999999888888777777
Программа начинается с того, что считывает это число из файла и выдает количество цифр в нем. В примере №1 сообщает, что считано 19 цифр. Читать дальше >
Разработка программы реализующей алгоритм Рабина-Миллера на С++
1 Декабрь
При выборе языка написания программы главными критериями являлись скорость выполнения и трудоемкость написания. С++ является одним из наиболее распространенных современных языков программирования. Язык С++ хорошо зарекомендовал себя эффективностью, лаконичностью записи алгоритмов, логической стойкостью программ. Ключевым понятием С++ является класс. Класс – это определяемый пользователем тип. Классы обеспечивают упрятывание данных, их инициализацию, неявное преобразование пользовательских типов, динамическое задание типов, контролируемое пользователем управление памятью и средства для перегрузки операций. В языке С++ концепции контроля типов и модульного построения программ реализованы более полно, чем в С. Кроме того, С++ содержит усовершенствования, прямо с классами не связанные: символические константы, функции-подстановки, стандартные значения параметров функций, перегрузка имен функций, операции управления свободной памятью и ссылочный тип. В С++ сохранены все возможности С эффективной работы с основными объектами, отражающими аппаратную «реальность» (разряды, байты, слова, адреса и т.д.). Это позволяет достаточно эффективно реализовывать пользовательские типы. Читать дальше >
Объединение тестов проверки на простоту
1 Декабрь
Первым возможным улучшением предложенного теста является использование для небольших целых n > 1 в качестве оснований теста Рабина-Миллера последовательных простых чисел больших или равных 2. К примеру, доказаны следующие утверждения : Читать дальше >
Методы проверки на простоту
1 Декабрь
Все алгоритмы проверки простоты делятся на две больших подгруппы: детерминированные и вероятностные проверки. Алгоритмы первой группы позволяют точно сказать, является число простым или составным. Алгоритмы второй группы позволяют это определить, но с некоторой вероятностью ошибки. Многократное их повторение для одного числа, но с разными параметрами, обычно позволяет сделать вероятность ошибки сколь угодно малой величиной. Читать дальше >
