Реферат: Розклад числа на прості множники

Реферат на тему:

Розклад числа на прості множники

Означення. Розкладом натурального числа n на прості множники (факторизацією числа) називається представлення його у вигляді n = , де p_i – взаємно прості числа, k_i ³ 1 .

Задача перевірки числа на простоту є простішою за задачу факторизації. Тому перед розкладанням числа на прості множники слід перевірити число на простоту.

Означення. Розбиттям числа називається задача представлення натурального числа n у вигляді n = a * b , де a , b – натуральні числа, більші за 1 (не обов’язково прості).

Метод Ферма

Нехай n – складене число, яке не є степенем простого числа. Метод Ферма намагається знати такі натуральні x та y , що n = x ² – y ² . Після чого дільниками числа n будуть a = x – y та b = x + y : n = a * b = (x – y )(x + y ).

Якщо припустити що n = a * b , то в якості x та y (таких що n = x ² – y ² ) можна обрати

,

Приклад. Виберемо n = 143 = 11 * 13.

Тоді x = (13 + 11) / 2 = 12, y = (13 – 11) / 2 = 1.

Перевірка: x ² – y ² = 12² – 1¹ = 143 = n .

Теорема. Якщо n = x ² – y ² , то < x < (n + 1) / 2.

Доведення. З рівності n = x ² – y ² випливає, що n < x ² , тобто < x .

Оскільки a = n / b , то . Максимальне значення x досягається при мінімальному b , тобто при b = 1. Звідси x = < .

Отже для пошуку представлення n = x ² – y ² слід перебрати всі можливі значення x із проміжку [, (n + 1) / 2], перевіряючи при цьому чи є вираз x ² - n повним квадратом.

Приклад. Розкласти на множники n = 391 методом Ферма. = 19.

20² – 391 = 9 = 3² . Маємо рівність: 391 = 20² – 3² .

Звідси 391 = (20 – 3)(20 + 3) = 17 * 23.

Алгоритм Полард - ро факторизації числа

У 1974 році Джон Полард запропонував алгоритм знаходження нетривіального дільника натурального числа n . Пр цьому алгоритм використовує лише операції додавання, множення та віднімання модулярної арифметики.

Ідея алгоритма Полард – ро полягає в ітеративному обчисленні деякої наперед заданої поліноміальної функції f з цілими коефіцієнтами. Побудуємо послідовність x_i наступним чином: x ₀ оберемо довільним із Z_n , а x_{i +1} = f(x_i ) mod n , i ³ 0. Оскільки x_i можуть приймати лише скінченний набір значень (цілі числа від 0 до n ), то існують такі цілі n ₁ та n ₂ (n ₁ < n ₂ ), що = . Враховуючи поліноміальність f , для кожного натурального k маємо: =, тобто починаючи з індекса i = n ₁ послідовність {x_i mod n } буде періодичною.

Приклад. Нехай n = 21, x ₀ = 1, x_{i +1} = + 3 mod 21.

Тоді послідовність x_i має вигляд: 1, 4, 19, 7, 10, 19, 7, 10, ... .

Таким чином x ₃ = x ₆ , період послідовності дорівнює 3.

Послідовність x_i можна відобразити у вигляді кола з хвостом: коло відповідає періодичній частині, а хвіст – доперіодичній. Картинка нагадує грецьку літеру r, тому метод який застосовується в алгоритмі називається r – евристикою. Послідовність із попереднього прикладу можна зобразити так:

Ідея алгоритму полягає в обчисленні для кожного i > 0 значення d = НСД(x _2i – x_i , n ). Якщо на деякому кроці d > 1, то це і є нетривіальний дільник числа n .

Побудуємо послідовність елементів x_i наступним чином:

x ₀ = 2, x_{i +1} = f(x_i ) = ( + 1) mod n , i > 0

Алгоритм

Вхід: натуральне число n , параметр t ³ 1.

Вихід: нетривіальний дільник d числа n .

1. a = 2, b = 2;

2. for i ¬ 1 to t do

2.1. Обчислити a ¬ (a ² + 1) mod n ; b ¬ (b ² + 1) mod n ; b ¬ (b ² + 1) mod n ;

