Лабораторная/Практика. Проверка заданного числа (простое или составное)

Метод 1. Проверка числа методом перебора возможных делителей. Возможна некоторая оптимизация с проверкой числа с помощью признаков делимости.

Теория из предыдущей работы, признаки делимости смотрим самостоятельно.

Метод 2. Тест Ферма

Тест основан на малой теореме Ферма.

Теорема. Если n-простое и НОД(a, n) = 1, то a^n-1 = 1 mod n.

Вывод – если n составное, то соотношения из малой теоремы Ферма не всегда будут выполняться. Можно показать, что в среднем для составных чисел соотношения из малой теоремы Ферма выполняются с вероятностью ½.

Алгоритм тестирования числа n.

Выбираем количество тестов – k (это определить вероятность ошибочно принять составное число за простое). Выбираем k случайных чисел a: a₁, a₂, …, a_k < n (обычно выбирают малые простые числа).

Для каждого a_i вычисляем НОД(a_i ,n), если «n» простое, то всегда должна быть 1. Если любое из НОД(a_i ,n)≠1, то тест заканчивается с выводом, что «n» составное.

Если проверки пройдены, то для каждого a_i проверяем: a_i^(n-1) = 1 mod n. Если любое из a_i^(n-1) ≠ 1 mod n, то тест заканчивается с выводом, что «n» составное.

Если все проверки пройдены, то принимаем решение, что n – простое, с итоговой вероятностью, что мы приняли составное число за простое равное: (½)^k.

Некоторые составные числа всегда удовлетворяют условиям теоремы Ферма, так называемые числа Кармайкла. Выполняя тест Ферма узнать что число Кармайкла составное можно на проверке НОД (a_i, n) ≠ 1, если «удачно» выбран a_i.

Задание

Выбрать два простых и два составных нечетных числа (не кратных 3, 5 и 7) и еще одно составное число Кармайкла. Выбирать числа для выполнения задания по следующей формуле: 1. Вычисляем: X=((№ студента в группе)+110)*23. Далее произвольно в диапазоне X±20 выбрать нужные числа (если в бригаде один студент, то проверяем 4-ые числа, если два, то 8, если три то 12). Число Кармайкла выбирать по следующему алгоритму: студент в группе с номером 1. Берёт число 1105 студент в группе с номером 2. Берёт число 1729 студент в группе с номером 3. Берёт число 2465 студент в группе с номером 4. Берёт число 2821 студент в группе с номером 5. Берёт число 6601 студент в группе с номером 6. Берёт число 8911 для студентов с большими номерами выбирать число Кармайкла циклически, 7-й берёт опять число 1105 и т.п. Сколько человек в бригаде, столько разных чисел Кармайкла должно быть проверено.

1. Проверить каждое из этих чисел методом перебора возможных делителей. По желанию возможно использовать предварительную проверку по признакам делимости на 3, 5, 7 и 11. Проверять выбранные числа по признакам делимости можно «вручную» или программно.

2. Проверить каждое из чисел тестом Ферма. Если задание выполняется в EXCEL, то выбирать k таком образом, чтоб вероятность принять составное за простое была не более 0,125. При полностью программной реализации алгоритма выбирать k таким образом, чтоб вероятность принять составное за простое была не более 10^-3.

Отчет.

Содержание отчёта:

1. Стандартный титульный лист.

2. Теория по исследуемому вопросу, если есть в задании (достаточно использовать материалы задания самой лабораторной работы).

3. Формулировка задания на вычисления.

4. Шаги выполнения вычисления или доказательства.

5. Проверка правильности найденных решений, если применимо.

6. Файл с отчётом должен иметь название по следующему шаблону: Лаб_(номер лабы(две цифры))_(номер группы)_Фамилия1_ИО_Фамилия2_ИО_Фамилия3_ИО. Пример: Лаб_01_ИКБ-72_Иванов_ДИ_Петров_ЕН_Сидоров_ЯЭ.