Оцінка складністі алгоритмів факторизації. Факторизація великих цілих чисел (Практичне заняття № 2)

 Практичне заняття №2 (ТСО).

 Мета заняття:  Поглибити теоретичні знання і навчитися на практиці оцінювати складність алгоритмів факторизації.

Короткі відомості з теорії:

 Проблеми факторизації великих цілих чисел цікавлять учених і математиків близько ста років. З появою швидкодіючих комп'ютерів, були із зростаючою швидкістю виявлені нові методи факторизації, зріс інтерес до факторизації через взаємозв'язок між великими складеними числами і криптографією, але це не пояснює, чому пошук кращих методів факторизації був популярним більш ніж десять років тому серед багатьох математиків.

 Завдання факторизації цілого числа n полягає в знаходженні розкладення його в добуток простих співмножників. Тривіальний алгоритм часто називають алгоритмом „пробных ділень”, полягає у послідовному діленні числа n на всілякі прості числа, що не перевершують n. Найстаріший і найбільш проаналізований метод є просто "ділення і факторизація " або "тривіальне ділення" . Цей метод просто перевіряє кожен можливий головний співмножник один за іншим. Ніяка бібліотека алгоритмів факторизації не повинна бути без цього простого методу, тому що він виявить і розподілить групу невеликих головних множників, які часто ділять всі природно проведені складні числа.  Більшість факторизацій  використовують цю просту процедуру.

  При виконанні даного алгоритму виникають дві проблеми. З одного боку, для великих чисел n число операцій ділення, які необхідно виконати, може виявитися настільки великим, що його просто неможливо виконати. З іншого боку, необхідно наперед будувати список всіх простих чисел, що не перевершують n, що вже саме по собі є важким завданням. Іншої складності можна легко уникнути, якщо здійснювати ділення числа n не на прості, а на всі цілі числа k, що не перевершують n. Це позбавить від необхідності будувати початковий список простих чисел, причому складність такого алгоритму збільшиться не більше, ніж в О(log n) разів.

 Складність знаходження першого нетривіального дільника числа n для даного алгоритму оцінюється величиною

(p (n ) log ²n ) = О (n log n )

 для ділення на прості числа, і

 О (n log ²n )

 для ділення на ідучі підряд цілі числа.

 Помітимо, що при аналізі алгоритмів факторизації часто обмежуються розглядом тільки першого кроку - знаходження першого нетривіального дільника. Для знаходження повної факторизації числа n необхідно рекурсивно повторити виконання даного кроку не більше log ₂n разів.

Хоча застосування алгоритму „пробных ділень” в повному об'ємі для простих n практично неможливе, він все одно знаходить широке застосування в своєму „ скороченому” варіанті, коли пробні ділення здійснюються на всі прості числа, що не перевершують деякої константи С.

Граница С	Число простых p
256	54
1 000	168
10 000	1229
100 000	9592
1000 000	78498
10 000 000	664579
100 000 000	5761455

У такому вигляді алгоритм „пробных ділень” входить складовою частиною практично у всі алгоритми факторизації.

 Приступаючи до факторизації числа n, потрібно спочатку переконатися, що воно не просте. Це можна зробити за допомогою одного з відомих алгоритмів (тестів) на простоту. Їх трудомісткість, как правило, значно менше, ніж у алгоритмів факторизації.

 Найбільш популярним ймовірнісним алгоритмом факторизації є так званий „r - метод” , запропонований Дж. Поллардом в1975 р.

 Алгоритм 1

Крок1. Обираємо многочлен  .

Крок2. Випадково выбираємо  і, обчислюючи значення  перевіряємо тест кроку 3.

Крок3. Припускаємо  і для кожного  обчислюємо  Якщо , то нетривіальний дільник числа  був знайдений. Якщо  або , то переходимо до наступного значення  

Щоб зрозуміти сутність алгоритму розглянемо його на простому прикладі з невеликими значеннями чисел.

 Приклад. Хай потрібне факторізовать число   Нехай  , , .

Обчислюємо ,

,

,

,

,

,

,

,

,

,

.

Знаходимо

(

 - нетрівіальний дільник знайдений.

209:11 = 19 -  другий дільник знайдений.