2.2. Обчислити d ¬ НСД(a - b , n );

2.3. if 1 < d < n return (d ); // знайдено нетривіальний дільник

3. return (False); // дільника не знайдено

Вважаємо, що функція f(x ) = (x ² + 1) mod n генерує випадкові числа. Тоді для знаходження дільника числа n необхідно виконати не більш ніж O() операцій модулярного множення.

Якщо алгоритм Поларда – ро не знаходить дільника за t ітерацій, то замість функції f(x ) = (x ² + 1) mod n можна використовувати f(x ) = (x ² + c) mod n , для деякого цілого c, c ¹ 0, -2.

Приклад. Нехай n = 19939.

Послідовність x_i : 2, 5, 26, 677, 19672, 11473, 12391, 6582, 15217, 5483, 15217, 5483, 15217, ... .

Знайдено розклад 19939 = 157 * 127.

Нехай n = 143. Послідовність x_i : 2, 5, 26, 105, 15, ... .

Знайдено розклад 143 = 11 * 13.

Ймовірносний квадратичний алгоритм факторизації числа

Твердження. Нехай x та y – цілі числа, x ² º y ² (mod n ) та x ¹ ±y (mod n ). Тоді x ² – y ² ділиться на n , при чому жоден із виразів x + y та x – y не ділиться на n . Число d = НСД(x ² – y ² , n ) є нетривіальним дільником n .

Теорема. Якщо n – непарне складене число, яке не є степенем простого числа, то завжди існують такі x та y , що x ² º y ² (mod n ), при чому x ¹ ± y (mod n ).

Доведення. Нехай n = n ₁ * n ₂ – добуток взаємно простих чисел. Оберемо таке y , що НСД(y , n ) = 1. Далі розв’яжемо систему рівнянь:

Розв’язком системи будуть такі x та y за модулем n = НСК(n ₁ , n ₂ ), що x ² º y ² (mod n ). Якщо при цьому припустити, що x º – y (mod n ), то з другого рівняння системи маємо: y º – y (mod n ₂ ), або 2 * y = 0 (mod n ₂ ). Оскільки було обрано НСД(y , n ₂ ) = 1, то з останньої рівності випливає що n ₂ ділиться на 2, тобто є парним. Це суперечить умові теореми про непарність n .

Приклад. Виберемо n ₁ = 11, n ₂ = 13 – взаємно прості числа. Тоді n = 11 * 13 = 143. Покладемо y = 5, НСД(5, 143) = 1. Складемо систему порівнянь:

або

Розв’язком системи буде x º 60 (mod 143).

Має місце рівність 60² º 5² (mod 143) , при чому 60 ¹ ±5 (mod 143).

Тоді дільником числа n буде d = НСД(60 – 5, 143) = 11.

Формально ймовірносний квадратичний алгоритм факторизації будується на наступній ідеї:

Нехай F = {p ₀ , p ₁ , p ₂ , …, p_t } – множникова основа, p_i – різні прості числа, при чому дозволяється обрати p ₀ = -1. Побудуємо множину порівнянь

º z_i ,

таку що значення z_i є повіністю факторизованими у множині F :

,

та добуток деякої підмножини значень z_i є повним квадратом:

z = = y ² , y Î Z, f_i Î {0, 1}

Якщо множина порівнянь із вказаними властивостями побудована, то поклавши x = і перевіривши виконання нерівності x ¹ ± y (mod n ), отри маємо x ² º y ² (mod n ). Число d = НСД(x ² – y ² , n ) є нетривіальним дільником n .

Приклад. Знайти дільник числа n = 143.

Обираємо випадково число x Î [2, 142], обчислюємо x² (mod 143) та розкладаємо результат на множники:

1. z₁ = 19² (mod 143) = 75 = 3 * 5² .

2. z₂ = 77² (mod 143) = 66 = 2 * 3 * 11.

3. z₃ = 29² (mod 143) = 126 = 2 * 3² * 7.

4. z₄ = 54² (mod 143) = 56 = 2³ * 7.

Можна помітити, що добуток z₃ та z₄ є повним квадратом:

