МИНИСТЕРСТВО ЦИФРОВОГО РАЗВИТИЯ, СВЯЗИ И МАССОВЫХ КОММУНИКАЦИЙ РОССИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ОБРАЗОВАНИЯ «САНКТ-ПЕТЕРБУРГСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ТЕЛЕКОММУНИКАЦИЙ ИМ. ПРОФ. М.А. БОНЧ-БРУЕВИЧА»

(СПбГУТ)

Факультет Инфокоммуникационных сетей и систем

Кафедра Защищенных систем связи

Дисциплина Математические основы защиты информации

ОТЧЕТ ПО ЛАБОРАТОРНОЙ РАБОТЕ №8

Тест Ферма

10.03.01 Информационная безопасность

ФИО:

Группа:

Преподаватель: Кушнир Д.В.

Санкт-Петербург

Содержание

Тест Ферма 3

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

Теоретическая часть по исследуемому вопросу

Основная теорема арифметики.

Всякое целое число n ≥ = единственным образом может быть представлено в виде:

, где p₁,p₂,…,p_k – простые, (1<p₁<p₂<…<p_k), e₁,e₂,…,e_k-натуральные числа.

Замечание, если число делится нацело только на 1 и на себя, то такое число простое.

Алгоритм разложения на множители методом «перебора».

Последовательно выполняем деление исследуемого числа n на числа: 2,3,4,5,6,7,8… - самостоятельно определить до какого числа достаточно производить такое деление. При выполнении деления можно учитывать признаки делимости на различные числа (2,3,4,5,…) для сокращения числа операций.

Алгоритм разложения на множители Ферма. Этот алгоритм пытается представить n=x²-y², тогда n раскладывается на (x-y)*(x+y). Достаточно эффективен при близких сомножителях. Шаг1. Принять x=[sqrt(n)], если n=x² , то x делитель – окончание алгоритма, иначе x=x+1 ([ … ]- обозначает взять целое). Шаг2. Если x=(n+1)/2 – n простое – окончание алгоритма, иначе вычисляем y=sqrt(x²-n). Шаг3. Если y целое, т.е. y²=x²-n,то решение найдено (n=(x+y)*(x-y)), иначе x=x+1 и переходим к шагу 2.

Тест Ферма

Тест основан на мой теореме Ферма. Если n-простое и НОД(а, 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. Проверить каждое из этих чисел методом перебора возможных делителей. По желанию возможно использовать предварительную проверку по признакам делимости на 3, 5, 7 и 11. Проверять выбранные числа по признакам делимости можно «вручную» или программно.

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

Ход работы

X = (22+110)*23=3036

Простые +- 20 от Х: 3019, 3049

Составные +- 20 от Х: 3029, 3043

Число Кармайкла – 2821

Проверяем каждое из чисел методом перебора. Для этого воспользуемся Excel

Проверка каждого из чисел тестом Ферма. Проверим для каждого числа НОД(a,n) где n столбец слева.

Сразу получаем, что числа 3029, 3043, 2721 составные, и дальнейший тест ферма для них нет смысла проводить.

3019 (2^3018) mod 3019 = 1 (3^3018) mod 3019 = 1 (5^3018) mod 3019 = 1 (7^3018) mod 3019 = 1 (11^3018) mod 3019 = 1 (13^3018) mod 3019 = 1

Число 3019 – простое, с итоговой вероятностью (0.5)^6

3049 (2^3048) mod 3049 = 1 (3^3048) mod 3049 = 1 (5^3048) mod 3049 = 1 (7^3048) mod 3049 = 1 (11^3048) mod 3049 = 1 (13^3048) mod 3049 = 1

Число 3049 – простое, с итоговой вероятностью (0.5)^6