Означення. Розкладом натурального числа n на прості множники (факторизацією числа) називається представлення його у вигляді n = , де pi – взаємно прості числа, ki ³ 1 .
Задача перевірки числа на простоту є простішою за задачу факторизації. Тому перед розкладанням числа на прості множники слід перевірити число на простоту.
Означення. Розбиттям числа називається задача представлення натурального числа n у вигляді n = a * b , де a , b – натуральні числа, більші за 1 (не обов’язково прості).
Метод Ферма
Нехай n – складене число, яке не є степенем простого числа. Метод Ферма намагається знати такі натуральні x та y , що n = x 2 – y 2 . Після чого дільниками числа n будуть a = x – y та b = x + y : n = a * b = (x – y )(x + y ).
Якщо припустити що n = a * b , то в якості x та y (таких що n = x 2 – y 2 ) можна обрати
,
Возможно вы искали - Реферат: Eduational Research Foundation Essay Research Paper Educational
Приклад. Виберемо n = 143 = 11 * 13.
Тоді x = (13 + 11) / 2 = 12, y = (13 – 11) / 2 = 1.
Перевірка: x 2 – y 2 = 122 – 11 = 143 = n .
Теорема. Якщо n = x 2 – y 2 , то < x < (n + 1) / 2.
Доведення. З рівності n = x 2 – y 2 випливає, що n < x 2 , тобто < x .
Оскільки a = n / b , то . Максимальне значення x досягається при мінімальному b , тобто при b = 1. Звідси x = < .
Похожий материал - Реферат: Жизнь и реформы Екатерины II
Отже для пошуку представлення n = x 2 – y 2 слід перебрати всі можливі значення x із проміжку [, (n + 1) / 2], перевіряючи при цьому чи є вираз x 2 - n повним квадратом.
Приклад. Розкласти на множники n = 391 методом Ферма. = 19.
202 – 391 = 9 = 32 . Маємо рівність: 391 = 202 – 32 .
Звідси 391 = (20 – 3)(20 + 3) = 17 * 23.
Алгоритм Полард - ро факторизації числа
У 1974 році Джон Полард запропонував алгоритм знаходження нетривіального дільника натурального числа n . Пр цьому алгоритм використовує лише операції додавання, множення та віднімання модулярної арифметики.
Очень интересно - Реферат: Идейно-художественное содержание романа Апулея Метаморфозы или Золотой осёл
Ідея алгоритма Полард – ро полягає в ітеративному обчисленні деякої наперед заданої поліноміальної функції f з цілими коефіцієнтами. Побудуємо послідовність xi наступним чином: x 0 оберемо довільним із Zn , а xi +1 = f(xi ) mod n , i ³ 0. Оскільки xi можуть приймати лише скінченний набір значень (цілі числа від 0 до n ), то існують такі цілі n 1 та n 2 (n 1 < n 2 ), що = . Враховуючи поліноміальність f , для кожного натурального k маємо: =, тобто починаючи з індекса i = n 1 послідовність {xi mod n } буде періодичною.
Приклад. Нехай n = 21, x 0 = 1, xi +1 = + 3 mod 21.
Тоді послідовність xi має вигляд: 1, 4, 19, 7, 10, 19, 7, 10, ... .
Таким чином x 3 = x 6 , період послідовності дорівнює 3.
Послідовність xi можна відобразити у вигляді кола з хвостом: коло відповідає періодичній частині, а хвіст – доперіодичній. Картинка нагадує грецьку літеру r, тому метод який застосовується в алгоритмі називається r – евристикою. Послідовність із попереднього прикладу можна зобразити так:
Вам будет интересно - Реферат: Правовое воспитание понятие, формы, методы
Ідея алгоритму полягає в обчисленні для кожного i > 0 значення d = НСД(x 2i – xi , n ). Якщо на деякому кроці d > 1, то це і є нетривіальний дільник числа n .
Побудуємо послідовність елементів xi наступним чином:
x 0 = 2, xi +1 = f(xi ) = ( + 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 2 + 1) mod n ; b ¬ (b 2 + 1) mod n ; b ¬ (b 2 + 1) mod n ;
2.2. Обчислити d ¬ НСД(a - b , n );
2.3. if 1 < d < n return (d ); // знайдено нетривіальний дільник