z = z₃ * z₄ = 2⁴ * 3² * 7² = (2² * 3 * 7)² = 84²

Маємо рівність:

z₃ * z₄ = 29² * 54² º 84² (mod 143)

або враховуючи що 29 * 54 (mod 143) º 136, маємо:

136² = 84² (mod 143), при чому 136 ¹ ±84 (mod 143)

Дільником числа n = 143 буде d = НСД(136 – 84, 143) = НСД(52, 143) = 13.

Квадратичний алгоритм факторизації

Серед усіх існуючих алгоритмів факторизації найшвидшим є квадратичний. Він ефективно застосовується для чисел, кількість цифр яких менша за 100 та які не мають малих простих дільників. Еврістичний аналіз, проведений Померансом [1] у 1981 році показав, що число N може бути розкладено на множники за час .

Нехай n – число, яке факторизується, m = . Розглянемо многочлен

q(x ) = (x + m )² - n

Квадратичний алгоритм обирає a_i = x + m (x = 0, ±1, ±2, …), обчислює значення b_i = (x + m )² – n та перевіряє, чи факторизується b_i у множниковій основі F = {p ₀ , p ₁ , p ₂ , …, p_t }.

Помітимо, що = (x + m )² – n º (x + m )² (mod n ) º b_i (mod n ).

Алгоритм

Вхід: натуральне число n , яке не є степенм простого числа.

Вихід: нетривіальний дільник d числа n .

1. Обрати множникову основу F = {p ₀ , p ₁ , p ₂ , …, p_t }, де p ₀ = -1, p_i – i - те просте число p , для якого n є квадратичним лишком за модулем p.

2. Обчислити m = [].

3. Знаходження t + 1 пари (a_i , b_i ).

Значення x перебираються у послідовності 0, ±1, ±2, … .

Покласти i ¬ 1. Поки i £ t + 1 робити:

3.1. Обчислити b = q(x ) = (x + m )² – n та перевірити, чи розкладається b у множниковій основі F . Якщо ні, обрати наступне x та повторити цей крок.

3.2. Нехай b = . Покласти a_i = x + m , b_i = b , v_i = (v_{i 1} , v_{i 2} , …, v_it ), де v_ij = e_ij mod 2, 1 £ j £ t .

3.3. i ¬ i + 1.

4. Знайти підмножину T Í {1, 2, …, t + 1} таку що = 0.

5. Обчислити x = mod n .

6. Для кожного j, 1 £ j £ t , обчислити l_j = () / 2.

7. Обчислити y = mod n .

8. Якщо x º ±y (mod n ), знайти іншу підмножину T Í {1, 2, …, t + 1} таку що = 0 та перейти до кроку 5.

9. Обчислити дільник d = НСД(x – y , n ).

Приклад. Розкласти на множники n = 24961.

1. Побудуємо множникову основу: F = {-1, 2, 3, 5, 13, 23}

2. m = [] = 157.

3. Побудуємо наступну таблицю:

4. Виберемо T = {1, 2, 5}, оскільки v ₁ + v ₂ + v ₅ = 0.

5. Обчислимо x = (a ₁ a ₂ a ₅ ) (mod n ) = 936 = 2⁶ * 3⁴ * 13² .

6. l ₁ = 1, l ₂ = 3, l ₃ = 2, l ₄ = 0, l ₅ = 1, l ₆ = 0.

7. y = -2³ * 3² * 13 (mod n ) = 24025.

8. Оскільки 936 º –24025 (mod n ), необхідно шукати іншу множину T.

9. Виберемо T = {3, 6, 7}, оскільки v ₃ + v ₆ + v ₇ = 0.

10. Обчислимо x = (a ₃ a ₆ a ₇ ) mod n = 23405 = 2¹⁰ * 3⁴ * 5⁶ .

11. l ₁ = 1, l ₂ = 5, l ₃ = 2, l ₄ = 3, l ₅ = 0, l ₆ = 0.

12. y = -2⁵ * 3² * 5³ (mod n ) = 13922.

13. 23405 ¹ ±13922 (mod n).

d = НСД(x – y , n ) = НСД(9483, 24961) = 109 – дільник.

Відповідь: 109 – дільник 24961.