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

Рефераты, курсовые, дипломные, контрольные (предпросмотр)

Тип: Реферат. Файл: Word (.doc) в архиве zip. Язык: Украинский. Категория: Математика
Адрес этого реферата http://referat.repetitor.ua/?essayId=9657 или
Загрузить
В режиме предпросмотра не отображаются таблицы, графики и иллюстрации. Для получения полной версии нажмите кнопку «Загрузить». Рефераты, контрольные, дипломные, курсовые работы предоставляются в ознакомительных целях, не для плагиата.
Страница 1 из 2 [Всего 2 записей]1 2 »

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

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

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

Метод Ферма

Нехай n - складене число, яке не є степенем простого числа. Метод Ферма намагається знати такі натуральні x та y, що n = x2 - y2. Після чого дільниками числа n будутьЯкщо припустити що 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 наступним чином:

Алгоритм

Вхід: натуральне число 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, ... .

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

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

Знайдено розклад 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. Далі розв'яжемо систему рівнянь:

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

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

або

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

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

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

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

Нехай F = {p0, p1, p2, …, pt} - множникова основа, pi - різні прості числа, при чому дозволяється обрати p0 = -1. Побудуємо множину порівнянь

zi ,

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

,

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

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

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

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

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

z = z3 * z4 = 24 * 32 * 72 = (22 * 3 * 7)2 = 842

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

z3 * z4 = 292 * 542 842 (mod 143)

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

1362 = 842 (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)2 - n

Квадратичний алгоритм обирає

обчислює значення bi = (x + m)2 - n та перевіряє, чи факторизується bi у множниковій основі F

Помітимо, що

Алгоритм

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

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

1. Обрати множникову основу F = {p0, p1, p2, …, pt}, де p0 = -1, pi - i - те просте число p, для якого n є квадратичним лишком за модулем p.

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

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

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

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

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

3.2. Нехай b = . Покласти ai = x + m, bi = b, vi = (vi1, vi2, …, vit), де vij = eij 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, обчислити lj = ( ) / 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}, оскільки

RSSСтраница 1 из 2 [Всего 2 записей]1 2 »





При любом использовании материалов сайта обязательна гиперссылка на сайт «Репетитор».
Разработка и Дизайн компании Awelan
bigmir)net TOP 100 Rambler's Top100