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

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

(СПбГУТ)

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

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

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

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

Алгоритмы разложения на множители

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

ФИО:

Группа:

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

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

Содержание

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

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

Всякое целое число 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=1342127

x	x2	x2-n	y=sqrt(x2-n)
1158	1340964	-1163
1159	1343281	1154	33,97058
1160	1345600	3473	58,93216
1161	1347921	5794	76,11833
1162	1350244	8117	90,09439
1163	1352569	10442	102,1861
1164	1354896	12769	113

Т.е. x=1164, y=113. n=(1164+113)*(1164-113)=1277*1051

Задание

1. Выполнить попытку разложение на множители любого 4-х значного простого числа методом перебора. Указать признак остановки алгоритма. Привести примеры признаков делимости на 2,3,4,5,6

2. Выполнить аналогичные действия для любого числа, которое является произведением двух двухзначных (больше 50-ти) простых чисел

3. Разложить на множители 6142785497,550661749. Использовать алгоритм Ферма. (Второе число состоит из трех множителей, один из которых меньше 25)

Ход работы

1. 2503 2503: 2 – не делится, т.к. число нечетное. 2503: 3 – не делится (сумма цифр не делится на 3) 2503: 4 – не делится, т.к. последние две цифры числа не делятся на 4 2503: 5 – не делится (2503 не оканчивается на 0 или 5) 2503: 6 – не делится (не выполняются признаки делимости на 2 и 3) 2503: 7 – не делится (разность между числом десятков и удвоенным числом единиц не делится на 7) 2503: 8 – не делится, т.к. число нечетное. 2503: 9 – не делится (сумма цифр не делится на 9). 2503: 10 – не делится (число не оканчивается на 0). 2503: 11 – не делится (разность между суммой цифр, стоящих на четных местах, и суммой цифр, стоящих на нечетных местах, не делится на 11) 2503: 12 – не делится (сумма цифр не делится на 3, сумма последних двух цифр не нечетна) Дальнейший перебор не имеет смысла, так как мы провели достаточно операций, чтобы показать что число не имеет делителей от 1 до 10 и не является произведением простых чисел.

2. 89*97 = 8633

8633: 2 – не делится, т.к. число нечетное. 8633: 3 – не делится (сумма цифр не делится на 3) 8633: 4 – не делится, т.к. последние две цифры числа не делятся на 4 8633: 5 – не делится (2503 не оканчивается на 0 или 5) 8633: 6 – не делится (не выполняются признаки делимости на 2 и 3) 8633: 7 – не делится (разность между числом десятков и удвоенным числом единиц не делится на 7) 8633: 8 – не делится, т.к. число нечетное. 8633: 9 – не делится (сумма цифр не делится на 9). 8633: 10 – не делится (число не оканчивается на 0). 8633: 11 – не делится (разность между суммой цифр, стоящих на четных местах, и суммой цифр, стоящих на нечетных местах, не делится на 11) 8633: 12 – не делится (сумма цифр не делится на 3, сумма последних двух цифр не нечетна)

Число не будет являться простым, так как мы знаем, что 89 и 97 будут являться его множителями.

3. Через алгоритм Ферма 6142785497 и 550661749 6142785497

Т.е. х = 78381 y = 892 n = (78381+892) * (78381-892) = 79273*77489 550661749 Найдем для этого числа третий множитель, из которого состоит число, для этого методом подбора, определим множитель (т.к. по условию третий множитель до 25)

550661749: 2 – не делится, т.к. число нечетное. 550661749: 3 – не делится (сумма цифр не делится на 3) 550661749: 4 – не делится, т.к. последние две цифры числа не делятся на 4 550661749: 5 – не делится (550661749 не оканчивается на 0 или 5) 550661749: 6 – не делится (не выполняются признаки делимости на 2 и 3) 550661749: 7 – не делится (разность между числом десятков и удвоенным числом единиц не делится на 7) 550661749: 8 – не делится, т.к. число нечетное. 550661749: 9 – не делится (сумма цифр не делится на 9). 550661749: 10 – не делится (число не оканчивается на 0). 550661749: 11 – делится (разность между суммой цифр, стоящих на четных местах, и суммой цифр, стоящих на нечетных местах, делится на 11, 27-16 = 11)

Значит число состоит из каких-то двух множителей умноженных на 11. Разделим число на 11, для простоты вычислений и вставим данные в имеющуюся таблицу и дополним её.

Т.е x = 7128, y =865 n = (7128+865)(7128-865) = 7993*6263