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

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

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

Означення. Розкладом натурального числа 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