Головна Головна -> Реферати українською -> Математика -> Розклад числа на прості множники

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

Назва:
Розклад числа на прості множники
Тип:
Реферат
Мова:
Українська
Розмiр:
30,90 KB
Завантажень:
82
Оцінка:
 
поточна оцінка 3.8


Скачати цю роботу безкоштовно
Пролистати роботу: 1  2 
Означення. Розкладом натурального числа n на прості множники (факторизацією числа) називається представлення його у вигляді n = , де pi – взаємно прості числа, ki 1 .

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

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

Метод Ферма

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

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

,

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

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

Перевірка: x2 – y2 = 122 – 11 = 143 = n.

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

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

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

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

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

202 – 391 = 9 = 32. Маємо рівність: 391 = 202 – 32.

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

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

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

Ідея алгоритма Полард – ро полягає в ітеративному обчисленні деякої наперед заданої поліноміальної функції f з цілими коефіцієнтами. Побудуємо послідовність xi наступним чином: x0 оберемо довільним із Zn, а xi+1 = f(xi) mod n, i 0. Оскільки xi можуть приймати лише скінченний набір значень (цілі числа від 0 до n), то існують такі цілі n1 та n2 (n1 < n2), що = . Враховуючи поліноміальність f, для кожного натурального k маємо: = , тобто починаючи з індекса i = n1 послідовність {xi mod n} буде періодичною.

Приклад. Нехай n = 21, x0 = 1, xi+1 = + 3 mod 21.

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

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

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

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

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

x0 = 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 a2 + 1) mod n; b b2 + 1) mod n; b b2 + 1) mod n;

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

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

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

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

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

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

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

a b d

2 2 1

5 26 1

26 19672 1

677 12391 1

19672 15217 1

11473 15217 1

12391 15217 157

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

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

a b d

2 2 1

5 26 НСД(21, 143) = 1

26 15 НСД(11, 143) = 11

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

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

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

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

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

Завантажити цю роботу безкоштовно
Пролистати роботу: 1  2 



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

Схожі роботи:


BR.com.ua © 1999-2017 | Реклама на сайті | Умови використання | Зворотній зв'язок