Лабораторная/практика №7. Алгоритмы разложения на множители.

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

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

,

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

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

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

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

2. Алгоритм разложения на множители Ферма. Этот алгоритм пытается представить 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. Разложить на множители (факторизовать), два числа из таблицы ниже, вариант выбирать по номеру студента в группе. Использовать алгоритм Ферма. Обратите внимание на примечание.

Номер	Факторизовать *
1	5810653073	319066187
2	5824662901	208613461
3	5842265399	339726871
4	5858168527	224263319
5	5872408933	363499961
6	5887482301	236246759
7	5905333157	383745989
8	5920578299	252427511
9	5942282681	481531609
10	5959258237	420194951
11	5978426309	511196179
12	5994802861	282205427
13	6014624081	290886421
14	6034362907	472103467
15	6049910107	571104131
16	6070137431	491937083
17	6087943019	323735251
18	6107106413	616870501
19	6123988457	535279349
20	6142785497	550661749

* Примечание. Одно из чисел для факторизации является произведением двух простых чисел, а другое трех, причем третий сомножитель меньше 25 (т.е. напрямую алгоритм Ферма будет мало эффективен, сперва надо найти этот «малый» множитель).

Отчет.

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

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

2. Теория по исследуемому вопросу.

3. Задание на вычисления.

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

При выполнении заданий с помощью программирования в какой-либо среде – приводить программный код или указывать используемые формулы в соответствующей среде (например, формулы в ячейках Excel).

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